#include using namespace std; typedef signed long long ll; #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define FORR2(x,y,arr) for(auto& [x,y]:arr) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) template bool chmax(T &a, const T &b) { if(a bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;} //------------------------------------------------------- const ll mo=1000000007; ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } ll fact(ll v) { static int data[][2]= { {0,1}, {10000000,682498929}, {20000000,491101308}, {30000000,76479948}, {40000000,723816384}, {50000000,67347853}, {60000000,27368307}, {70000000,625544428}, {80000000,199888908}, {90000000,888050723}, {100000000,927880474}, {110000000,281863274}, {120000000,661224977}, {130000000,623534362}, {140000000,970055531}, {150000000,261384175}, {160000000,195888993}, {170000000,66404266}, {180000000,547665832}, {190000000,109838563}, {200000000,933245637}, {210000000,724691727}, {220000000,368925948}, {230000000,268838846}, {240000000,136026497}, {250000000,112390913}, {260000000,135498044}, {270000000,217544623}, {280000000,419363534}, {290000000,500780548}, {300000000,668123525}, {310000000,128487469}, {320000000,30977140}, {330000000,522049725}, {340000000,309058615}, {350000000,386027524}, {360000000,189239124}, {370000000,148528617}, {380000000,940567523}, {390000000,917084264}, {400000000,429277690}, {410000000,996164327}, {420000000,358655417}, {430000000,568392357}, {440000000,780072518}, {450000000,462639908}, {460000000,275105629}, {470000000,909210595}, {480000000,99199382}, {490000000,703397904}, {500000000,733333339}, {510000000,97830135}, {520000000,608823837}, {530000000,256141983}, {540000000,141827977}, {550000000,696628828}, {560000000,637939935}, {570000000,811575797}, {580000000,848924691}, {590000000,131772368}, {600000000,724464507}, {610000000,272814771}, {620000000,326159309}, {630000000,456152084}, {640000000,903466878}, {650000000,92255682}, {660000000,769795511}, {670000000,373745190}, {680000000,606241871}, {690000000,825871994}, {700000000,957939114}, {710000000,435887178}, {720000000,852304035}, {730000000,663307737}, {740000000,375297772}, {750000000,217598709}, {760000000,624148346}, {770000000,671734977}, {780000000,624500515}, {790000000,748510389}, {800000000,203191898}, {810000000,423951674}, {820000000,629786193}, {830000000,672850561}, {840000000,814362881}, {850000000,823845496}, {860000000,116667533}, {870000000,256473217}, {880000000,627655552}, {890000000,245795606}, {900000000,586445753}, {910000000,172114298}, {920000000,193781724}, {930000000,778983779}, {940000000,83868974}, {950000000,315103615}, {960000000,965785236}, {970000000,492741665}, {980000000,377329025}, {990000000,847549272}, {1000000000,698611116}, {1010000000,0}, }; if(v>=mo) return 0; int cur=v/10000000*10000000; ll ret=data[cur/10000000][1]; for(int i=cur+1;i<=v;i++) ret=ret*i%mo; return ret; } void solve() { int i,j,k,l,r,x,y; string s; int N; cin>>N; if(N%2) { cout<<0<