#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;
}