結果
| 問題 | No.502 階乗を計算するだけ |
| ユーザー |
 0313
|
| 提出日時 | 2019-03-26 12:35:47 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
AC
|
| 実行時間 | 18 ms / 1,000 ms |
| コード長 | 42,645 bytes |
| コンパイル時間 | 1,989 ms |
| コンパイル使用メモリ | 92,316 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-10-11 01:19:58 |
| 合計ジャッジ時間 | 3,367 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,820 KB |
| testcase_02 | AC | 2 ms
6,816 KB |
| testcase_03 | AC | 2 ms
6,816 KB |
| testcase_04 | AC | 1 ms
6,816 KB |
| testcase_05 | AC | 1 ms
6,820 KB |
| testcase_06 | AC | 1 ms
6,820 KB |
| testcase_07 | AC | 1 ms
6,820 KB |
| testcase_08 | AC | 1 ms
6,816 KB |
| testcase_09 | AC | 2 ms
6,816 KB |
| testcase_10 | AC | 1 ms
6,820 KB |
| testcase_11 | AC | 1 ms
6,816 KB |
| testcase_12 | AC | 2 ms
6,816 KB |
| testcase_13 | AC | 2 ms
6,816 KB |
| testcase_14 | AC | 2 ms
6,816 KB |
| testcase_15 | AC | 1 ms
6,816 KB |
| testcase_16 | AC | 1 ms
6,816 KB |
| testcase_17 | AC | 2 ms
6,816 KB |
| testcase_18 | AC | 1 ms
6,820 KB |
| testcase_19 | AC | 1 ms
6,816 KB |
| testcase_20 | AC | 2 ms
6,816 KB |
| testcase_21 | AC | 1 ms
6,816 KB |
| testcase_22 | AC | 17 ms
6,820 KB |
| testcase_23 | AC | 6 ms
6,816 KB |
| testcase_24 | AC | 11 ms
6,820 KB |
| testcase_25 | AC | 3 ms
6,816 KB |
| testcase_26 | AC | 8 ms
6,820 KB |
| testcase_27 | AC | 4 ms
6,820 KB |
| testcase_28 | AC | 7 ms
6,816 KB |
| testcase_29 | AC | 3 ms
6,816 KB |
| testcase_30 | AC | 16 ms
6,820 KB |
| testcase_31 | AC | 9 ms
6,820 KB |
| testcase_32 | AC | 3 ms
6,816 KB |
| testcase_33 | AC | 18 ms
6,820 KB |
| testcase_34 | AC | 5 ms
6,820 KB |
| testcase_35 | AC | 15 ms
6,820 KB |
| testcase_36 | AC | 4 ms
6,816 KB |
| testcase_37 | AC | 16 ms
6,816 KB |
| testcase_38 | AC | 5 ms
6,816 KB |
| testcase_39 | AC | 14 ms
6,816 KB |
| testcase_40 | AC | 10 ms
6,820 KB |
| testcase_41 | AC | 1 ms
6,820 KB |
| testcase_42 | AC | 2 ms
6,816 KB |
| testcase_43 | AC | 1 ms
6,816 KB |
| testcase_44 | AC | 2 ms
6,820 KB |
| testcase_45 | AC | 2 ms
6,820 KB |
| testcase_46 | AC | 2 ms
6,820 KB |
| testcase_47 | AC | 2 ms
6,816 KB |
| testcase_48 | AC | 1 ms
6,820 KB |
| testcase_49 | AC | 1 ms
6,816 KB |
| testcase_50 | AC | 2 ms
6,816 KB |
| testcase_51 | AC | 1 ms
6,816 KB |
コンパイルメッセージ
main.cpp: In function ‘long long int mod_fact(long long int, long long int)’:
main.cpp:1131:22: warning: ‘ret’ may be used uninitialized in this function [-Wmaybe-uninitialized]
1131 | return ret % MOD;
| ^~~
ソースコード
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <utility>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cstdio>
#include <math.h>
#include <stdio.h>
#include <deque>
using namespace std;
#define REP(i,n,m) for( long long int i = (n); i < (m); i++ )
#define REV(v) for (auto itr = v.rbegin(); itr != v.rend(); itr++)
#define ll long long
#define ALL(a) (a).begin(), (a).end()
#define SORT(v) sort( ALL(v) );
#define LAST(v) v[v.size()-1]
#define ZERO(a) memset(a,0,sizeof(a));
#define MINUS(a) memset(a,-1,sizeof(a));
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pi pair<int, int>
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define IIN(a) int a; cin >> a;
#define LIN(a) ll a; cin >> a;
#define SIN(a) string a; cin >> a;
#define VL(v,n) vector<ll> v(n);
#define Read_VL(v,n) vector<ll> v(n);REP(i,0,n)cin>>v[i];
#define sumV(v,n) Vl(acm,n) REP(i,0,n) acm[i] = v[i] + ( i == 0 ? 0 : acm[i - 1]);
#define EPS (1e-10)
#define INF 1000000000000LL
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class T=ll>struct Graph{
int n;
vector<vector<tuple<ll,T>>>edge;
Graph(int N=1):n(N){edge.resize(n);}
void add(ll f,ll t,T c,bool d=false){
edge[f].emplace_back(t,c);
if(!d)edge[t].emplace_back(f,c);
}
void view(){
REP(i,0,n)for(auto&e:edge[i])
puta(i,"=>",get<0>(e),", cost :",get<1>(e));
}
};
bool length_cmp( string &a, string &b ){
return a.size() < b.size();
}
ll StoLL( string s )
{
ll num=0;
REP( i, 0, s.size() ){
num = num * 10 + ( s[i] ^ 48 );
}
return num;
}
ll CtoLL( char c )
{
if( 'a' <= c && c <= 'z'){
return (ll)( c ^ 96 ) ;
}
else if( 'A' <= c && c <= 'Z'){
return (ll)( c ^ 64 );
}
return 0;
}
ll MOD=1000000007;
ll dx[4] = { 1, 0, -1, 0 };
ll dy[4] = { 0, 1, 0, -1 };
//I ASCII code: '0' = 48; 'A' = 65; 'a' = 97
#include <chrono>
ll fact[1001];
void precalc(){
fact[ 0 ] = 1;
fact[ 1 ] = 641102369 ;//( 1 e6 )!
fact[ 2 ] = 578095319 ;//( 2 e6)!
fact[ 3 ] = 5832229 ;//( 3 e6)!
fact[ 4 ] = 259081142 ;//( 4 e6)!
fact[ 5 ] = 974067448 ;//( 5 e6)!
fact[ 6 ] = 316220877 ;//( 6 e6)!
fact[ 7 ] = 690120224 ;//( 7 e6)!
fact[ 8 ] = 251368199 ;//( 8 e6)!
fact[ 9 ] = 980250487 ;//( 9 e6)!
fact[ 10 ] = 682498929 ;//( 10 e6)!
fact[ 11 ] = 134623568 ;//( 11 e6)!
fact[ 12 ] = 95936601 ;//( 12 e6)!
fact[ 13 ] = 933097914 ;//( 13 e6)!
fact[ 14 ] = 167332441 ;//( 14 e6)!
fact[ 15 ] = 598816162 ;//( 15 e6)!
fact[ 16 ] = 336060741 ;//( 16 e6)!
fact[ 17 ] = 248744620 ;//( 17 e6)!
fact[ 18 ] = 626497524 ;//( 18 e6)!
fact[ 19 ] = 288843364 ;//( 19 e6)!
fact[ 20 ] = 491101308 ;//( 20 e6)!
fact[ 21 ] = 245341950 ;//( 21 e6)!
fact[ 22 ] = 565768255 ;//( 22 e6)!
fact[ 23 ] = 246899319 ;//( 23 e6)!
fact[ 24 ] = 968999 ;//( 24 e6)!
fact[ 25 ] = 586350670 ;//( 25 e6)!
fact[ 26 ] = 638587686 ;//( 26 e6)!
fact[ 27 ] = 881746146 ;//( 27 e6)!
fact[ 28 ] = 19426633 ;//( 28 e6)!
fact[ 29 ] = 850500036 ;//( 29 e6)!
fact[ 30 ] = 76479948 ;//( 30 e6)!
fact[ 31 ] = 268124147 ;//( 31 e6)!
fact[ 32 ] = 842267748 ;//( 32 e6)!
fact[ 33 ] = 886294336 ;//( 33 e6)!
fact[ 34 ] = 485348706 ;//( 34 e6)!
fact[ 35 ] = 463847391 ;//( 35 e6)!
fact[ 36 ] = 544075857 ;//( 36 e6)!
fact[ 37 ] = 898187927 ;//( 37 e6)!
fact[ 38 ] = 798967520 ;//( 38 e6)!
fact[ 39 ] = 82926604 ;//( 39 e6)!
fact[ 40 ] = 723816384 ;//( 40 e6)!
fact[ 41 ] = 156530778 ;//( 41 e6)!
fact[ 42 ] = 721996174 ;//( 42 e6)!
fact[ 43 ] = 299085602 ;//( 43 e6)!
fact[ 44 ] = 323604647 ;//( 44 e6)!
fact[ 45 ] = 172827403 ;//( 45 e6)!
fact[ 46 ] = 398699886 ;//( 46 e6)!
fact[ 47 ] = 530389102 ;//( 47 e6)!
fact[ 48 ] = 294587621 ;//( 48 e6)!
fact[ 49 ] = 813805606 ;//( 49 e6)!
fact[ 50 ] = 67347853 ;//( 50 e6)!
fact[ 51 ] = 497478507 ;//( 51 e6)!
fact[ 52 ] = 196447201 ;//( 52 e6)!
fact[ 53 ] = 722054885 ;//( 53 e6)!
fact[ 54 ] = 228338256 ;//( 54 e6)!
fact[ 55 ] = 407719831 ;//( 55 e6)!
fact[ 56 ] = 762479457 ;//( 56 e6)!
fact[ 57 ] = 746536789 ;//( 57 e6)!
fact[ 58 ] = 811667359 ;//( 58 e6)!
fact[ 59 ] = 778773518 ;//( 59 e6)!
fact[ 60 ] = 27368307 ;//( 60 e6)!
fact[ 61 ] = 438371670 ;//( 61 e6)!
fact[ 62 ] = 59469516 ;//( 62 e6)!
fact[ 63 ] = 5974669 ;//( 63 e6)!
fact[ 64 ] = 766196482 ;//( 64 e6)!
fact[ 65 ] = 606322308 ;//( 65 e6)!
fact[ 66 ] = 86609485 ;//( 66 e6)!
fact[ 67 ] = 889750731 ;//( 67 e6)!
fact[ 68 ] = 340941507 ;//( 68 e6)!
fact[ 69 ] = 371263376 ;//( 69 e6)!
fact[ 70 ] = 625544428 ;//( 70 e6)!
fact[ 71 ] = 788878910 ;//( 71 e6)!
fact[ 72 ] = 808412394 ;//( 72 e6)!
fact[ 73 ] = 996952918 ;//( 73 e6)!
fact[ 74 ] = 585237443 ;//( 74 e6)!
fact[ 75 ] = 1669644 ;//( 75 e6)!
fact[ 76 ] = 361786913 ;//( 76 e6)!
fact[ 77 ] = 480748381 ;//( 77 e6)!
fact[ 78 ] = 595143852 ;//( 78 e6)!
fact[ 79 ] = 837229828 ;//( 79 e6)!
fact[ 80 ] = 199888908 ;//( 80 e6)!
fact[ 81 ] = 526807168 ;//( 81 e6)!
fact[ 82 ] = 579691190 ;//( 82 e6)!
fact[ 83 ] = 145404005 ;//( 83 e6)!
fact[ 84 ] = 459188207 ;//( 84 e6)!
fact[ 85 ] = 534491822 ;//( 85 e6)!
fact[ 86 ] = 439729802 ;//( 86 e6)!
fact[ 87 ] = 840398449 ;//( 87 e6)!
fact[ 88 ] = 899297830 ;//( 88 e6)!
fact[ 89 ] = 235861787 ;//( 89 e6)!
fact[ 90 ] = 888050723 ;//( 90 e6)!
fact[ 91 ] = 656116726 ;//( 91 e6)!
fact[ 92 ] = 736550105 ;//( 92 e6)!
fact[ 93 ] = 440902696 ;//( 93 e6)!
fact[ 94 ] = 85990869 ;//( 94 e6)!
fact[ 95 ] = 884343068 ;//( 95 e6)!
fact[ 96 ] = 56305184 ;//( 96 e6)!
fact[ 97 ] = 973478770 ;//( 97 e6)!
fact[ 98 ] = 168891766 ;//( 98 e6)!
fact[ 99 ] = 804805577 ;//( 99 e6)!
fact[ 100 ] = 927880474 ;//( 100 e6)!
fact[ 101 ] = 876297919 ;//( 101 e6)!
fact[ 102 ] = 934814019 ;//( 102 e6)!
fact[ 103 ] = 676405347 ;//( 103 e6)!
fact[ 104 ] = 567277637 ;//( 104 e6)!
fact[ 105 ] = 112249297 ;//( 105 e6)!
fact[ 106 ] = 44930135 ;//( 106 e6)!
fact[ 107 ] = 39417871 ;//( 107 e6)!
fact[ 108 ] = 47401357 ;//( 108 e6)!
fact[ 109 ] = 108819476 ;//( 109 e6)!
fact[ 110 ] = 281863274 ;//( 110 e6)!
fact[ 111 ] = 60168088 ;//( 111 e6)!
fact[ 112 ] = 692636218 ;//( 112 e6)!
fact[ 113 ] = 432775082 ;//( 113 e6)!
fact[ 114 ] = 14235602 ;//( 114 e6)!
fact[ 115 ] = 770511792 ;//( 115 e6)!
fact[ 116 ] = 400295761 ;//( 116 e6)!
fact[ 117 ] = 697066277 ;//( 117 e6)!
fact[ 118 ] = 421835306 ;//( 118 e6)!
fact[ 119 ] = 220108638 ;//( 119 e6)!
fact[ 120 ] = 661224977 ;//( 120 e6)!
fact[ 121 ] = 261799937 ;//( 121 e6)!
fact[ 122 ] = 168203998 ;//( 122 e6)!
fact[ 123 ] = 802214249 ;//( 123 e6)!
fact[ 124 ] = 544064410 ;//( 124 e6)!
fact[ 125 ] = 935080803 ;//( 125 e6)!
fact[ 126 ] = 583967898 ;//( 126 e6)!
fact[ 127 ] = 211768084 ;//( 127 e6)!
fact[ 128 ] = 751231582 ;//( 128 e6)!
fact[ 129 ] = 972424306 ;//( 129 e6)!
fact[ 130 ] = 623534362 ;//( 130 e6)!
fact[ 131 ] = 335160196 ;//( 131 e6)!
fact[ 132 ] = 243276029 ;//( 132 e6)!
fact[ 133 ] = 554749550 ;//( 133 e6)!
fact[ 134 ] = 60050552 ;//( 134 e6)!
fact[ 135 ] = 797848181 ;//( 135 e6)!
fact[ 136 ] = 395891998 ;//( 136 e6)!
fact[ 137 ] = 172428290 ;//( 137 e6)!
fact[ 138 ] = 159554990 ;//( 138 e6)!
fact[ 139 ] = 887420150 ;//( 139 e6)!
fact[ 140 ] = 970055531 ;//( 140 e6)!
fact[ 141 ] = 250388809 ;//( 141 e6)!
fact[ 142 ] = 487998999 ;//( 142 e6)!
fact[ 143 ] = 856259313 ;//( 143 e6)!
fact[ 144 ] = 82104855 ;//( 144 e6)!
fact[ 145 ] = 232253360 ;//( 145 e6)!
fact[ 146 ] = 513365505 ;//( 146 e6)!
fact[ 147 ] = 244109365 ;//( 147 e6)!
fact[ 148 ] = 1559745 ;//( 148 e6)!
fact[ 149 ] = 695345956 ;//( 149 e6)!
fact[ 150 ] = 261384175 ;//( 150 e6)!
fact[ 151 ] = 849009131 ;//( 151 e6)!
fact[ 152 ] = 323214113 ;//( 152 e6)!
fact[ 153 ] = 747664143 ;//( 153 e6)!
fact[ 154 ] = 444090941 ;//( 154 e6)!
fact[ 155 ] = 659224434 ;//( 155 e6)!
fact[ 156 ] = 80729842 ;//( 156 e6)!
fact[ 157 ] = 570033864 ;//( 157 e6)!
fact[ 158 ] = 664989237 ;//( 158 e6)!
fact[ 159 ] = 827348878 ;//( 159 e6)!
fact[ 160 ] = 195888993 ;//( 160 e6)!
fact[ 161 ] = 576798521 ;//( 161 e6)!
fact[ 162 ] = 457882808 ;//( 162 e6)!
fact[ 163 ] = 731551699 ;//( 163 e6)!
fact[ 164 ] = 212938473 ;//( 164 e6)!
fact[ 165 ] = 509096183 ;//( 165 e6)!
fact[ 166 ] = 827544702 ;//( 166 e6)!
fact[ 167 ] = 678320208 ;//( 167 e6)!
fact[ 168 ] = 677711203 ;//( 168 e6)!
fact[ 169 ] = 289752035 ;//( 169 e6)!
fact[ 170 ] = 66404266 ;//( 170 e6)!
fact[ 171 ] = 555972231 ;//( 171 e6)!
fact[ 172 ] = 195290384 ;//( 172 e6)!
fact[ 173 ] = 97136305 ;//( 173 e6)!
fact[ 174 ] = 349551356 ;//( 174 e6)!
fact[ 175 ] = 785113347 ;//( 175 e6)!
fact[ 176 ] = 83489485 ;//( 176 e6)!
fact[ 177 ] = 66247239 ;//( 177 e6)!
fact[ 178 ] = 52167191 ;//( 178 e6)!
fact[ 179 ] = 307390891 ;//( 179 e6)!
fact[ 180 ] = 547665832 ;//( 180 e6)!
fact[ 181 ] = 143066173 ;//( 181 e6)!
fact[ 182 ] = 350016754 ;//( 182 e6)!
fact[ 183 ] = 917404120 ;//( 183 e6)!
fact[ 184 ] = 296269301 ;//( 184 e6)!
fact[ 185 ] = 996122673 ;//( 185 e6)!
fact[ 186 ] = 23015220 ;//( 186 e6)!
fact[ 187 ] = 602139210 ;//( 187 e6)!
fact[ 188 ] = 748566338 ;//( 188 e6)!
fact[ 189 ] = 187348575 ;//( 189 e6)!
fact[ 190 ] = 109838563 ;//( 190 e6)!
fact[ 191 ] = 574053420 ;//( 191 e6)!
fact[ 192 ] = 105574531 ;//( 192 e6)!
fact[ 193 ] = 304173654 ;//( 193 e6)!
fact[ 194 ] = 542432219 ;//( 194 e6)!
fact[ 195 ] = 34538816 ;//( 195 e6)!
fact[ 196 ] = 325636655 ;//( 196 e6)!
fact[ 197 ] = 437843114 ;//( 197 e6)!
fact[ 198 ] = 630621321 ;//( 198 e6)!
fact[ 199 ] = 26853683 ;//( 199 e6)!
fact[ 200 ] = 933245637 ;//( 200 e6)!
fact[ 201 ] = 616368450 ;//( 201 e6)!
fact[ 202 ] = 238971581 ;//( 202 e6)!
fact[ 203 ] = 511371690 ;//( 203 e6)!
fact[ 204 ] = 557301633 ;//( 204 e6)!
fact[ 205 ] = 911398531 ;//( 205 e6)!
fact[ 206 ] = 848952161 ;//( 206 e6)!
fact[ 207 ] = 958992544 ;//( 207 e6)!
fact[ 208 ] = 925152039 ;//( 208 e6)!
fact[ 209 ] = 914456118 ;//( 209 e6)!
fact[ 210 ] = 724691727 ;//( 210 e6)!
fact[ 211 ] = 636817583 ;//( 211 e6)!
fact[ 212 ] = 238087006 ;//( 212 e6)!
fact[ 213 ] = 946237212 ;//( 213 e6)!
fact[ 214 ] = 910291942 ;//( 214 e6)!
fact[ 215 ] = 114985663 ;//( 215 e6)!
fact[ 216 ] = 492237273 ;//( 216 e6)!
fact[ 217 ] = 450387329 ;//( 217 e6)!
fact[ 218 ] = 834860913 ;//( 218 e6)!
fact[ 219 ] = 763017204 ;//( 219 e6)!
fact[ 220 ] = 368925948 ;//( 220 e6)!
fact[ 221 ] = 475812562 ;//( 221 e6)!
fact[ 222 ] = 740594930 ;//( 222 e6)!
fact[ 223 ] = 45060610 ;//( 223 e6)!
fact[ 224 ] = 806047532 ;//( 224 e6)!
fact[ 225 ] = 464456846 ;//( 225 e6)!
fact[ 226 ] = 172115341 ;//( 226 e6)!
fact[ 227 ] = 75307702 ;//( 227 e6)!
fact[ 228 ] = 116261993 ;//( 228 e6)!
fact[ 229 ] = 562519302 ;//( 229 e6)!
fact[ 230 ] = 268838846 ;//( 230 e6)!
fact[ 231 ] = 173784895 ;//( 231 e6)!
fact[ 232 ] = 243624360 ;//( 232 e6)!
fact[ 233 ] = 61570384 ;//( 233 e6)!
fact[ 234 ] = 481661251 ;//( 234 e6)!
fact[ 235 ] = 938269070 ;//( 235 e6)!
fact[ 236 ] = 95182730 ;//( 236 e6)!
fact[ 237 ] = 91068149 ;//( 237 e6)!
fact[ 238 ] = 115435332 ;//( 238 e6)!
fact[ 239 ] = 495022305 ;//( 239 e6)!
fact[ 240 ] = 136026497 ;//( 240 e6)!
fact[ 241 ] = 506496856 ;//( 241 e6)!
fact[ 242 ] = 710729672 ;//( 242 e6)!
fact[ 243 ] = 113570024 ;//( 243 e6)!
fact[ 244 ] = 366384665 ;//( 244 e6)!
fact[ 245 ] = 564758715 ;//( 245 e6)!
fact[ 246 ] = 270239666 ;//( 246 e6)!
fact[ 247 ] = 277118392 ;//( 247 e6)!
fact[ 248 ] = 79874094 ;//( 248 e6)!
fact[ 249 ] = 702807165 ;//( 249 e6)!
fact[ 250 ] = 112390913 ;//( 250 e6)!
fact[ 251 ] = 730341625 ;//( 251 e6)!
fact[ 252 ] = 103056890 ;//( 252 e6)!
fact[ 253 ] = 677948390 ;//( 253 e6)!
fact[ 254 ] = 339464594 ;//( 254 e6)!
fact[ 255 ] = 167240465 ;//( 255 e6)!
fact[ 256 ] = 108312174 ;//( 256 e6)!
fact[ 257 ] = 839079953 ;//( 257 e6)!
fact[ 258 ] = 479334442 ;//( 258 e6)!
fact[ 259 ] = 271788964 ;//( 259 e6)!
fact[ 260 ] = 135498044 ;//( 260 e6)!
fact[ 261 ] = 277717575 ;//( 261 e6)!
fact[ 262 ] = 591048681 ;//( 262 e6)!
fact[ 263 ] = 811637561 ;//( 263 e6)!
fact[ 264 ] = 353339603 ;//( 264 e6)!
fact[ 265 ] = 889410460 ;//( 265 e6)!
fact[ 266 ] = 839849206 ;//( 266 e6)!
fact[ 267 ] = 192345193 ;//( 267 e6)!
fact[ 268 ] = 736265527 ;//( 268 e6)!
fact[ 269 ] = 316439118 ;//( 269 e6)!
fact[ 270 ] = 217544623 ;//( 270 e6)!
fact[ 271 ] = 788132977 ;//( 271 e6)!
fact[ 272 ] = 618898635 ;//( 272 e6)!
fact[ 273 ] = 183011467 ;//( 273 e6)!
fact[ 274 ] = 380858207 ;//( 274 e6)!
fact[ 275 ] = 996097969 ;//( 275 e6)!
fact[ 276 ] = 898554793 ;//( 276 e6)!
fact[ 277 ] = 335353644 ;//( 277 e6)!
fact[ 278 ] = 54062950 ;//( 278 e6)!
fact[ 279 ] = 611251733 ;//( 279 e6)!
fact[ 280 ] = 419363534 ;//( 280 e6)!
fact[ 281 ] = 965429853 ;//( 281 e6)!
fact[ 282 ] = 160398980 ;//( 282 e6)!
fact[ 283 ] = 151319402 ;//( 283 e6)!
fact[ 284 ] = 990918946 ;//( 284 e6)!
fact[ 285 ] = 607730875 ;//( 285 e6)!
fact[ 286 ] = 450718279 ;//( 286 e6)!
fact[ 287 ] = 173539388 ;//( 287 e6)!
fact[ 288 ] = 648991369 ;//( 288 e6)!
fact[ 289 ] = 970937898 ;//( 289 e6)!
fact[ 290 ] = 500780548 ;//( 290 e6)!
fact[ 291 ] = 780122909 ;//( 291 e6)!
fact[ 292 ] = 39052406 ;//( 292 e6)!
fact[ 293 ] = 276894233 ;//( 293 e6)!
fact[ 294 ] = 460373282 ;//( 294 e6)!
fact[ 295 ] = 651081062 ;//( 295 e6)!
fact[ 296 ] = 461415770 ;//( 296 e6)!
fact[ 297 ] = 358700839 ;//( 297 e6)!
fact[ 298 ] = 643638805 ;//( 298 e6)!
fact[ 299 ] = 560006119 ;//( 299 e6)!
fact[ 300 ] = 668123525 ;//( 300 e6)!
fact[ 301 ] = 686692315 ;//( 301 e6)!
fact[ 302 ] = 673464765 ;//( 302 e6)!
fact[ 303 ] = 957633609 ;//( 303 e6)!
fact[ 304 ] = 199866123 ;//( 304 e6)!
fact[ 305 ] = 563432246 ;//( 305 e6)!
fact[ 306 ] = 841799766 ;//( 306 e6)!
fact[ 307 ] = 385330357 ;//( 307 e6)!
fact[ 308 ] = 504962686 ;//( 308 e6)!
fact[ 309 ] = 954061253 ;//( 309 e6)!
fact[ 310 ] = 128487469 ;//( 310 e6)!
fact[ 311 ] = 685707545 ;//( 311 e6)!
fact[ 312 ] = 299172297 ;//( 312 e6)!
fact[ 313 ] = 717975101 ;//( 313 e6)!
fact[ 314 ] = 577786541 ;//( 314 e6)!
fact[ 315 ] = 318951960 ;//( 315 e6)!
fact[ 316 ] = 773206631 ;//( 316 e6)!
fact[ 317 ] = 306832604 ;//( 317 e6)!
fact[ 318 ] = 204355779 ;//( 318 e6)!
fact[ 319 ] = 573592106 ;//( 319 e6)!
fact[ 320 ] = 30977140 ;//( 320 e6)!
fact[ 321 ] = 450398100 ;//( 321 e6)!
fact[ 322 ] = 363172638 ;//( 322 e6)!
fact[ 323 ] = 258379324 ;//( 323 e6)!
fact[ 324 ] = 472935553 ;//( 324 e6)!
fact[ 325 ] = 93940075 ;//( 325 e6)!
fact[ 326 ] = 587220627 ;//( 326 e6)!
fact[ 327 ] = 776264326 ;//( 327 e6)!
fact[ 328 ] = 793270300 ;//( 328 e6)!
fact[ 329 ] = 291733496 ;//( 329 e6)!
fact[ 330 ] = 522049725 ;//( 330 e6)!
fact[ 331 ] = 579995261 ;//( 331 e6)!
fact[ 332 ] = 335416359 ;//( 332 e6)!
fact[ 333 ] = 142946099 ;//( 333 e6)!
fact[ 334 ] = 472012302 ;//( 334 e6)!
fact[ 335 ] = 559947225 ;//( 335 e6)!
fact[ 336 ] = 332139472 ;//( 336 e6)!
fact[ 337 ] = 499377092 ;//( 337 e6)!
fact[ 338 ] = 464599136 ;//( 338 e6)!
fact[ 339 ] = 164752359 ;//( 339 e6)!
fact[ 340 ] = 309058615 ;//( 340 e6)!
fact[ 341 ] = 86117128 ;//( 341 e6)!
fact[ 342 ] = 580204973 ;//( 342 e6)!
fact[ 343 ] = 563781682 ;//( 343 e6)!
fact[ 344 ] = 954840109 ;//( 344 e6)!
fact[ 345 ] = 624577416 ;//( 345 e6)!
fact[ 346 ] = 895609896 ;//( 346 e6)!
fact[ 347 ] = 888287558 ;//( 347 e6)!
fact[ 348 ] = 836813268 ;//( 348 e6)!
fact[ 349 ] = 926036911 ;//( 349 e6)!
fact[ 350 ] = 386027524 ;//( 350 e6)!
fact[ 351 ] = 184419613 ;//( 351 e6)!
fact[ 352 ] = 724205533 ;//( 352 e6)!
fact[ 353 ] = 403351886 ;//( 353 e6)!
fact[ 354 ] = 715247054 ;//( 354 e6)!
fact[ 355 ] = 716986954 ;//( 355 e6)!
fact[ 356 ] = 830567832 ;//( 356 e6)!
fact[ 357 ] = 383388563 ;//( 357 e6)!
fact[ 358 ] = 68409439 ;//( 358 e6)!
fact[ 359 ] = 6734065 ;//( 359 e6)!
fact[ 360 ] = 189239124 ;//( 360 e6)!
fact[ 361 ] = 68322490 ;//( 361 e6)!
fact[ 362 ] = 943653305 ;//( 362 e6)!
fact[ 363 ] = 405755338 ;//( 363 e6)!
fact[ 364 ] = 811056092 ;//( 364 e6)!
fact[ 365 ] = 179518046 ;//( 365 e6)!
fact[ 366 ] = 825132993 ;//( 366 e6)!
fact[ 367 ] = 343807435 ;//( 367 e6)!
fact[ 368 ] = 985084650 ;//( 368 e6)!
fact[ 369 ] = 868553027 ;//( 369 e6)!
fact[ 370 ] = 148528617 ;//( 370 e6)!
fact[ 371 ] = 160684257 ;//( 371 e6)!
fact[ 372 ] = 882148737 ;//( 372 e6)!
fact[ 373 ] = 591915968 ;//( 373 e6)!
fact[ 374 ] = 701445829 ;//( 374 e6)!
fact[ 375 ] = 529726489 ;//( 375 e6)!
fact[ 376 ] = 302177126 ;//( 376 e6)!
fact[ 377 ] = 974886682 ;//( 377 e6)!
fact[ 378 ] = 241107368 ;//( 378 e6)!
fact[ 379 ] = 798830099 ;//( 379 e6)!
fact[ 380 ] = 940567523 ;//( 380 e6)!
fact[ 381 ] = 11633075 ;//( 381 e6)!
fact[ 382 ] = 325334066 ;//( 382 e6)!
fact[ 383 ] = 346091869 ;//( 383 e6)!
fact[ 384 ] = 115312728 ;//( 384 e6)!
fact[ 385 ] = 473718967 ;//( 385 e6)!
fact[ 386 ] = 218129285 ;//( 386 e6)!
fact[ 387 ] = 878471898 ;//( 387 e6)!
fact[ 388 ] = 180002392 ;//( 388 e6)!
fact[ 389 ] = 699739374 ;//( 389 e6)!
fact[ 390 ] = 917084264 ;//( 390 e6)!
fact[ 391 ] = 856859395 ;//( 391 e6)!
fact[ 392 ] = 435327356 ;//( 392 e6)!
fact[ 393 ] = 808651347 ;//( 393 e6)!
fact[ 394 ] = 421623838 ;//( 394 e6)!
fact[ 395 ] = 105419548 ;//( 395 e6)!
fact[ 396 ] = 59883031 ;//( 396 e6)!
fact[ 397 ] = 322487421 ;//( 397 e6)!
fact[ 398 ] = 79716267 ;//( 398 e6)!
fact[ 399 ] = 715317963 ;//( 399 e6)!
fact[ 400 ] = 429277690 ;//( 400 e6)!
fact[ 401 ] = 398078032 ;//( 401 e6)!
fact[ 402 ] = 316486674 ;//( 402 e6)!
fact[ 403 ] = 384843585 ;//( 403 e6)!
fact[ 404 ] = 940338439 ;//( 404 e6)!
fact[ 405 ] = 937409008 ;//( 405 e6)!
fact[ 406 ] = 940524812 ;//( 406 e6)!
fact[ 407 ] = 947549662 ;//( 407 e6)!
fact[ 408 ] = 833550543 ;//( 408 e6)!
fact[ 409 ] = 593524514 ;//( 409 e6)!
fact[ 410 ] = 996164327 ;//( 410 e6)!
fact[ 411 ] = 987314628 ;//( 411 e6)!
fact[ 412 ] = 697611981 ;//( 412 e6)!
fact[ 413 ] = 636177449 ;//( 413 e6)!
fact[ 414 ] = 274192146 ;//( 414 e6)!
fact[ 415 ] = 418537348 ;//( 415 e6)!
fact[ 416 ] = 925347821 ;//( 416 e6)!
fact[ 417 ] = 952831975 ;//( 417 e6)!
fact[ 418 ] = 893732627 ;//( 418 e6)!
fact[ 419 ] = 1277567 ;//( 419 e6)!
fact[ 420 ] = 358655417 ;//( 420 e6)!
fact[ 421 ] = 141866945 ;//( 421 e6)!
fact[ 422 ] = 581830879 ;//( 422 e6)!
fact[ 423 ] = 987597705 ;//( 423 e6)!
fact[ 424 ] = 347046911 ;//( 424 e6)!
fact[ 425 ] = 775305697 ;//( 425 e6)!
fact[ 426 ] = 125354499 ;//( 426 e6)!
fact[ 427 ] = 951540811 ;//( 427 e6)!
fact[ 428 ] = 247662371 ;//( 428 e6)!
fact[ 429 ] = 343043237 ;//( 429 e6)!
fact[ 430 ] = 568392357 ;//( 430 e6)!
fact[ 431 ] = 997474832 ;//( 431 e6)!
fact[ 432 ] = 209244402 ;//( 432 e6)!
fact[ 433 ] = 380480118 ;//( 433 e6)!
fact[ 434 ] = 149586983 ;//( 434 e6)!
fact[ 435 ] = 392838702 ;//( 435 e6)!
fact[ 436 ] = 309134554 ;//( 436 e6)!
fact[ 437 ] = 990779998 ;//( 437 e6)!
fact[ 438 ] = 263053337 ;//( 438 e6)!
fact[ 439 ] = 325362513 ;//( 439 e6)!
fact[ 440 ] = 780072518 ;//( 440 e6)!
fact[ 441 ] = 551028176 ;//( 441 e6)!
fact[ 442 ] = 990826116 ;//( 442 e6)!
fact[ 443 ] = 989944961 ;//( 443 e6)!
fact[ 444 ] = 155569943 ;//( 444 e6)!
fact[ 445 ] = 596737944 ;//( 445 e6)!
fact[ 446 ] = 711553356 ;//( 446 e6)!
fact[ 447 ] = 268844715 ;//( 447 e6)!
fact[ 448 ] = 451373308 ;//( 448 e6)!
fact[ 449 ] = 379404150 ;//( 449 e6)!
fact[ 450 ] = 462639908 ;//( 450 e6)!
fact[ 451 ] = 961812918 ;//( 451 e6)!
fact[ 452 ] = 654611901 ;//( 452 e6)!
fact[ 453 ] = 382776490 ;//( 453 e6)!
fact[ 454 ] = 41815820 ;//( 454 e6)!
fact[ 455 ] = 843321396 ;//( 455 e6)!
fact[ 456 ] = 675258797 ;//( 456 e6)!
fact[ 457 ] = 845583555 ;//( 457 e6)!
fact[ 458 ] = 934281721 ;//( 458 e6)!
fact[ 459 ] = 741114145 ;//( 459 e6)!
fact[ 460 ] = 275105629 ;//( 460 e6)!
fact[ 461 ] = 666247477 ;//( 461 e6)!
fact[ 462 ] = 325912072 ;//( 462 e6)!
fact[ 463 ] = 526131620 ;//( 463 e6)!
fact[ 464 ] = 252551589 ;//( 464 e6)!
fact[ 465 ] = 432030917 ;//( 465 e6)!
fact[ 466 ] = 554917439 ;//( 466 e6)!
fact[ 467 ] = 818036959 ;//( 467 e6)!
fact[ 468 ] = 754363835 ;//( 468 e6)!
fact[ 469 ] = 795190182 ;//( 469 e6)!
fact[ 470 ] = 909210595 ;//( 470 e6)!
fact[ 471 ] = 278704903 ;//( 471 e6)!
fact[ 472 ] = 719566487 ;//( 472 e6)!
fact[ 473 ] = 628514947 ;//( 473 e6)!
fact[ 474 ] = 424989675 ;//( 474 e6)!
fact[ 475 ] = 321685608 ;//( 475 e6)!
fact[ 476 ] = 50590510 ;//( 476 e6)!
fact[ 477 ] = 832069712 ;//( 477 e6)!
fact[ 478 ] = 198768464 ;//( 478 e6)!
fact[ 479 ] = 702004730 ;//( 479 e6)!
fact[ 480 ] = 99199382 ;//( 480 e6)!
fact[ 481 ] = 707469729 ;//( 481 e6)!
fact[ 482 ] = 747407118 ;//( 482 e6)!
fact[ 483 ] = 302020341 ;//( 483 e6)!
fact[ 484 ] = 497196934 ;//( 484 e6)!
fact[ 485 ] = 5003231 ;//( 485 e6)!
fact[ 486 ] = 726997875 ;//( 486 e6)!
fact[ 487 ] = 382617671 ;//( 487 e6)!
fact[ 488 ] = 296229203 ;//( 488 e6)!
fact[ 489 ] = 183888367 ;//( 489 e6)!
fact[ 490 ] = 703397904 ;//( 490 e6)!
fact[ 491 ] = 552133875 ;//( 491 e6)!
fact[ 492 ] = 732868367 ;//( 492 e6)!
fact[ 493 ] = 350095207 ;//( 493 e6)!
fact[ 494 ] = 26031303 ;//( 494 e6)!
fact[ 495 ] = 863250534 ;//( 495 e6)!
fact[ 496 ] = 216665960 ;//( 496 e6)!
fact[ 497 ] = 561745549 ;//( 497 e6)!
fact[ 498 ] = 352946234 ;//( 498 e6)!
fact[ 499 ] = 784139777 ;//( 499 e6)!
fact[ 500 ] = 733333339 ;//( 500 e6)!
fact[ 501 ] = 503105966 ;//( 501 e6)!
fact[ 502 ] = 459878625 ;//( 502 e6)!
fact[ 503 ] = 803187381 ;//( 503 e6)!
fact[ 504 ] = 16634739 ;//( 504 e6)!
fact[ 505 ] = 180898306 ;//( 505 e6)!
fact[ 506 ] = 68718097 ;//( 506 e6)!
fact[ 507 ] = 985594252 ;//( 507 e6)!
fact[ 508 ] = 404206040 ;//( 508 e6)!
fact[ 509 ] = 749724532 ;//( 509 e6)!
fact[ 510 ] = 97830135 ;//( 510 e6)!
fact[ 511 ] = 611751357 ;//( 511 e6)!
fact[ 512 ] = 31131935 ;//( 512 e6)!
fact[ 513 ] = 662741752 ;//( 513 e6)!
fact[ 514 ] = 864326453 ;//( 514 e6)!
fact[ 515 ] = 864869025 ;//( 515 e6)!
fact[ 516 ] = 167831173 ;//( 516 e6)!
fact[ 517 ] = 559214642 ;//( 517 e6)!
fact[ 518 ] = 718498895 ;//( 518 e6)!
fact[ 519 ] = 91352335 ;//( 519 e6)!
fact[ 520 ] = 608823837 ;//( 520 e6)!
fact[ 521 ] = 473379392 ;//( 521 e6)!
fact[ 522 ] = 385388084 ;//( 522 e6)!
fact[ 523 ] = 152267158 ;//( 523 e6)!
fact[ 524 ] = 681756977 ;//( 524 e6)!
fact[ 525 ] = 46819124 ;//( 525 e6)!
fact[ 526 ] = 313132653 ;//( 526 e6)!
fact[ 527 ] = 56547945 ;//( 527 e6)!
fact[ 528 ] = 442795120 ;//( 528 e6)!
fact[ 529 ] = 796616594 ;//( 529 e6)!
fact[ 530 ] = 256141983 ;//( 530 e6)!
fact[ 531 ] = 152028387 ;//( 531 e6)!
fact[ 532 ] = 636578562 ;//( 532 e6)!
fact[ 533 ] = 385377759 ;//( 533 e6)!
fact[ 534 ] = 553033642 ;//( 534 e6)!
fact[ 535 ] = 491415383 ;//( 535 e6)!
fact[ 536 ] = 919273670 ;//( 536 e6)!
fact[ 537 ] = 996049638 ;//( 537 e6)!
fact[ 538 ] = 326686486 ;//( 538 e6)!
fact[ 539 ] = 160150665 ;//( 539 e6)!
fact[ 540 ] = 141827977 ;//( 540 e6)!
fact[ 541 ] = 540818053 ;//( 541 e6)!
fact[ 542 ] = 693305776 ;//( 542 e6)!
fact[ 543 ] = 593938674 ;//( 543 e6)!
fact[ 544 ] = 186576440 ;//( 544 e6)!
fact[ 545 ] = 688809790 ;//( 545 e6)!
fact[ 546 ] = 565456578 ;//( 546 e6)!
fact[ 547 ] = 749296077 ;//( 547 e6)!
fact[ 548 ] = 519397500 ;//( 548 e6)!
fact[ 549 ] = 551096742 ;//( 549 e6)!
fact[ 550 ] = 696628828 ;//( 550 e6)!
fact[ 551 ] = 775025061 ;//( 551 e6)!
fact[ 552 ] = 370732451 ;//( 552 e6)!
fact[ 553 ] = 164246193 ;//( 553 e6)!
fact[ 554 ] = 915265013 ;//( 554 e6)!
fact[ 555 ] = 457469634 ;//( 555 e6)!
fact[ 556 ] = 923043932 ;//( 556 e6)!
fact[ 557 ] = 912368644 ;//( 557 e6)!
fact[ 558 ] = 777901604 ;//( 558 e6)!
fact[ 559 ] = 464118005 ;//( 559 e6)!
fact[ 560 ] = 637939935 ;//( 560 e6)!
fact[ 561 ] = 956856710 ;//( 561 e6)!
fact[ 562 ] = 490676632 ;//( 562 e6)!
fact[ 563 ] = 453019482 ;//( 563 e6)!
fact[ 564 ] = 462528877 ;//( 564 e6)!
fact[ 565 ] = 502297454 ;//( 565 e6)!
fact[ 566 ] = 798895521 ;//( 566 e6)!
fact[ 567 ] = 100498586 ;//( 567 e6)!
fact[ 568 ] = 699767918 ;//( 568 e6)!
fact[ 569 ] = 849974789 ;//( 569 e6)!
fact[ 570 ] = 811575797 ;//( 570 e6)!
fact[ 571 ] = 438952959 ;//( 571 e6)!
fact[ 572 ] = 606870929 ;//( 572 e6)!
fact[ 573 ] = 907720182 ;//( 573 e6)!
fact[ 574 ] = 179111720 ;//( 574 e6)!
fact[ 575 ] = 48053248 ;//( 575 e6)!
fact[ 576 ] = 508038818 ;//( 576 e6)!
fact[ 577 ] = 811944661 ;//( 577 e6)!
fact[ 578 ] = 752550134 ;//( 578 e6)!
fact[ 579 ] = 401382061 ;//( 579 e6)!
fact[ 580 ] = 848924691 ;//( 580 e6)!
fact[ 581 ] = 764368449 ;//( 581 e6)!
fact[ 582 ] = 34629406 ;//( 582 e6)!
fact[ 583 ] = 529840945 ;//( 583 e6)!
fact[ 584 ] = 435904287 ;//( 584 e6)!
fact[ 585 ] = 26011548 ;//( 585 e6)!
fact[ 586 ] = 208184231 ;//( 586 e6)!
fact[ 587 ] = 446477394 ;//( 587 e6)!
fact[ 588 ] = 206330671 ;//( 588 e6)!
fact[ 589 ] = 366033520 ;//( 589 e6)!
fact[ 590 ] = 131772368 ;//( 590 e6)!
fact[ 591 ] = 185646898 ;//( 591 e6)!
fact[ 592 ] = 648711554 ;//( 592 e6)!
fact[ 593 ] = 472759660 ;//( 593 e6)!
fact[ 594 ] = 523696723 ;//( 594 e6)!
fact[ 595 ] = 271198437 ;//( 595 e6)!
fact[ 596 ] = 25058942 ;//( 596 e6)!
fact[ 597 ] = 859369491 ;//( 597 e6)!
fact[ 598 ] = 817928963 ;//( 598 e6)!
fact[ 599 ] = 330711333 ;//( 599 e6)!
fact[ 600 ] = 724464507 ;//( 600 e6)!
fact[ 601 ] = 437605233 ;//( 601 e6)!
fact[ 602 ] = 701453022 ;//( 602 e6)!
fact[ 603 ] = 626663115 ;//( 603 e6)!
fact[ 604 ] = 281230685 ;//( 604 e6)!
fact[ 605 ] = 510650790 ;//( 605 e6)!
fact[ 606 ] = 596949867 ;//( 606 e6)!
fact[ 607 ] = 295726547 ;//( 607 e6)!
fact[ 608 ] = 303076380 ;//( 608 e6)!
fact[ 609 ] = 465070856 ;//( 609 e6)!
fact[ 610 ] = 272814771 ;//( 610 e6)!
fact[ 611 ] = 538771609 ;//( 611 e6)!
fact[ 612 ] = 48824684 ;//( 612 e6)!
fact[ 613 ] = 951279549 ;//( 613 e6)!
fact[ 614 ] = 939889684 ;//( 614 e6)!
fact[ 615 ] = 564188856 ;//( 615 e6)!
fact[ 616 ] = 48527183 ;//( 616 e6)!
fact[ 617 ] = 201307702 ;//( 617 e6)!
fact[ 618 ] = 484458461 ;//( 618 e6)!
fact[ 619 ] = 861754542 ;//( 619 e6)!
fact[ 620 ] = 326159309 ;//( 620 e6)!
fact[ 621 ] = 181594759 ;//( 621 e6)!
fact[ 622 ] = 668422905 ;//( 622 e6)!
fact[ 623 ] = 286273596 ;//( 623 e6)!
fact[ 624 ] = 965656187 ;//( 624 e6)!
fact[ 625 ] = 44135644 ;//( 625 e6)!
fact[ 626 ] = 359960756 ;//( 626 e6)!
fact[ 627 ] = 936229527 ;//( 627 e6)!
fact[ 628 ] = 407934361 ;//( 628 e6)!
fact[ 629 ] = 267193060 ;//( 629 e6)!
fact[ 630 ] = 456152084 ;//( 630 e6)!
fact[ 631 ] = 459116722 ;//( 631 e6)!
fact[ 632 ] = 124804049 ;//( 632 e6)!
fact[ 633 ] = 262322489 ;//( 633 e6)!
fact[ 634 ] = 920251227 ;//( 634 e6)!
fact[ 635 ] = 816929577 ;//( 635 e6)!
fact[ 636 ] = 483924582 ;//( 636 e6)!
fact[ 637 ] = 151834896 ;//( 637 e6)!
fact[ 638 ] = 167087470 ;//( 638 e6)!
fact[ 639 ] = 490222511 ;//( 639 e6)!
fact[ 640 ] = 903466878 ;//( 640 e6)!
fact[ 641 ] = 361583925 ;//( 641 e6)!
fact[ 642 ] = 368114731 ;//( 642 e6)!
fact[ 643 ] = 339383292 ;//( 643 e6)!
fact[ 644 ] = 388728584 ;//( 644 e6)!
fact[ 645 ] = 218107212 ;//( 645 e6)!
fact[ 646 ] = 249153339 ;//( 646 e6)!
fact[ 647 ] = 909458706 ;//( 647 e6)!
fact[ 648 ] = 322908524 ;//( 648 e6)!
fact[ 649 ] = 202649964 ;//( 649 e6)!
fact[ 650 ] = 92255682 ;//( 650 e6)!
fact[ 651 ] = 573074791 ;//( 651 e6)!
fact[ 652 ] = 15570863 ;//( 652 e6)!
fact[ 653 ] = 94331513 ;//( 653 e6)!
fact[ 654 ] = 744158074 ;//( 654 e6)!
fact[ 655 ] = 196345098 ;//( 655 e6)!
fact[ 656 ] = 334326205 ;//( 656 e6)!
fact[ 657 ] = 9416035 ;//( 657 e6)!
fact[ 658 ] = 98349682 ;//( 658 e6)!
fact[ 659 ] = 882121662 ;//( 659 e6)!
fact[ 660 ] = 769795511 ;//( 660 e6)!
fact[ 661 ] = 231988936 ;//( 661 e6)!
fact[ 662 ] = 888146074 ;//( 662 e6)!
fact[ 663 ] = 137603545 ;//( 663 e6)!
fact[ 664 ] = 582627184 ;//( 664 e6)!
fact[ 665 ] = 407518072 ;//( 665 e6)!
fact[ 666 ] = 919419361 ;//( 666 e6)!
fact[ 667 ] = 909433461 ;//( 667 e6)!
fact[ 668 ] = 986708498 ;//( 668 e6)!
fact[ 669 ] = 310317874 ;//( 669 e6)!
fact[ 670 ] = 373745190 ;//( 670 e6)!
fact[ 671 ] = 263645931 ;//( 671 e6)!
fact[ 672 ] = 256853930 ;//( 672 e6)!
fact[ 673 ] = 876379959 ;//( 673 e6)!
fact[ 674 ] = 702823274 ;//( 674 e6)!
fact[ 675 ] = 147050765 ;//( 675 e6)!
fact[ 676 ] = 308186532 ;//( 676 e6)!
fact[ 677 ] = 175504139 ;//( 677 e6)!
fact[ 678 ] = 180350107 ;//( 678 e6)!
fact[ 679 ] = 797736554 ;//( 679 e6)!
fact[ 680 ] = 606241871 ;//( 680 e6)!
fact[ 681 ] = 384547635 ;//( 681 e6)!
fact[ 682 ] = 273712630 ;//( 682 e6)!
fact[ 683 ] = 586444655 ;//( 683 e6)!
fact[ 684 ] = 682189174 ;//( 684 e6)!
fact[ 685 ] = 666493603 ;//( 685 e6)!
fact[ 686 ] = 946867127 ;//( 686 e6)!
fact[ 687 ] = 819114541 ;//( 687 e6)!
fact[ 688 ] = 502371023 ;//( 688 e6)!
fact[ 689 ] = 261970285 ;//( 689 e6)!
fact[ 690 ] = 825871994 ;//( 690 e6)!
fact[ 691 ] = 126925175 ;//( 691 e6)!
fact[ 692 ] = 701506133 ;//( 692 e6)!
fact[ 693 ] = 314738056 ;//( 693 e6)!
fact[ 694 ] = 341779962 ;//( 694 e6)!
fact[ 695 ] = 561011609 ;//( 695 e6)!
fact[ 696 ] = 815463367 ;//( 696 e6)!
fact[ 697 ] = 46765164 ;//( 697 e6)!
fact[ 698 ] = 49187570 ;//( 698 e6)!
fact[ 699 ] = 188054995 ;//( 699 e6)!
fact[ 700 ] = 957939114 ;//( 700 e6)!
fact[ 701 ] = 64814326 ;//( 701 e6)!
fact[ 702 ] = 933376898 ;//( 702 e6)!
fact[ 703 ] = 329837066 ;//( 703 e6)!
fact[ 704 ] = 338121343 ;//( 704 e6)!
fact[ 705 ] = 765215899 ;//( 705 e6)!
fact[ 706 ] = 869630152 ;//( 706 e6)!
fact[ 707 ] = 978119194 ;//( 707 e6)!
fact[ 708 ] = 632627667 ;//( 708 e6)!
fact[ 709 ] = 975266085 ;//( 709 e6)!
fact[ 710 ] = 435887178 ;//( 710 e6)!
fact[ 711 ] = 282092463 ;//( 711 e6)!
fact[ 712 ] = 129621197 ;//( 712 e6)!
fact[ 713 ] = 758245605 ;//( 713 e6)!
fact[ 714 ] = 827722926 ;//( 714 e6)!
fact[ 715 ] = 201339230 ;//( 715 e6)!
fact[ 716 ] = 918513230 ;//( 716 e6)!
fact[ 717 ] = 322096036 ;//( 717 e6)!
fact[ 718 ] = 547838438 ;//( 718 e6)!
fact[ 719 ] = 985546115 ;//( 719 e6)!
fact[ 720 ] = 852304035 ;//( 720 e6)!
fact[ 721 ] = 593090119 ;//( 721 e6)!
fact[ 722 ] = 689189630 ;//( 722 e6)!
fact[ 723 ] = 555842733 ;//( 723 e6)!
fact[ 724 ] = 567033437 ;//( 724 e6)!
fact[ 725 ] = 469928208 ;//( 725 e6)!
fact[ 726 ] = 212842957 ;//( 726 e6)!
fact[ 727 ] = 117842065 ;//( 727 e6)!
fact[ 728 ] = 404149413 ;//( 728 e6)!
fact[ 729 ] = 155133422 ;//( 729 e6)!
fact[ 730 ] = 663307737 ;//( 730 e6)!
fact[ 731 ] = 208761293 ;//( 731 e6)!
fact[ 732 ] = 206282795 ;//( 732 e6)!
fact[ 733 ] = 717946122 ;//( 733 e6)!
fact[ 734 ] = 488906585 ;//( 734 e6)!
fact[ 735 ] = 414236650 ;//( 735 e6)!
fact[ 736 ] = 280700600 ;//( 736 e6)!
fact[ 737 ] = 962670136 ;//( 737 e6)!
fact[ 738 ] = 534279149 ;//( 738 e6)!
fact[ 739 ] = 214569244 ;//( 739 e6)!
fact[ 740 ] = 375297772 ;//( 740 e6)!
fact[ 741 ] = 811053196 ;//( 741 e6)!
fact[ 742 ] = 922377372 ;//( 742 e6)!
fact[ 743 ] = 289594327 ;//( 743 e6)!
fact[ 744 ] = 219932130 ;//( 744 e6)!
fact[ 745 ] = 211487466 ;//( 745 e6)!
fact[ 746 ] = 701050258 ;//( 746 e6)!
fact[ 747 ] = 398782410 ;//( 747 e6)!
fact[ 748 ] = 863002719 ;//( 748 e6)!
fact[ 749 ] = 27236531 ;//( 749 e6)!
fact[ 750 ] = 217598709 ;//( 750 e6)!
fact[ 751 ] = 375472836 ;//( 751 e6)!
fact[ 752 ] = 810551911 ;//( 752 e6)!
fact[ 753 ] = 178598958 ;//( 753 e6)!
fact[ 754 ] = 247844667 ;//( 754 e6)!
fact[ 755 ] = 676526196 ;//( 755 e6)!
fact[ 756 ] = 812283640 ;//( 756 e6)!
fact[ 757 ] = 863066876 ;//( 757 e6)!
fact[ 758 ] = 857241854 ;//( 758 e6)!
fact[ 759 ] = 113917835 ;//( 759 e6)!
fact[ 760 ] = 624148346 ;//( 760 e6)!
fact[ 761 ] = 726089763 ;//( 761 e6)!
fact[ 762 ] = 564827277 ;//( 762 e6)!
fact[ 763 ] = 826300950 ;//( 763 e6)!
fact[ 764 ] = 478982047 ;//( 764 e6)!
fact[ 765 ] = 439411911 ;//( 765 e6)!
fact[ 766 ] = 454039189 ;//( 766 e6)!
fact[ 767 ] = 633292726 ;//( 767 e6)!
fact[ 768 ] = 48562889 ;//( 768 e6)!
fact[ 769 ] = 802100365 ;//( 769 e6)!
fact[ 770 ] = 671734977 ;//( 770 e6)!
fact[ 771 ] = 945204804 ;//( 771 e6)!
fact[ 772 ] = 508831870 ;//( 772 e6)!
fact[ 773 ] = 398781902 ;//( 773 e6)!
fact[ 774 ] = 897162044 ;//( 774 e6)!
fact[ 775 ] = 644050694 ;//( 775 e6)!
fact[ 776 ] = 892168027 ;//( 776 e6)!
fact[ 777 ] = 828883117 ;//( 777 e6)!
fact[ 778 ] = 277714559 ;//( 778 e6)!
fact[ 779 ] = 713448377 ;//( 779 e6)!
fact[ 780 ] = 624500515 ;//( 780 e6)!
fact[ 781 ] = 590098114 ;//( 781 e6)!
fact[ 782 ] = 808691930 ;//( 782 e6)!
fact[ 783 ] = 514359662 ;//( 783 e6)!
fact[ 784 ] = 895205045 ;//( 784 e6)!
fact[ 785 ] = 715264908 ;//( 785 e6)!
fact[ 786 ] = 628829100 ;//( 786 e6)!
fact[ 787 ] = 484492064 ;//( 787 e6)!
fact[ 788 ] = 919717789 ;//( 788 e6)!
fact[ 789 ] = 513196123 ;//( 789 e6)!
fact[ 790 ] = 748510389 ;//( 790 e6)!
fact[ 791 ] = 403652653 ;//( 791 e6)!
fact[ 792 ] = 574455974 ;//( 792 e6)!
fact[ 793 ] = 77123823 ;//( 793 e6)!
fact[ 794 ] = 172096141 ;//( 794 e6)!
fact[ 795 ] = 819801784 ;//( 795 e6)!
fact[ 796 ] = 581418893 ;//( 796 e6)!
fact[ 797 ] = 15655126 ;//( 797 e6)!
fact[ 798 ] = 15391652 ;//( 798 e6)!
fact[ 799 ] = 875641535 ;//( 799 e6)!
fact[ 800 ] = 203191898 ;//( 800 e6)!
fact[ 801 ] = 264582598 ;//( 801 e6)!
fact[ 802 ] = 880691101 ;//( 802 e6)!
fact[ 803 ] = 907800444 ;//( 803 e6)!
fact[ 804 ] = 986598821 ;//( 804 e6)!
fact[ 805 ] = 340030191 ;//( 805 e6)!
fact[ 806 ] = 264688936 ;//( 806 e6)!
fact[ 807 ] = 369832433 ;//( 807 e6)!
fact[ 808 ] = 785804644 ;//( 808 e6)!
fact[ 809 ] = 842065079 ;//( 809 e6)!
fact[ 810 ] = 423951674 ;//( 810 e6)!
fact[ 811 ] = 663560047 ;//( 811 e6)!
fact[ 812 ] = 696623384 ;//( 812 e6)!
fact[ 813 ] = 496709826 ;//( 813 e6)!
fact[ 814 ] = 161960209 ;//( 814 e6)!
fact[ 815 ] = 331910086 ;//( 815 e6)!
fact[ 816 ] = 541120825 ;//( 816 e6)!
fact[ 817 ] = 951524114 ;//( 817 e6)!
fact[ 818 ] = 841656666 ;//( 818 e6)!
fact[ 819 ] = 162683802 ;//( 819 e6)!
fact[ 820 ] = 629786193 ;//( 820 e6)!
fact[ 821 ] = 190395535 ;//( 821 e6)!
fact[ 822 ] = 269571439 ;//( 822 e6)!
fact[ 823 ] = 832671304 ;//( 823 e6)!
fact[ 824 ] = 76770272 ;//( 824 e6)!
fact[ 825 ] = 341080135 ;//( 825 e6)!
fact[ 826 ] = 421943723 ;//( 826 e6)!
fact[ 827 ] = 494210290 ;//( 827 e6)!
fact[ 828 ] = 751040886 ;//( 828 e6)!
fact[ 829 ] = 317076664 ;//( 829 e6)!
fact[ 830 ] = 672850561 ;//( 830 e6)!
fact[ 831 ] = 72482816 ;//( 831 e6)!
fact[ 832 ] = 493689107 ;//( 832 e6)!
fact[ 833 ] = 135625240 ;//( 833 e6)!
fact[ 834 ] = 100228913 ;//( 834 e6)!
fact[ 835 ] = 684748812 ;//( 835 e6)!
fact[ 836 ] = 639655136 ;//( 836 e6)!
fact[ 837 ] = 906233141 ;//( 837 e6)!
fact[ 838 ] = 929893103 ;//( 838 e6)!
fact[ 839 ] = 277813439 ;//( 839 e6)!
fact[ 840 ] = 814362881 ;//( 840 e6)!
fact[ 841 ] = 562608724 ;//( 841 e6)!
fact[ 842 ] = 406024012 ;//( 842 e6)!
fact[ 843 ] = 885537778 ;//( 843 e6)!
fact[ 844 ] = 10065330 ;//( 844 e6)!
fact[ 845 ] = 60625018 ;//( 845 e6)!
fact[ 846 ] = 983737173 ;//( 846 e6)!
fact[ 847 ] = 60517502 ;//( 847 e6)!
fact[ 848 ] = 551060742 ;//( 848 e6)!
fact[ 849 ] = 804930491 ;//( 849 e6)!
fact[ 850 ] = 823845496 ;//( 850 e6)!
fact[ 851 ] = 727416538 ;//( 851 e6)!
fact[ 852 ] = 946421040 ;//( 852 e6)!
fact[ 853 ] = 678171399 ;//( 853 e6)!
fact[ 854 ] = 842203531 ;//( 854 e6)!
fact[ 855 ] = 175638827 ;//( 855 e6)!
fact[ 856 ] = 894247956 ;//( 856 e6)!
fact[ 857 ] = 538609927 ;//( 857 e6)!
fact[ 858 ] = 885362182 ;//( 858 e6)!
fact[ 859 ] = 946464959 ;//( 859 e6)!
fact[ 860 ] = 116667533 ;//( 860 e6)!
fact[ 861 ] = 749816133 ;//( 861 e6)!
fact[ 862 ] = 241427979 ;//( 862 e6)!
fact[ 863 ] = 871117927 ;//( 863 e6)!
fact[ 864 ] = 281804989 ;//( 864 e6)!
fact[ 865 ] = 163928347 ;//( 865 e6)!
fact[ 866 ] = 563796647 ;//( 866 e6)!
fact[ 867 ] = 640266394 ;//( 867 e6)!
fact[ 868 ] = 774625892 ;//( 868 e6)!
fact[ 869 ] = 59342705 ;//( 869 e6)!
fact[ 870 ] = 256473217 ;//( 870 e6)!
fact[ 871 ] = 674115061 ;//( 871 e6)!
fact[ 872 ] = 918860977 ;//( 872 e6)!
fact[ 873 ] = 322633051 ;//( 873 e6)!
fact[ 874 ] = 753513874 ;//( 874 e6)!
fact[ 875 ] = 393556719 ;//( 875 e6)!
fact[ 876 ] = 304644842 ;//( 876 e6)!
fact[ 877 ] = 767372800 ;//( 877 e6)!
fact[ 878 ] = 161362528 ;//( 878 e6)!
fact[ 879 ] = 754787150 ;//( 879 e6)!
fact[ 880 ] = 627655552 ;//( 880 e6)!
fact[ 881 ] = 677395736 ;//( 881 e6)!
fact[ 882 ] = 799289297 ;//( 882 e6)!
fact[ 883 ] = 846650652 ;//( 883 e6)!
fact[ 884 ] = 816701166 ;//( 884 e6)!
fact[ 885 ] = 687265514 ;//( 885 e6)!
fact[ 886 ] = 787113234 ;//( 886 e6)!
fact[ 887 ] = 358757251 ;//( 887 e6)!
fact[ 888 ] = 701220427 ;//( 888 e6)!
fact[ 889 ] = 607715125 ;//( 889 e6)!
fact[ 890 ] = 245795606 ;//( 890 e6)!
fact[ 891 ] = 600624983 ;//( 891 e6)!
fact[ 892 ] = 10475577 ;//( 892 e6)!
fact[ 893 ] = 728620948 ;//( 893 e6)!
fact[ 894 ] = 759404319 ;//( 894 e6)!
fact[ 895 ] = 36292292 ;//( 895 e6)!
fact[ 896 ] = 491466901 ;//( 896 e6)!
fact[ 897 ] = 22556579 ;//( 897 e6)!
fact[ 898 ] = 114495791 ;//( 898 e6)!
fact[ 899 ] = 647630109 ;//( 899 e6)!
fact[ 900 ] = 586445753 ;//( 900 e6)!
fact[ 901 ] = 482254337 ;//( 901 e6)!
fact[ 902 ] = 718623833 ;//( 902 e6)!
fact[ 903 ] = 763514207 ;//( 903 e6)!
fact[ 904 ] = 66547751 ;//( 904 e6)!
fact[ 905 ] = 953634340 ;//( 905 e6)!
fact[ 906 ] = 351472920 ;//( 906 e6)!
fact[ 907 ] = 308474522 ;//( 907 e6)!
fact[ 908 ] = 494166907 ;//( 908 e6)!
fact[ 909 ] = 634359666 ;//( 909 e6)!
fact[ 910 ] = 172114298 ;//( 910 e6)!
fact[ 911 ] = 865440961 ;//( 911 e6)!
fact[ 912 ] = 364380585 ;//( 912 e6)!
fact[ 913 ] = 921648059 ;//( 913 e6)!
fact[ 914 ] = 965683742 ;//( 914 e6)!
fact[ 915 ] = 260466949 ;//( 915 e6)!
fact[ 916 ] = 117483873 ;//( 916 e6)!
fact[ 917 ] = 962540888 ;//( 917 e6)!
fact[ 918 ] = 237120480 ;//( 918 e6)!
fact[ 919 ] = 620531822 ;//( 919 e6)!
fact[ 920 ] = 193781724 ;//( 920 e6)!
fact[ 921 ] = 213092254 ;//( 921 e6)!
fact[ 922 ] = 107141741 ;//( 922 e6)!
fact[ 923 ] = 602742426 ;//( 923 e6)!
fact[ 924 ] = 793307102 ;//( 924 e6)!
fact[ 925 ] = 756154604 ;//( 925 e6)!
fact[ 926 ] = 236455213 ;//( 926 e6)!
fact[ 927 ] = 362928234 ;//( 927 e6)!
fact[ 928 ] = 14162538 ;//( 928 e6)!
fact[ 929 ] = 753042874 ;//( 929 e6)!
fact[ 930 ] = 778983779 ;//( 930 e6)!
fact[ 931 ] = 25977209 ;//( 931 e6)!
fact[ 932 ] = 49389215 ;//( 932 e6)!
fact[ 933 ] = 698308420 ;//( 933 e6)!
fact[ 934 ] = 859637374 ;//( 934 e6)!
fact[ 935 ] = 49031023 ;//( 935 e6)!
fact[ 936 ] = 713258160 ;//( 936 e6)!
fact[ 937 ] = 737331920 ;//( 937 e6)!
fact[ 938 ] = 923333660 ;//( 938 e6)!
fact[ 939 ] = 804861409 ;//( 939 e6)!
fact[ 940 ] = 83868974 ;//( 940 e6)!
fact[ 941 ] = 682873215 ;//( 941 e6)!
fact[ 942 ] = 217298111 ;//( 942 e6)!
fact[ 943 ] = 883278906 ;//( 943 e6)!
fact[ 944 ] = 176966527 ;//( 944 e6)!
fact[ 945 ] = 954913 ;//( 945 e6)!
fact[ 946 ] = 105359006 ;//( 946 e6)!
fact[ 947 ] = 390019735 ;//( 947 e6)!
fact[ 948 ] = 10430738 ;//( 948 e6)!
fact[ 949 ] = 706334445 ;//( 949 e6)!
fact[ 950 ] = 315103615 ;//( 950 e6)!
fact[ 951 ] = 567473423 ;//( 951 e6)!
fact[ 952 ] = 708233401 ;//( 952 e6)!
fact[ 953 ] = 48160594 ;//( 953 e6)!
fact[ 954 ] = 946149627 ;//( 954 e6)!
fact[ 955 ] = 346966053 ;//( 955 e6)!
fact[ 956 ] = 281329488 ;//( 956 e6)!
fact[ 957 ] = 462880311 ;//( 957 e6)!
fact[ 958 ] = 31503476 ;//( 958 e6)!
fact[ 959 ] = 185438078 ;//( 959 e6)!
fact[ 960 ] = 965785236 ;//( 960 e6)!
fact[ 961 ] = 992656683 ;//( 961 e6)!
fact[ 962 ] = 916291845 ;//( 962 e6)!
fact[ 963 ] = 881482632 ;//( 963 e6)!
fact[ 964 ] = 899946391 ;//( 964 e6)!
fact[ 965 ] = 321900901 ;//( 965 e6)!
fact[ 966 ] = 512634493 ;//( 966 e6)!
fact[ 967 ] = 303338827 ;//( 967 e6)!
fact[ 968 ] = 121000338 ;//( 968 e6)!
fact[ 969 ] = 967284733 ;//( 969 e6)!
fact[ 970 ] = 492741665 ;//( 970 e6)!
fact[ 971 ] = 152233223 ;//( 971 e6)!
fact[ 972 ] = 165393390 ;//( 972 e6)!
fact[ 973 ] = 680128316 ;//( 973 e6)!
fact[ 974 ] = 917041303 ;//( 974 e6)!
fact[ 975 ] = 532702135 ;//( 975 e6)!
fact[ 976 ] = 741626808 ;//( 976 e6)!
fact[ 977 ] = 496442755 ;//( 977 e6)!
fact[ 978 ] = 536841269 ;//( 978 e6)!
fact[ 979 ] = 131384366 ;//( 979 e6)!
fact[ 980 ] = 377329025 ;//( 980 e6)!
fact[ 981 ] = 301196854 ;//( 981 e6)!
fact[ 982 ] = 859917803 ;//( 982 e6)!
fact[ 983 ] = 676511002 ;//( 983 e6)!
fact[ 984 ] = 373451745 ;//( 984 e6)!
fact[ 985 ] = 847645126 ;//( 985 e6)!
fact[ 986 ] = 823495900 ;//( 986 e6)!
fact[ 987 ] = 576368335 ;//( 987 e6)!
fact[ 988 ] = 73146164 ;//( 988 e6)!
fact[ 989 ] = 954958912 ;//( 989 e6)!
fact[ 990 ] = 847549272 ;//( 990 e6)!
fact[ 991 ] = 241289571 ;//( 991 e6)!
fact[ 992 ] = 646654592 ;//( 992 e6)!
fact[ 993 ] = 216046746 ;//( 993 e6)!
fact[ 994 ] = 205951465 ;//( 994 e6)!
fact[ 995 ] = 3258987 ;//( 995 e6)!
fact[ 996 ] = 780882948 ;//( 996 e6)!
fact[ 997 ] = 822439091 ;//( 997 e6)!
fact[ 998 ] = 598245292 ;//( 998 e6)!
fact[ 999 ] = 869544707 ;//( 999 e6)!
fact[ 1000 ] = 698611116 ;//( 1000 e6)!
}
//O(10 ^ 6)
ll mod_fact( ll n, ll p ){
precalc();
ll ret,a = n % MOD,b = a / 100000;
ll i = 0;
if( n >= MOD ){
return 0;
}else if( n == MOD - 1 ){
return MOD - 1;
}
while( i < 10000 ){
if( i <= b && b < i + 10 ){
i/=10;b/=10;
ret = fact[i];
REP( j, i * 1000000 + 1, a + 1 ){
ret = ret * j % MOD;
}
}
i+=10;
}
return ret % MOD;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
LIN(n);
puta( mod_fact( n, MOD ));
return 0;
}