#include using namespace std; typedef long long ll; #define P pair #define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I) #define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I) #define TO(x,t,f) ((x)?(t):(f)) #define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9 #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v x is sorted #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v x is sorted #define NUM(x,v) (POSU(x,v)-POSL(x,v)) //x is sorted #define REV(x) (reverse(x.begin(),x.end())) //reverse ll gcd(ll a,ll b){if(a> n; if(n>=MOD){ cout << 0 << endl; return 0; } ll ans[101] = {}; ans[0] = 1; ans[1] = 682498929; ans[2] = 491101308; ans[3] = 76479948; ans[4] = 723816384; ans[5] = 67347853; ans[6] = 27368307; ans[7] = 625544428; ans[8] = 199888908; ans[9] = 888050723; ans[10] = 927880474; ans[11] = 281863274; ans[12] = 661224977; ans[13] = 623534362; ans[14] = 970055531; ans[15] = 261384175; ans[16] = 195888993; ans[17] = 66404266; ans[18] = 547665832; ans[19] = 109838563; ans[20] = 933245637; ans[21] = 724691727; ans[22] = 368925948; ans[23] = 268838846; ans[24] = 136026497; ans[25] = 112390913; ans[26] = 135498044; ans[27] = 217544623; ans[28] = 419363534; ans[29] = 500780548; ans[30] = 668123525; ans[31] = 128487469; ans[32] = 30977140; ans[33] = 522049725; ans[34] = 309058615; ans[35] = 386027524; ans[36] = 189239124; ans[37] = 148528617; ans[38] = 940567523; ans[39] = 917084264; ans[40] = 429277690; ans[41] = 996164327; ans[42] = 358655417; ans[43] = 568392357; ans[44] = 780072518; ans[45] = 462639908; ans[46] = 275105629; ans[47] = 909210595; ans[48] = 99199382; ans[49] = 703397904; ans[50] = 733333339; ans[51] = 97830135; ans[52] = 608823837; ans[53] = 256141983; ans[54] = 141827977; ans[55] = 696628828; ans[56] = 637939935; ans[57] = 811575797; ans[58] = 848924691; ans[59] = 131772368; ans[60] = 724464507; ans[61] = 272814771; ans[62] = 326159309; ans[63] = 456152084; ans[64] = 903466878; ans[65] = 92255682; ans[66] = 769795511; ans[67] = 373745190; ans[68] = 606241871; ans[69] = 825871994; ans[70] = 957939114; ans[71] = 435887178; ans[72] = 852304035; ans[73] = 663307737; ans[74] = 375297772; ans[75] = 217598709; ans[76] = 624148346; ans[77] = 671734977; ans[78] = 624500515; ans[79] = 748510389; ans[80] = 203191898; ans[81] = 423951674; ans[82] = 629786193; ans[83] = 672850561; ans[84] = 814362881; ans[85] = 823845496; ans[86] = 116667533; ans[87] = 256473217; ans[88] = 627655552; ans[89] = 245795606; ans[90] = 586445753; ans[91] = 172114298; ans[92] = 193781724; ans[93] = 778983779; ans[94] = 83868974; ans[95] = 315103615; ans[96] = 965785236; ans[97] = 492741665; ans[98] = 377329025; ans[99] = 847549272; ans[100] = 698611116; ll k = n/10000000; ll a = ans[ k ]; FOR(i,k*10000000+1,n+1){ (a*=i)%=MOD; } cout << a << endl; }