#include using namespace std; using lint = long long int; struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i ma; lint get_fac(lint n) { lint k = n / 10000000 * 10000000; lint ret = ma[k]; FOR(j, k + 1, n + 1) ret = ret * j % MOD; return ret; } int main() { ma[0] = 1; ma[10000000] = 682498929; ma[20000000] = 491101308; ma[30000000] = 76479948; ma[40000000] = 723816384; ma[50000000] = 67347853; ma[60000000] = 27368307; ma[70000000] = 625544428; ma[80000000] = 199888908; ma[90000000] = 888050723; ma[100000000] = 927880474; ma[110000000] = 281863274; ma[120000000] = 661224977; ma[130000000] = 623534362; ma[140000000] = 970055531; ma[150000000] = 261384175; ma[160000000] = 195888993; ma[170000000] = 66404266; ma[180000000] = 547665832; ma[190000000] = 109838563; ma[200000000] = 933245637; ma[210000000] = 724691727; ma[220000000] = 368925948; ma[230000000] = 268838846; ma[240000000] = 136026497; ma[250000000] = 112390913; ma[260000000] = 135498044; ma[270000000] = 217544623; ma[280000000] = 419363534; ma[290000000] = 500780548; ma[300000000] = 668123525; ma[310000000] = 128487469; ma[320000000] = 30977140; ma[330000000] = 522049725; ma[340000000] = 309058615; ma[350000000] = 386027524; ma[360000000] = 189239124; ma[370000000] = 148528617; ma[380000000] = 940567523; ma[390000000] = 917084264; ma[400000000] = 429277690; ma[410000000] = 996164327; ma[420000000] = 358655417; ma[430000000] = 568392357; ma[440000000] = 780072518; ma[450000000] = 462639908; ma[460000000] = 275105629; ma[470000000] = 909210595; ma[480000000] = 99199382; ma[490000000] = 703397904; ma[500000000] = 733333339; ma[510000000] = 97830135; ma[520000000] = 608823837; ma[530000000] = 256141983; ma[540000000] = 141827977; ma[550000000] = 696628828; ma[560000000] = 637939935; ma[570000000] = 811575797; ma[580000000] = 848924691; ma[590000000] = 131772368; ma[600000000] = 724464507; ma[610000000] = 272814771; ma[620000000] = 326159309; ma[630000000] = 456152084; ma[640000000] = 903466878; ma[650000000] = 92255682; ma[660000000] = 769795511; ma[670000000] = 373745190; ma[680000000] = 606241871; ma[690000000] = 825871994; ma[700000000] = 957939114; ma[710000000] = 435887178; ma[720000000] = 852304035; ma[730000000] = 663307737; ma[740000000] = 375297772; ma[750000000] = 217598709; ma[760000000] = 624148346; ma[770000000] = 671734977; ma[780000000] = 624500515; ma[790000000] = 748510389; ma[800000000] = 203191898; ma[810000000] = 423951674; ma[820000000] = 629786193; ma[830000000] = 672850561; ma[840000000] = 814362881; ma[850000000] = 823845496; ma[860000000] = 116667533; ma[870000000] = 256473217; ma[880000000] = 627655552; ma[890000000] = 245795606; ma[900000000] = 586445753; ma[910000000] = 172114298; ma[920000000] = 193781724; ma[930000000] = 778983779; ma[940000000] = 83868974; ma[950000000] = 315103615; ma[960000000] = 965785236; ma[970000000] = 492741665; ma[980000000] = 377329025; ma[990000000] = 847549272; ma[1000000000] = 698611116; cin >> K; if (K % 2) cout << 0 << endl; else { lint ans = get_fac(K); lint ans2 = get_fac(K / 2); cout << mod_inverse(ans2, MOD) * mod_inverse(ans2, MOD) % MOD * ans % MOD << endl; } }