#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;
const int golden[40] = {0, 1, 2, 600000005, 400132278, 487584641, 876858367, 263720209, 87310300, 990011298, 804082657, 30041045, 525597963, 311174041, 458258908, 408113009, 457195388, 957266801, 755828841, 713043415, 404135883, 510801329, 240550576, 597828118, 844982714, 946100026, 204946949, 945121533, 72714973, 997449477, 241137224, 163055691, 921685423, 103881493, 189096351, 861996784, 959730307, 228509140, 178932181, 651360761};
int main()
{
int n;
cin >> n;
cout << golden[n-1] << endl;
}
