#723707 (C++17) No.502 階乗を計算するだけ

提出ソース
結果

問題	No.502 階乗を計算するだけ
ユーザー	hari64
提出日時	2021-12-12 13:34:00
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	6 ms / 1,000 ms
コード長	19,385 bytes
コンパイル時間	2,330 ms
コンパイル使用メモリ	220,404 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-21 00:12:26
合計ジャッジ時間	4,044 ms
ジャッジサーバーID （参考情報）	judge3 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	1 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	1 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	1 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	1 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	1 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	1 ms 5,376 KB
testcase_22	AC	5 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	5 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	3 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	3 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	5 ms 5,376 KB
testcase_31	AC	3 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	AC	6 ms 5,376 KB
testcase_34	AC	3 ms 5,376 KB
testcase_35	AC	6 ms 5,376 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	AC	5 ms 5,376 KB
testcase_38	AC	3 ms 5,376 KB
testcase_39	AC	5 ms 5,376 KB
testcase_40	AC	4 ms 5,376 KB
testcase_41	AC	1 ms 5,376 KB
testcase_42	AC	2 ms 5,376 KB
testcase_43	AC	1 ms 5,376 KB
testcase_44	AC	1 ms 5,376 KB
testcase_45	AC	2 ms 5,376 KB
testcase_46	AC	2 ms 5,376 KB
testcase_47	AC	2 ms 5,376 KB
testcase_48	AC	2 ms 5,376 KB
testcase_49	AC	1 ms 5,376 KB
testcase_50	AC	1 ms 5,376 KB
testcase_51	AC	1 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>  // clang-format off
using namespace std;constexpr int INF=1001001001;constexpr long long INFll=1001001001001001001;namespace viewer{template <class T>string f(T i){string s=(i==INF||i==INFll?"inf":to_string(i));s=string(max(0,3-int(s.size())),' ')+s;return s;}
template<class T>auto v(T&x,string end)->decltype(cerr<<x){return cerr<<x<<end;}void v(int x,string end){cerr<<f(x)<<end;}void v(long long x,string end){cerr<<f(x)<<end;}void v(float x,string end){cerr<<fixed<<setprecision(16)<<x<<end;}void v(double x,string end){cerr<<fixed<<setprecision(16)<<x<<end;}void v(long double x,string end){cerr<<fixed<<setprecision(16)<<x<<end;}
template<class T,class U>void v(const pair<T,U>&p,string end="\n"){cerr<<"(";v(p.first,", ");v(p.second,")"+end);}template<class T,class U>void v(const tuple<T,U>&t,string end="\n"){auto[a,b]=t;cerr<<"(";v(a,", ");v(b,")"+end);}template<class T,class U,class V>void v(const tuple<T,U,V>&t,string end="\n"){auto[a,b,c]=t;cerr<<"(";v(a,", ");v(b,", ");v(c,")"+end);}template<class T,class U,class V,class W>void v(const tuple<T,U,V,W>&t,string end="\n"){auto[a,b,c,d]=t;cerr<<"(";v(a,", ");v(b,", ");v(c,", ");v(d,")"+end);}
template<class T>void v(const vector<T>&vx,string);template<class T>auto ve(int,const vector<T>&vx)->decltype(cerr<<vx[0]){cerr<<"{";for(const T&x:vx)v(x,",");return cerr<<"}\n";}template <class T>auto ve(bool,const vector<T> &vx){cerr << "{\n";for(const T&x:vx)cerr<<"  ",v(x,",");cerr<<"}\n";}template<class T>void v(const vector<T>&vx, string){ve(0,vx);}template<class T>void v(const deque<T>&s,string e){vector<T>z(s.begin(),s.end());v(z,e);}
template<class T,class C>void v(const set<T,C>&s,string e){vector<T>z(s.begin(),s.end());v(z,e);}template<class T,class C>void v(const multiset<T,C>&s,string e){vector<T>z(s.begin(),s.end());v(z,e);}template<class T>void v(const unordered_set<T>&s,string e){vector<T>z(s.begin(),s.end());v(z,e);}template<class T>void v(const priority_queue<T>&p,string e){priority_queue<T>q=p;vector<T>z;while(!q.empty()){z.push_back(q.top());q.pop();}v(z,e);}
template<class T,class U>void v(const map<T, U>&m,string e){cerr<<"{"<<(m.empty()?"":"\n");for(const auto&kv:m){cerr<<"  [";v(kv.first,"");cerr<<"] : ";v(kv.second,"");cerr<<"\n";}cerr<<"}"+e;}
template<class T>void _view(int n,string s,T&var){cerr<<"\033[1;32m"<<n<<"\033[0m: \033[1;36m"<<s<<"\033[0m = ";v(var,"\n");}template<class T>void grid(T _){}void grid(const vector<vector<bool>>&vvb){cerr<<"\n";for(const vector<bool>&vb:vvb){for(const bool&b:vb)cerr<<(b?".":"#");cerr<<"\n";}}
void _debug(int, string){}template<typename H,typename... T>void _debug(int n,string S,H h,T... t){int i=0,cnt=0;for(;i<int(S.size());i++){if(S[i]=='(')cnt++;if(S[i]==')')cnt--;if(cnt==0&&S[i]==',')break;}if(i==int(S.size()))i=-1;if(i==-1)_view(n,S,h);else {string s1=S.substr(0,i);string s2=S.substr(i+2);if(s2=="\"grid\"")cerr<<"\033[1;32m"<<n<<"\033[0m: \033[1;36m"<<s1<<"\033[0m = ",grid(h);else _view(n,s1,h),_debug(n,s2,t...);}}}
template<class T>bool chmax(T&a,const T&b){return a<b?a=b,1:0;}template<class T>bool chmin(T&a,const T&b){return a>b?a=b,1:0;}
constexpr int MOD=1000000007;
/*https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a*/struct mint{int_fast64_t val;constexpr mint(long long v=0)noexcept:val(v%MOD){if(val<0)val+=MOD;}static constexpr int getmod()noexcept{return MOD;}constexpr mint operator-()const noexcept{return val?MOD-val:0;}
constexpr mint operator+(const mint&r)const noexcept{return mint(*this)+=r;}constexpr mint operator-(const mint&r)const noexcept{return mint(*this)-=r;}constexpr mint operator*(const mint&r)const noexcept{return mint(*this)*=r;}mint operator/(const mint&r)const noexcept{return mint(*this)/=r;}constexpr mint operator++(int)noexcept{val+=1;if(val>=MOD)val-=MOD;return*this;}constexpr mint operator--(int)noexcept{val-=1;if(val<0)val+=MOD;return*this;}
constexpr mint&operator+=(const mint&r)noexcept{val+=r.val;if(val>=MOD)val-=MOD;return*this;}constexpr mint&operator-=(const mint&r)noexcept{val-=r.val;if(val<0)val+=MOD;return*this;}constexpr mint&operator*=(const mint&r)noexcept{val=val*r.val%MOD;return*this;}mint&operator/=(const mint&r)noexcept{int_fast64_t a=r.val,b=MOD,u=1,v=0;while(b){int_fast64_t t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}val=val*u%MOD;if(val<0)val+=MOD;return*this;}
constexpr bool operator<(const mint&r)const noexcept{return this->val<r.val;}constexpr bool operator>(const mint&r)const noexcept{return this->val>r.val;}constexpr bool operator<=(const mint&r)const noexcept{return this->val<=r.val;}constexpr bool operator>=(const mint&r)const noexcept{return this->val>=r.val;}constexpr bool operator==(const mint&r)const noexcept{return this->val==r.val;}constexpr bool operator!=(const mint&r)const noexcept{return this->val!=r.val;}
friend ostream&operator<<(ostream&os,const mint&x)noexcept{return os<<x.val;}friend istream&operator>>(istream&os,mint&x)noexcept{return os>>x.val;}};
vector<mint>mod_factorial={mint(1)};mint modpow(mint base,long long exp){assert(exp>=0);mint ret=1;if(base==0&&exp==0)cerr<<"\033[1;31mWARNING: 0^0 is a mathematical expression with no agreed-upon value.\033[0m"<<endl;while(exp>0){if(exp&1)ret*=base;base*=base;exp>>=1;}return ret;}mint modinv(mint base)noexcept{return modpow(base,base.getmod()-2);}mint modfact(int n){if(int(mod_factorial.size())<=n){for(int i=mod_factorial.size();i<=n;i++){mint next=mod_factorial.back()*i;mod_factorial.push_back(next);}}return mod_factorial[n];}
/*x s.t. x^2 ≡ a (mod Prime) or -1*/mint modsqrt(mint a){long long p=mint::getmod();if(a<2)return a;if(modpow(a,(p-1)>>1)!=1)return -1;mint b=1,one=1;while(modpow(b,(p-1)>>1)==1)b+=one;long long m=p-1,e=0;while(m%2==0)m>>=1,e++;mint x=modpow(a,(m-1)>>1);mint y=a*x*x;x*=a;mint z=modpow(b,m);while(y!=1){long long j=0;mint t=y;while(t!=one)j++,t*=t;z=modpow(z,1ll<<(e-j-1));x*=z;z*=z;y*=z;e=j;}return x;}mint nCk(int n,int k){if(k<0||n<k)return mint(0);return modfact(n)*modinv(modfact(k))*modinv(modfact(n-k));}
/*min x s.t. a^x ≡ b (mod M) or -1*/mint modlog(mint a, mint b){long long m=mint::getmod();long long lo=-1,hi=m;while(hi-lo>1){long long mi=(lo+hi)>>1;if(mi*mi>=m)hi=mi;else lo=mi;}long long sqrtM=hi;map<mint,long long>apow;mint rem=a;for(long long r=1;r<sqrtM;r++){if(apow.find(rem)==apow.end())apow[rem]=r;rem*=a;}mint A=modpow(modinv(a),sqrtM);rem=b;for(mint q=0;q<sqrtM;q++){if(rem==1&&q>0)return q*sqrtM;if(apow.find(rem)!=apow.end())return q*sqrtM+apow[rem];rem*=A;}return -1;}
#ifdef ONLINE_JUDGE
#define debug(...)
#else
#define debug(...)viewer::_debug(__LINE__,#__VA_ARGS__,__VA_ARGS__)
#endif  // clang-format on

// よっぽどの事がない限り、式変形で巨大なN!は消せるはず
// それでも無理そうであるならば、以下を用いる
// N>=MOD⇒N!==0(mod MOD)に注意すると、MODまでのN!を適当な間隔で列挙すれば
// いかなるNであっても間隔分程度の計算量で算出可能

// ここに埋め込む
vector<int> fact1000000{
    1,         641102369, 578095319, 5832229,   259081142, 974067448, 316220877,
    690120224, 251368199, 980250487, 682498929, 134623568, 95936601,  933097914,
    167332441, 598816162, 336060741, 248744620, 626497524, 288843364, 491101308,
    245341950, 565768255, 246899319, 968999,    586350670, 638587686, 881746146,
    19426633,  850500036, 76479948,  268124147, 842267748, 886294336, 485348706,
    463847391, 544075857, 898187927, 798967520, 82926604,  723816384, 156530778,
    721996174, 299085602, 323604647, 172827403, 398699886, 530389102, 294587621,
    813805606, 67347853,  497478507, 196447201, 722054885, 228338256, 407719831,
    762479457, 746536789, 811667359, 778773518, 27368307,  438371670, 59469516,
    5974669,   766196482, 606322308, 86609485,  889750731, 340941507, 371263376,
    625544428, 788878910, 808412394, 996952918, 585237443, 1669644,   361786913,
    480748381, 595143852, 837229828, 199888908, 526807168, 579691190, 145404005,
    459188207, 534491822, 439729802, 840398449, 899297830, 235861787, 888050723,
    656116726, 736550105, 440902696, 85990869,  884343068, 56305184,  973478770,
    168891766, 804805577, 927880474, 876297919, 934814019, 676405347, 567277637,
    112249297, 44930135,  39417871,  47401357,  108819476, 281863274, 60168088,
    692636218, 432775082, 14235602,  770511792, 400295761, 697066277, 421835306,
    220108638, 661224977, 261799937, 168203998, 802214249, 544064410, 935080803,
    583967898, 211768084, 751231582, 972424306, 623534362, 335160196, 243276029,
    554749550, 60050552,  797848181, 395891998, 172428290, 159554990, 887420150,
    970055531, 250388809, 487998999, 856259313, 82104855,  232253360, 513365505,
    244109365, 1559745,   695345956, 261384175, 849009131, 323214113, 747664143,
    444090941, 659224434, 80729842,  570033864, 664989237, 827348878, 195888993,
    576798521, 457882808, 731551699, 212938473, 509096183, 827544702, 678320208,
    677711203, 289752035, 66404266,  555972231, 195290384, 97136305,  349551356,
    785113347, 83489485,  66247239,  52167191,  307390891, 547665832, 143066173,
    350016754, 917404120, 296269301, 996122673, 23015220,  602139210, 748566338,
    187348575, 109838563, 574053420, 105574531, 304173654, 542432219, 34538816,
    325636655, 437843114, 630621321, 26853683,  933245637, 616368450, 238971581,
    511371690, 557301633, 911398531, 848952161, 958992544, 925152039, 914456118,
    724691727, 636817583, 238087006, 946237212, 910291942, 114985663, 492237273,
    450387329, 834860913, 763017204, 368925948, 475812562, 740594930, 45060610,
    806047532, 464456846, 172115341, 75307702,  116261993, 562519302, 268838846,
    173784895, 243624360, 61570384,  481661251, 938269070, 95182730,  91068149,
    115435332, 495022305, 136026497, 506496856, 710729672, 113570024, 366384665,
    564758715, 270239666, 277118392, 79874094,  702807165, 112390913, 730341625,
    103056890, 677948390, 339464594, 167240465, 108312174, 839079953, 479334442,
    271788964, 135498044, 277717575, 591048681, 811637561, 353339603, 889410460,
    839849206, 192345193, 736265527, 316439118, 217544623, 788132977, 618898635,
    183011467, 380858207, 996097969, 898554793, 335353644, 54062950,  611251733,
    419363534, 965429853, 160398980, 151319402, 990918946, 607730875, 450718279,
    173539388, 648991369, 970937898, 500780548, 780122909, 39052406,  276894233,
    460373282, 651081062, 461415770, 358700839, 643638805, 560006119, 668123525,
    686692315, 673464765, 957633609, 199866123, 563432246, 841799766, 385330357,
    504962686, 954061253, 128487469, 685707545, 299172297, 717975101, 577786541,
    318951960, 773206631, 306832604, 204355779, 573592106, 30977140,  450398100,
    363172638, 258379324, 472935553, 93940075,  587220627, 776264326, 793270300,
    291733496, 522049725, 579995261, 335416359, 142946099, 472012302, 559947225,
    332139472, 499377092, 464599136, 164752359, 309058615, 86117128,  580204973,
    563781682, 954840109, 624577416, 895609896, 888287558, 836813268, 926036911,
    386027524, 184419613, 724205533, 403351886, 715247054, 716986954, 830567832,
    383388563, 68409439,  6734065,   189239124, 68322490,  943653305, 405755338,
    811056092, 179518046, 825132993, 343807435, 985084650, 868553027, 148528617,
    160684257, 882148737, 591915968, 701445829, 529726489, 302177126, 974886682,
    241107368, 798830099, 940567523, 11633075,  325334066, 346091869, 115312728,
    473718967, 218129285, 878471898, 180002392, 699739374, 917084264, 856859395,
    435327356, 808651347, 421623838, 105419548, 59883031,  322487421, 79716267,
    715317963, 429277690, 398078032, 316486674, 384843585, 940338439, 937409008,
    940524812, 947549662, 833550543, 593524514, 996164327, 987314628, 697611981,
    636177449, 274192146, 418537348, 925347821, 952831975, 893732627, 1277567,
    358655417, 141866945, 581830879, 987597705, 347046911, 775305697, 125354499,
    951540811, 247662371, 343043237, 568392357, 997474832, 209244402, 380480118,
    149586983, 392838702, 309134554, 990779998, 263053337, 325362513, 780072518,
    551028176, 990826116, 989944961, 155569943, 596737944, 711553356, 268844715,
    451373308, 379404150, 462639908, 961812918, 654611901, 382776490, 41815820,
    843321396, 675258797, 845583555, 934281721, 741114145, 275105629, 666247477,
    325912072, 526131620, 252551589, 432030917, 554917439, 818036959, 754363835,
    795190182, 909210595, 278704903, 719566487, 628514947, 424989675, 321685608,
    50590510,  832069712, 198768464, 702004730, 99199382,  707469729, 747407118,
    302020341, 497196934, 5003231,   726997875, 382617671, 296229203, 183888367,
    703397904, 552133875, 732868367, 350095207, 26031303,  863250534, 216665960,
    561745549, 352946234, 784139777, 733333339, 503105966, 459878625, 803187381,
    16634739,  180898306, 68718097,  985594252, 404206040, 749724532, 97830135,
    611751357, 31131935,  662741752, 864326453, 864869025, 167831173, 559214642,
    718498895, 91352335,  608823837, 473379392, 385388084, 152267158, 681756977,
    46819124,  313132653, 56547945,  442795120, 796616594, 256141983, 152028387,
    636578562, 385377759, 553033642, 491415383, 919273670, 996049638, 326686486,
    160150665, 141827977, 540818053, 693305776, 593938674, 186576440, 688809790,
    565456578, 749296077, 519397500, 551096742, 696628828, 775025061, 370732451,
    164246193, 915265013, 457469634, 923043932, 912368644, 777901604, 464118005,
    637939935, 956856710, 490676632, 453019482, 462528877, 502297454, 798895521,
    100498586, 699767918, 849974789, 811575797, 438952959, 606870929, 907720182,
    179111720, 48053248,  508038818, 811944661, 752550134, 401382061, 848924691,
    764368449, 34629406,  529840945, 435904287, 26011548,  208184231, 446477394,
    206330671, 366033520, 131772368, 185646898, 648711554, 472759660, 523696723,
    271198437, 25058942,  859369491, 817928963, 330711333, 724464507, 437605233,
    701453022, 626663115, 281230685, 510650790, 596949867, 295726547, 303076380,
    465070856, 272814771, 538771609, 48824684,  951279549, 939889684, 564188856,
    48527183,  201307702, 484458461, 861754542, 326159309, 181594759, 668422905,
    286273596, 965656187, 44135644,  359960756, 936229527, 407934361, 267193060,
    456152084, 459116722, 124804049, 262322489, 920251227, 816929577, 483924582,
    151834896, 167087470, 490222511, 903466878, 361583925, 368114731, 339383292,
    388728584, 218107212, 249153339, 909458706, 322908524, 202649964, 92255682,
    573074791, 15570863,  94331513,  744158074, 196345098, 334326205, 9416035,
    98349682,  882121662, 769795511, 231988936, 888146074, 137603545, 582627184,
    407518072, 919419361, 909433461, 986708498, 310317874, 373745190, 263645931,
    256853930, 876379959, 702823274, 147050765, 308186532, 175504139, 180350107,
    797736554, 606241871, 384547635, 273712630, 586444655, 682189174, 666493603,
    946867127, 819114541, 502371023, 261970285, 825871994, 126925175, 701506133,
    314738056, 341779962, 561011609, 815463367, 46765164,  49187570,  188054995,
    957939114, 64814326,  933376898, 329837066, 338121343, 765215899, 869630152,
    978119194, 632627667, 975266085, 435887178, 282092463, 129621197, 758245605,
    827722926, 201339230, 918513230, 322096036, 547838438, 985546115, 852304035,
    593090119, 689189630, 555842733, 567033437, 469928208, 212842957, 117842065,
    404149413, 155133422, 663307737, 208761293, 206282795, 717946122, 488906585,
    414236650, 280700600, 962670136, 534279149, 214569244, 375297772, 811053196,
    922377372, 289594327, 219932130, 211487466, 701050258, 398782410, 863002719,
    27236531,  217598709, 375472836, 810551911, 178598958, 247844667, 676526196,
    812283640, 863066876, 857241854, 113917835, 624148346, 726089763, 564827277,
    826300950, 478982047, 439411911, 454039189, 633292726, 48562889,  802100365,
    671734977, 945204804, 508831870, 398781902, 897162044, 644050694, 892168027,
    828883117, 277714559, 713448377, 624500515, 590098114, 808691930, 514359662,
    895205045, 715264908, 628829100, 484492064, 919717789, 513196123, 748510389,
    403652653, 574455974, 77123823,  172096141, 819801784, 581418893, 15655126,
    15391652,  875641535, 203191898, 264582598, 880691101, 907800444, 986598821,
    340030191, 264688936, 369832433, 785804644, 842065079, 423951674, 663560047,
    696623384, 496709826, 161960209, 331910086, 541120825, 951524114, 841656666,
    162683802, 629786193, 190395535, 269571439, 832671304, 76770272,  341080135,
    421943723, 494210290, 751040886, 317076664, 672850561, 72482816,  493689107,
    135625240, 100228913, 684748812, 639655136, 906233141, 929893103, 277813439,
    814362881, 562608724, 406024012, 885537778, 10065330,  60625018,  983737173,
    60517502,  551060742, 804930491, 823845496, 727416538, 946421040, 678171399,
    842203531, 175638827, 894247956, 538609927, 885362182, 946464959, 116667533,
    749816133, 241427979, 871117927, 281804989, 163928347, 563796647, 640266394,
    774625892, 59342705,  256473217, 674115061, 918860977, 322633051, 753513874,
    393556719, 304644842, 767372800, 161362528, 754787150, 627655552, 677395736,
    799289297, 846650652, 816701166, 687265514, 787113234, 358757251, 701220427,
    607715125, 245795606, 600624983, 10475577,  728620948, 759404319, 36292292,
    491466901, 22556579,  114495791, 647630109, 586445753, 482254337, 718623833,
    763514207, 66547751,  953634340, 351472920, 308474522, 494166907, 634359666,
    172114298, 865440961, 364380585, 921648059, 965683742, 260466949, 117483873,
    962540888, 237120480, 620531822, 193781724, 213092254, 107141741, 602742426,
    793307102, 756154604, 236455213, 362928234, 14162538,  753042874, 778983779,
    25977209,  49389215,  698308420, 859637374, 49031023,  713258160, 737331920,
    923333660, 804861409, 83868974,  682873215, 217298111, 883278906, 176966527,
    954913,    105359006, 390019735, 10430738,  706334445, 315103615, 567473423,
    708233401, 48160594,  946149627, 346966053, 281329488, 462880311, 31503476,
    185438078, 965785236, 992656683, 916291845, 881482632, 899946391, 321900901,
    512634493, 303338827, 121000338, 967284733, 492741665, 152233223, 165393390,
    680128316, 917041303, 532702135, 741626808, 496442755, 536841269, 131384366,
    377329025, 301196854, 859917803, 676511002, 373451745, 847645126, 823495900,
    576368335, 73146164,  954958912, 847549272, 241289571, 646654592, 216046746,
    205951465, 3258987,   780882948, 822439091, 598245292, 869544707, 698611116,

};
// 埋め込み生成用
void pre_calc() {
    std::ofstream writing_file;
    std::string filename = "fact1000000.txt";
    writing_file.open(filename, std::ios::out);
    writing_file << 1 << ", ";
    long long ans = 1;
    for (int i = 1; i <= MOD; i++) {
        ans *= i;
        ans %= MOD;
        if (i % 1000000 == 0) {
            writing_file << ans << ", ";
        }
    }
    writing_file << endl;
    writing_file.close();
}
mint fast_modfact(int n) {
    if (n >= MOD) {
        return 0;
    }
    mint ret = fact1000000[n / 1000000];
    for (int i = (n / 1000000 * 1000000) + 1; i <= n; i++) {
        ret *= mint(i);
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    // pre_calc();

    int n;
    cin >> n;
    cout << fast_modfact(n) << endl;

    return 0;
}
yukicoder

結果

テストケース

ソースコード
