C11CAL.cpp

/*
 * C11CAL.CPP
 *
 *  Created on: Nov 26, 2011
 *      Author: vanhoa
 */
#include<stdlib.h>
#include<stdio.h>

template<typename T, int MOD> T nm(T x){
	return ((x%MOD)+MOD)%MOD;
}
template<typename T, int MOD>
void exgcd(T a, T b, T& x, T& y){
	if(!a || !b) x=y=1;
	else{
		T xx;
		exgcd<T,MOD>(b,a%b,xx,y);
		//1==b*x+(a%b)*y
		// ==b*x+a*y-b*a/b*y
		// ==a*y+b*(x-a/b*y)
		x=y;
		y=nm<T,MOD>(xx-nm<T,MOD>(a/b*y));
	}
}

template<typename T, int MOD>
class IntMod{
	public:
		T value;
		IntMod(){}
		IntMod(T _){set(_);}
		inline T nm(T _){return ((_%MOD)+MOD)%MOD;}
		inline void set(T a){value=nm(a);}
		inline void operator=(T a){set(a);}
		inline void operator=(IntMod<T,MOD> a){set(a.value);}
		inline void operator*=(T a){set(value*a);}
		inline IntMod<T,MOD> sqr(){
			return IntMod(value*value);
		}
		inline IntMod<T,MOD> operator+(T x){
			return IntMod(value+x);
		}
		inline IntMod<T,MOD> operator+(IntMod<T,MOD> x){
			return IntMod(value+x.value);
		}
		inline IntMod<T,MOD> operator-(T x){
			return IntMod(value-x);
		}
		inline IntMod<T,MOD> operator-(IntMod<T,MOD> x){
			return IntMod(value-x.value);
		}
		inline IntMod<T,MOD> operator*(T x){
			return IntMod(value*x);
		}
		inline IntMod<T,MOD> operator*(IntMod<T,MOD> x){
			return IntMod(value*x.value);
		}
		template<T x>
		inline IntMod<T,MOD> div(){
			T a,b;
			exgcd<T,MOD>(MOD,x,a,b);
			//b=1/x
			return IntMod(value*nm(b));
		}
};

typedef IntMod<long long, 1000000007> TIM;

TIM F_(long long n_, int k){
	TIM n(n_);
	TIM pn[51];
	pn[1].set(n_);
	for(int i=2;i<51;i++) pn[i]=pn[i-1], pn[i]*=n_;
	switch(k){
	case 1: return ((n + 1)*n).div<2>();
	 case 2: return ((n + 1)*(pn[1]*2ll + 1)*n).div<6>();
	 case 3: return ((n+1).sqr()*pn[2]).div<4>();
	 case 4: return ((n + 1)*(pn[1]*2ll + 1)*(pn[2]*3ll + pn[1]*3ll - 1)*n).div<30>();
	 case 5: return ((n+ 1).sqr()*(pn[2]*2ll + pn[1]*2ll - 1)*n.sqr()).div<12>();
	 case 6: return ((n + 1)*(pn[1]*2ll + 1)*(pn[4]*3ll+ pn[3]*6ll- pn[1]*3ll + 1)*n).div<42>();
	 case 7: return ((n + 1).sqr()*(pn[4]*3ll + pn[3]*6ll - n.sqr() - pn[1]*4ll +2)*n.sqr()).div<24>();
	case 8: return ((n + 1)*(pn[1]*2ll + 1)*(pn[6]*5ll + pn[5]*15ll + pn[4]*5ll - pn[3]*15ll -n.sqr() + pn[1]*9ll- 3)*n).div<90>();
	 case 9: return ((n + 1).sqr()*(n.sqr() + n - 1)*(pn[4]*2ll + pn[3]*4ll - n.sqr()- pn[1]*3ll +3)*n.sqr()).div<20>();
	 case 10: return ((n + 1)*(pn[1]*2ll + 1)*(n.sqr() + n - 1)*(pn[6]*3ll + pn[5]*9ll+pn[4]*2ll - pn[3]*11ll + pn[2]*3ll + pn[1]*10ll - 5)*n).div<66>();
	 case 11: return ((n + 1).sqr()*(pn[8]*2ll+pn[7]*8ll + pn[6]*4ll - pn[5]*16ll - pn[4]*5ll + pn[3]*26ll - pn[2]*3ll - pn[1]*20ll + 10)*n.sqr()).div<24>();
	case 12: return ((n + 1)*(pn[1]*2ll + 1)*(pn[10]*105ll + pn[9]*525ll + pn[8]*525ll - pn[7]*1050ll-pn[6]*1190ll + pn[5]*2310ll + pn[4]*1420ll - pn[3]*3285ll - pn[2]*287ll + pn[1]*2073ll -691)*n).div<2730>();
	case 13: return ((n + 1).sqr()*(pn[10]*30ll + pn[9]*150ll + pn[8]*125ll - pn[7]*400ll -pn[6]*326ll +pn[5]*1052ll + pn[4]*367ll - pn[3]*1786ll + pn[2]*202ll + pn[1]*1382ll - 691)*n.sqr()).div<420>();
	case 14: return ((n + 1)*(pn[1]*2ll + 1)*(pn[12]*3ll + pn[11]*18ll + pn[10]*24ll - pn[9]*45ll - pn[8]*81ll+pn[7]*144ll + pn[6]*182ll - pn[5]*345ll - pn[4]*217ll + pn[3]*498ll + pn[2]*44ll - pn[1]*315ll+105)*n).div<90>();
	 case 15: return ((n + 1).sqr()*(pn[12]*3ll + pn[11]*18ll + pn[10]*21ll - pn[9]*60ll-pn[8]*83ll + pn[7]*226ll + pn[6]*203ll - pn[5]*632ll - pn[4]*226ll + pn[3]*1084ll - pn[2]*122ll-pn[1]*840ll + 420)*n.sqr()).div<48>();
	 case 16: return ((n + 1)*(pn[1]*2ll + 1)*(pn[14]*15ll + pn[13]*105ll+pn[12]*175ll - pn[11]*315ll - pn[10]*805ll + pn[9]*1365ll + pn[8]*2775ll - pn[7]*4845ll-pn[6]*6275ll + pn[5]*11835ll + pn[4]*7485ll - pn[3]*17145ll - pn[2]*1519ll + pn[1]*10851ll-3617)*n).div<510>();
	 case 17: return ((n + 1).sqr()*(pn[14]*10ll + pn[13]*70ll + pn[12]*105ll -pn[11]*280ll- pn[10]*565ll + pn[9]*1410ll + pn[8]*2165ll - pn[7]*5740ll - pn[6]*5271ll +pn[5]*16282ll +pn[4]*5857ll - pn[3]*27996ll + pn[2]*3147ll + pn[1]*21702ll - 10851)*n.sqr()).div<180>();
	 case 18: return ((n+ 1)*(pn[1]*2ll + 1)*(pn[16]*105ll + pn[15]*840ll + pn[14]*1680ll - pn[13]*2940ll -pn[12]*9996ll+ pn[11]*16464ll + pn[10]*48132ll - pn[9]*80430ll - pn[8]*167958ll + pn[7]*292152ll+pn[6]*380576ll - pn[5]*716940ll - pn[4]*454036ll + pn[3]*1039524ll + pn[2]*92162ll-pn[1]*658005ll + 219335)*n).div<3990>();
	 case 19: return ((n + 1).sqr()*(pn[16]*42ll + pn[15]*336ll+pn[14]*616ll - pn[13]*1568ll - pn[12]*4263ll + pn[11]*10094ll + pn[10]*22835ll - pn[9]*55764ll-pn[8]*87665ll + pn[7]*231094ll + pn[6]*213337ll - pn[5]*657768ll - pn[4]*236959ll+pn[3]*1131686ll - pn[2]*127173ll - pn[1]*877340ll + 438670)*n.sqr()).div<840>();
	 case 20: return ((n+1)*(pn[1]*2ll + 1)*(pn[18]*165ll + pn[17]*1485ll + pn[16]*3465ll - pn[15]*5940ll -pn[14]*25740ll+ pn[13]*41580ll + pn[12]*163680ll - pn[11]*266310ll - pn[10]*801570ll +pn[9]*1335510ll +pn[8]*2806470ll - pn[7]*4877460ll - pn[6]*6362660ll + pn[5]*11982720ll +pn[4]*7591150ll -pn[3]*17378085ll - pn[2]*1540967ll + pn[1]*11000493ll - 3666831)*n).div<6930>();
	 case 21: return ((n +1).sqr()*(pn[18]*30ll + pn[17]*270ll + pn[16]*585ll - pn[15]*1440ll - pn[14]*5020ll +pn[13]*11480ll+ pn[12]*35355ll - pn[11]*82190ll - pn[10]*190745ll + pn[9]*463680ll +pn[8]*733035ll -pn[7]*1929750ll - pn[6]*1783781ll + pn[5]*5497312ll + pn[4]*1981107ll -pn[3]*9459526ll +pn[2]*1062932ll + pn[1]*7333662ll - 3666831)*n.sqr()).div<660>();
	 case 22: return ((n +1)*(pn[1]*2ll +1)*(pn[20]*15ll + pn[19]*150ll + pn[18]*400ll - pn[17]*675ll - pn[16]*3615ll +pn[15]*5760ll +pn[14]*29220ll - pn[13]*46710ll - pn[12]*189702ll + pn[11]*307908ll +pn[10]*933064ll -pn[9]*1553550ll - pn[8]*3269646ll + pn[7]*5681244ll + pn[6]*7413782ll -pn[5]*13961295ll -pn[4]*8845327ll + pn[3]*20248638ll + pn[2]*1795584ll - pn[1]*12817695ll +4272565)*n).div<690>();
	case 23: return ((n + 1).sqr()*(pn[20]*30ll + pn[19]*300ll + pn[18]*750ll -pn[17]*1800ll -pn[16]*7776ll + pn[15]*17352ll + pn[14]*69212ll - pn[13]*155776ll -pn[12]*493131ll +pn[11]*1142038ll + pn[10]*2666455ll - pn[9]*6474948ll - pn[8]*10250315ll +pn[7]*26975578ll+ pn[6]*24943119ll - pn[5]*76861816ll - pn[4]*27701758ll + pn[3]*132265332ll-pn[2]*14861886ll - pn[1]*102541560ll + 51270780)*n.sqr()).div<720>();
	 case 24: return ((n + 1)*(pn[1]*2ll+1)*(pn[22]*273ll + pn[21]*3003ll + pn[20]*9009ll - pn[19]*15015ll - pn[18]*97097ll+pn[17]*153153ll + pn[16]*969969ll - pn[15]*1531530ll - pn[14]*8030022ll +pn[13]*12810798ll+ pn[12]*52402714ll - pn[11]*85009470ll - pn[10]*258027882ll +pn[9]*429546558ll +pn[8]*904376004ll - pn[7]*571337278ll - pn[6]*50706133ll +pn[5]*861727842ll +pn[4]*446689415ll - pn[3]*600898040ll - pn[2]*496674885ll +pn[1]*545461344ll -181820448)*n).div<13650>();
	 case 25: return ((n + 1).sqr()*(pn[22]*42ll + pn[21]*462ll +pn[20]*1309ll -pn[19]*3080ll - pn[18]*16079ll + pn[17]*35238ll + pn[16]*175833ll -pn[15]*386904ll -pn[14]*1589210ll + pn[13]*3565324ll + pn[12]*11359537ll - pn[11]*26284398ll-pn[10]*61459521ll + pn[9]*149203440ll + pn[8]*236279941ll - pn[7]*621763322ll-pn[6]*574962926ll + pn[5]*771689167ll + pn[4]*638548653ll - pn[3]*48786459ll+pn[2]*342572785ll + pn[1]*363640896ll - 181820448)*n.sqr()).div<1092>();
	 case 26: return ((n + 1)*(pn[1]*2ll+1)*(pn[24]*7ll + pn[23]*84ll + pn[22]*280ll - pn[21]*462ll - pn[20]*3542ll + pn[19]*5544ll+pn[18]*42790ll - pn[17]*66957ll - pn[16]*438977ll + pn[15]*691944ll + pn[14]*3655360ll-pn[13]*5829012ll - pn[12]*23884796ll + pn[11]*38741700ll + pn[10]*117639298ll-pn[9]*195829797ll - pn[8]*412342529ll + pn[7]*716428692ll + pn[6]*935010264ll-pn[5]*760729735ll - pn[4]*115557919ll + pn[3]*553701746ll + pn[2]*226457058ll-pn[1]*616536460ll + 538845489)*n).div<378>();
	 case 27: return ((n + 1).sqr()*(pn[24]*2ll + pn[23]*24ll+pn[22]*76ll - pn[21]*176ll - pn[20]*1089ll + pn[19]*2354ll + pn[18]*14321ll - pn[17]*30996ll-pn[16]*159536ll + pn[15]*350068ll + pn[14]*1447750ll - pn[13]*3245568ll -pn[12]*10356931ll+ pn[11]*23959430ll + pn[10]*56043471ll - pn[9]*136046372ll -pn[8]*215462444ll +pn[7]*566971260ll + pn[6]*524305554ll - pn[5]*615582361ll -pn[4]*582288225ll +pn[3]*780158804ll - pn[2]*312388431ll - pn[1]*155381942ll +77690971)*n.sqr()).div<56>();
	 case 28: return ((n + 1)*(pn[1]*2ll + 1)*(pn[26]*15ll + pn[25]*195ll +pn[24]*715ll - pn[23]*1170ll -pn[22]*10478ll + pn[21]*16302ll + pn[20]*150436ll -pn[19]*233805ll - pn[18]*1870583ll +pn[17]*2922777ll + pn[16]*19312501ll - pn[15]*30430140ll- pn[14]*161044508ll +pn[13]*256781832ll + pn[12]*52627799ll - pn[11]*707332618ll -pn[10]*184837888ll +pn[9]*630923141ll + pn[8]*173840815ll - pn[7]*576222793ll -pn[6]*210314671ll +pn[5]*603583403ll + pn[4]*167911673ll - pn[3]*553659211ll -pn[2]*981035330ll +pn[1]*248382590ll - 749460868)*n).div<870>();
	 case 29: return ((n + 1).sqr()*(pn[26]*2ll+ pn[25]*26ll +pn[24]*91ll - pn[23]*208ll - pn[22]*1502ll + pn[21]*3212ll + pn[20]*23353ll -pn[19]*49918ll -pn[18]*313712ll + pn[17]*677342ll + pn[16]*3511303ll - pn[15]*7699948ll -pn[14]*31896622ll+ pn[13]*71493192ll + pn[12]*228229813ll - pn[11]*527952818ll -pn[10]*235045015ll +pn[9]*998042848ll + pn[8]*748228195ll - pn[7]*494499224ll -pn[6]*554321131ll +pn[5]*603141479ll + pn[4]*832102901ll - pn[3]*267347267ll +pn[2]*884212776ll +pn[1]*498921729ll - 749460868)*n.sqr()).div<60>();
	 case 30: return ((n + 1)*(pn[1]*2ll+1)*(pn[28]*231ll + pn[27]*3234ll + pn[26]*12936ll - pn[25]*21021ll - pn[24]*217217ll+pn[23]*336336ll + pn[22]*3653650ll - pn[21]*5648643ll - pn[20]*54097043ll+pn[19]*83969886ll + pn[18]*677256580ll - pn[17]*57869806ll - pn[16]*3032064ll+pn[15]*33482999ll + pn[14]*417981524ll - pn[13]*143713782ll -pn[12]*864882350ll +pn[11]*369180409ll + pn[10]*950758848ll -pn[9]*110728466ll - pn[8]*111530404ll +pn[7]*222659839ll +pn[6]*298855604ll - pn[5]*59613322ll - pn[4]*160797406ll+pn[3]*271002770ll + pn[2]*925430472ll - pn[1]*523647086ll +841215700)*n).div<14322>();
	 case 31: return ((n + 1).sqr()*(pn[28]*231ll + pn[27]*3234ll +pn[26]*12397ll - pn[25]*28028ll -pn[24]*233233ll + pn[23]*494494ll + pn[22]*4228301ll -pn[21]*8951096ll - pn[20]*67317019ll +pn[19]*143585134ll + pn[18]*909110951ll -pn[17]*961807029ll - pn[16]*187430477ll +pn[15]*336667976ll + pn[14]*565987843ll- pn[13]*468643655ll - pn[12]*371625048ll +pn[11]*211893744ll +pn[10]*398325058ll - pn[9]*8543853ll - pn[8]*520553834ll+pn[7]*49651514ll + pn[6]*467907307ll - pn[5]*985466128ll -pn[4]*900133413ll +pn[3]*785732940ll - pn[2]*663140919ll -pn[1]*459451109ll + 729725558)*n.sqr()).div<7392>();
	 case 32: return ((n + 1)*(pn[1]*2ll +1)*(pn[30]*1785ll + pn[29]*26775ll + pn[28]*116025ll -pn[27]*187425ll - pn[26]*2211615ll +pn[25]*3411135ll + pn[24]*43060745ll - pn[23]*66296685ll- pn[22]*748192627ll +pn[21]*155437276ll + pn[20]*157717312ll - pn[19]*314294606ll-pn[18]*916610174ll + pn[17]*532062557ll + pn[16]*330358320ll -pn[15]*261568755ll -pn[14]*416693679ll + pn[13]*755824896ll +pn[12]*232896916ll - pn[11]*727257822ll -pn[10]*142923476ll +pn[9]*578014125ll + pn[8]*422386711ll - pn[7]*922587129ll-pn[6]*250132452ll + pn[5]*336492239ll + pn[4]*847305694ll -pn[3]*939204657ll -pn[2]*983042100ll + pn[1]*444165468ll -148055156)*n).div<117810>();
	 case 33: return ((n +1).sqr()*(pn[30]*210ll + pn[29]*3150ll +pn[28]*13125ll - pn[27]*29400ll - pn[26]*278957ll +pn[25]*587314ll + pn[24]*5828849ll -pn[23]*12245012ll - pn[22]*108432253ll +pn[21]*229109518ll + pn[20]*736342710ll -pn[19]*701794931ll - pn[18]*479878932ll +pn[17]*661552788ll +pn[16]*190802776ll - pn[15]*43158333ll - pn[14]*580901146ll+pn[13]*204960618ll + pn[12]*585551766ll - pn[11]*376064143ll -pn[10]*724098270ll +pn[9]*824260676ll + pn[8]*981558982ll -pn[7]*787378626ll - pn[6]*975929653ll +pn[5]*739237918ll +pn[4]*360942732ll - pn[3]*461123375ll + pn[2]*582506535ll+pn[1]*296110312ll - 148055156)*n.sqr()).div<7140>();
	 case 34: return ((n + 1)*(pn[1]*2ll +1)*(pn[32]*3ll +pn[31]*48ll + pn[30]*224ll - pn[29]*360ll - pn[28]*4808ll + pn[27]*7392ll +pn[26]*107256ll -pn[25]*164580ll - pn[24]*2160340ll + pn[23]*3322800ll + pn[22]*37818560ll- pn[21]*58389240ll- pn[20]*564958600ll + pn[19]*876632520ll + pn[18]*87388371ll -pn[17]*69398813ll -pn[16]*320554259ll + pn[15]*515530795ll +pn[14]*693291883ll - pn[13]*297703215ll -pn[12]*596446950ll +pn[11]*543522029ll + pn[10]*979324367ll - pn[9]*740747558ll-pn[8]*449864850ll + pn[7]*45171047ll + pn[6]*94036349ll -pn[5]*163640047ll -pn[4]*300043642ll + pn[3]*31885483ll +pn[2]*804860801ll - pn[1]*223233936ll +74411312)*n).div<210>();
	 case 35: return ((n + 1).sqr()*(pn[32]*2ll + pn[31]*32ll + pn[30]*144ll - pn[29]*320ll- pn[28]*3431ll +pn[27]*7182ll + pn[26]*81819ll - pn[25]*170820ll - pn[24]*1757535ll +pn[23]*3685890ll +pn[22]*32898915ll - pn[21]*69483720ll - pn[20]*527564655ll +pn[19]*124613023ll +pn[18]*136365346ll - pn[17]*397343715ll - pn[16]*998827876ll+pn[15]*394999453ll + pn[14]*950576891ll - pn[13]*296153221ll -pn[12]*902804192ll +pn[11]*101761591ll + pn[10]*978796312ll -pn[9]*59354201ll - pn[8]*2735896ll +pn[7]*64825993ll +pn[6]*321549101ll - pn[5]*707924195ll - pn[4]*401157325ll+pn[3]*510238838ll - pn[2]*808651554ll - pn[1]*892935744ll +446467872)*n.sqr()).div<72>();
	 case 36: return ((n + 1)*(pn[1]*2ll + 1)*(pn[34]*25935ll +pn[33]*440895ll + pn[32]*2204475ll -pn[31]*3527160ll - pn[30]*52907400ll +pn[29]*81124680ll + pn[28]*340320793ll -pn[27]*51043526ll - pn[26]*970228170ll +pn[25]*480864011ll + pn[24]*653364584ll -pn[23]*720478878ll -pn[22]*870506104ll + pn[21]*665998588ll + pn[20]*613812682ll-pn[19]*253718310ll - pn[18]*659774949ll + pn[17]*616521575ll +pn[16]*894349058ll -pn[15]*149784364ll -pn[14]*541717290ll + pn[13]*887468117ll +pn[12]*155801316ll -pn[11]*177436029ll -pn[10]*592511414ll + pn[9]*477485132ll +pn[8]*32389159ll -pn[7]*787326308ll -pn[6]*372953245ll + pn[5]*453093018ll +pn[4]*272946314ll -pn[3]*635965980ll -pn[2]*481166927ll + pn[1]*539733377ll -846577797)*n).div<1919190>();
	 case 37: return ((n + 1).sqr()*(pn[34]*2730ll +pn[33]*46410ll + pn[32]*224315ll - pn[31]*495040ll -pn[30]*5951400ll + pn[29]*12397840ll +pn[28]*160599985ll - pn[27]*333597810ll -pn[26]*943622116ll + pn[25]*220842028ll +pn[24]*271873274ll - pn[23]*764588576ll -pn[22]*608010307ll +pn[21]*980609183ll + pn[20]*176384869ll - pn[19]*333378914ll-pn[18]*733889971ll + pn[17]*801158849ll + pn[16]*829421072ll -pn[15]*460000979ll -pn[14]*758134521ll + pn[13]*976270014ll+ pn[12]*734630716ll - pn[11]*445531432ll-pn[10]*66643509ll + pn[9]*578818450ll +pn[8]*59793666ll - pn[7]*698405782ll-pn[6]*278081360ll + pn[5]*254568495ll +pn[4]*401998981ll - pn[3]*58566450ll+pn[2]*182705435ll + pn[1]*693155587ll -846577797)*n.sqr()).div<103740>();
	 case 38: return ((n + 1)*(pn[1]*2ll+ 1)*(pn[36]*105ll +pn[35]*1890ll + pn[34]*10080ll - pn[33]*16065ll - pn[32]*268821ll +pn[31]*411264ll +pn[30]*7674072ll - pn[29]*11716740ll - pn[28]*201595044ll +pn[27]*308250936ll +pn[26]*695486740ll - pn[25]*197355571ll - pn[24]*488671915ll +pn[23]*831685658ll+ pn[22]*348583055ll - pn[21]*438717408ll - pn[20]*704754310ll+pn[19]*276490162ll + pn[18]*273202542ll - pn[17]*548048894ll -pn[16]*144689678ll +pn[15]*491058964ll + pn[14]*5965475ll -pn[13]*754477698ll - pn[12]*293573766ll+pn[11]*817599498ll + pn[10]*476247691ll -pn[9]*623171282ll - pn[8]*205425917ll+pn[7]*119724513ll + pn[6]*861968630ll -pn[5]*852815198ll - pn[4]*765853348ll+pn[3]*575187614ll + pn[2]*936876905ll -pn[1]*192909154ll + 397636387)*n).div<8190>();
	 case 39: return ((n +1).sqr()*(pn[36]*42ll + pn[35]*756ll + pn[34]*3906ll - pn[33]*8568ll -pn[32]*114716ll +pn[31]*238000ll + pn[30]*3477096ll - pn[29]*7192192ll - pn[28]*96759271ll+pn[27]*200710734ll + pn[26]*392439469ll - pn[25]*985589672ll - pn[24]*813809798ll+pn[23]*613209254ll + pn[22]*726945498ll - pn[21]*67100236ll -pn[20]*385104282ll +pn[19]*837308800ll + pn[18]*863621699ll -pn[17]*564552184ll - pn[16]*198646728ll +pn[15]*961845640ll +pn[14]*92919085ll - pn[13]*147683803ll -pn[12]*719859051ll +pn[11]*587401898ll +pn[10]*466038169ll - pn[9]*519478229ll -pn[8]*629827037ll +pn[7]*779132296ll +pn[6]*773710352ll - pn[5]*326552986ll -pn[4]*348788019ll +pn[3]*24129017ll -pn[2]*921518978ll - pn[1]*181091075ll +590545541)*n.sqr()).div<1680>();
	 case 40: return ((n + 1)*(pn[1]*2ll + 1)*(pn[38]*1155ll +pn[37]*21945ll + pn[36]*124355ll -pn[35]*197505ll - pn[34]*3664815ll + pn[33]*5595975ll +pn[32]*117089115ll -pn[31]*178431660ll - pn[30]*469504479ll + pn[29]*293472545ll +pn[28]*890740943ll -pn[27]*482847680ll - pn[26]*362469212ll +pn[25]*785127658ll + pn[24]*109000924ll -pn[23]*556065215ll -pn[22]*555805160ll + pn[21]*611740344ll + pn[20]*541149232ll-pn[19]*117594013ll - pn[18]*442083192ll +pn[17]*221921791ll + pn[16]*612052934ll-pn[15]*529040293ll - pn[14]*594923691ll +pn[13]*156905676ll + pn[12]*122651883ll-pn[11]*762430666ll - pn[10]*117321918ll +pn[9]*557198210ll + pn[8]*193022897ll-pn[7]*68133447ll - pn[6]*747316969ll +pn[5]*155042170ll + pn[4]*161067210ll-pn[3]*319121900ll - pn[2]*408434535ll +pn[1]*272212749ll - 90737583)*n).div<94710>();
	 case 41: return ((n +1).sqr()*(pn[38]*330ll + pn[37]*6270ll + pn[36]*34485ll - pn[35]*75240ll -pn[34]*1115235ll +pn[33]*2305710ll + pn[32]*37720705ll - pn[31]*77747120ll -pn[30]*180558493ll +pn[29]*438864106ll + pn[28]*88904354ll - pn[27]*616672814ll-pn[26]*512106840ll + pn[25]*640886487ll + pn[24]*418387216ll -pn[23]*477660912ll -pn[22]*771712714ll + pn[21]*21086326ll +pn[20]*319968639ll - pn[19]*661023604ll -pn[18]*733139403ll+ pn[17]*127302396ll + pn[16]*812871025ll -pn[15]*753044439ll -pn[14]*361753925ll +pn[13]*476552282ll + pn[12]*79060779ll -pn[11]*634673840ll -pn[10]*266549081ll +pn[9]*167771995ll + pn[8]*901164344ll -pn[7]*970100676ll -pn[6]*264569824ll +pn[5]*499240317ll + pn[4]*46047166ll -pn[3]*591334649ll +pn[2]*523454579ll +pn[1]*544425498ll - 272212749)*n.sqr()).div<13860>();
	 case 42: return ((n + 1)*(pn[1]*2ll +1)*(pn[40]*1155ll + pn[39]*23100ll + pn[38]*138600ll -pn[37]*219450ll - pn[36]*4491410ll +pn[35]*6846840ll + pn[34]*159627930ll -pn[33]*242865315ll - pn[32]*298343708ll +pn[31]*68948216ll + pn[30]*312541870ll -pn[29]*503286913ll - pn[28]*104904745ll +pn[27]*409000574ll +pn[26]*587297310ll - pn[25]*85446245ll - pn[24]*626643016ll+pn[23]*482687643ll + pn[22]*403670100ll - pn[21]*346848968ll- pn[20]*122879121ll +pn[19]*857743169ll +pn[18]*837569105ll - pn[17]*685225235ll -pn[16]*852696788ll +pn[15]*121657789ll +pn[14]*208386281ll - pn[13]*373408316ll -pn[12]*461001590ll +pn[11]*878206543ll +pn[10]*836957652ll - pn[9]*194539739ll -pn[8]*462380751ll +pn[7]*790840996ll +pn[6]*254226064ll - pn[5]*776759594ll -pn[4]*645075950ll +pn[3]*355993715ll +pn[2]*825341190ll - pn[1]*916008639ll +305336213)*n).div<99330>();
	 case 43: return ((n + 1).sqr()*(pn[40]*210ll + pn[39]*4200ll+ pn[38]*24500ll - pn[37]*53200ll -pn[36]*868357ll + pn[35]*1789914ll + pn[34]*32583789ll -pn[33]*66957492ll -pn[32]*139297187ll + pn[31]*345551866ll + pn[30]*922732839ll -pn[29]*191017530ll -pn[28]*591588823ll + pn[27]*374195169ll +pn[26]*16090697ll - pn[25]*406376563ll -pn[24]*620812931ll +pn[23]*648002418ll + pn[22]*421540426ll - pn[21]*491083263ll-pn[20]*586479748ll + pn[19]*664042752ll +pn[18]*735755812ll - pn[17]*135554362ll-pn[16]*449347119ll + pn[15]*34248593ll +pn[14]*809527523ll - pn[13]*653303632ll-pn[12]*711380726ll + pn[11]*76065070ll +pn[10]*515688676ll - pn[9]*107442415ll-pn[8]*524611535ll + pn[7]*156665478ll +pn[6]*178718318ll - pn[5]*514102114ll-pn[4]*833616399ll + pn[3]*181334898ll -pn[2]*479995030ll - pn[1]*221344845ll+610672426)*n.sqr()).div<9240>();
	 case 44: return ((n + 1)*(pn[1]*2ll +1)*(pn[42]*2415ll + pn[41]*50715ll+ pn[40]*321195ll - pn[39]*507150ll - pn[38]*11393970ll +pn[37]*17344530ll +pn[36]*448021140ll - pn[35]*680703975ll - pn[34]*554986693ll +pn[33]*172832020ll +pn[32]*177506057ll - pn[31]*852675099ll -pn[30]*425986303ll + pn[29]*65316997ll +pn[28]*97976336ll -pn[27]*679623006ll - pn[26]*48294827ll + pn[25]*912253747ll+pn[24]*509803003ll - pn[23]*220831371ll -pn[22]*868745339ll + pn[21]*413533687ll+pn[20]*54707188ll - pn[19]*788827629ll -pn[18]*609934358ll + pn[17]*809315348ll+pn[16]*451028444ll - pn[15]*81200333ll -pn[14]*949495334ll + pn[13]*964843164ll+pn[12]*524597047ll - pn[11]*769317149ll -pn[10]*132974980ll + pn[9]*84121041ll+pn[8]*953854122ll - pn[7]*972841700ll -pn[6]*296046610ll + pn[5]*930490765ll+pn[4]*307674078ll - pn[3]*426756496ll -pn[2]*806974507ll + pn[1]*923840005ll-641280004)*n).div<217350>();
	 case 45: return ((n + 1).sqr()*(pn[42]*210ll +pn[41]*4410ll + pn[40]*27195ll- pn[39]*58800ll - pn[38]*1051890ll + pn[37]*2162580ll +pn[36]*43560825ll -pn[35]*89284230ll - pn[34]*691522063ll + pn[33]*472328349ll +pn[32]*597894342ll -pn[31]*668117026ll - pn[30]*510630406ll +pn[29]*689377831ll + pn[28]*129744586ll -pn[27]*948867003ll -pn[26]*501176084ll + pn[25]*951219164ll + pn[24]*577885798ll-pn[23]*106990746ll - pn[22]*663149060ll +pn[21]*433288859ll + pn[20]*336677187ll-pn[19]*106643226ll - pn[18]*80812952ll +pn[17]*268269130ll + pn[16]*616281555ll-pn[15]*500832233ll - pn[14]*24790782ll +pn[13]*550413797ll + pn[12]*798241730ll-pn[11]*146897243ll - pn[10]*511490722ll +pn[9]*169878680ll + pn[8]*342916092ll-pn[7]*855710864ll - pn[6]*342847212ll +pn[5]*541405281ll + pn[4]*287730112ll-pn[3]*116865498ll + pn[2]*417152752ll +pn[1]*282560001ll - 641280004)*n.sqr()).div<9660>();
	case 46: return ((n + 1)*(pn[1]*2ll + 1)*(pn[44]*105ll + pn[43]*2310ll + pn[42]*15400ll -pn[41]*24255ll- pn[40]*595595ll + pn[39]*905520ll + pn[38]*25783450ll - pn[37]*39127935ll-pn[36]*54801048ll + pn[35]*601765543ll + pn[34]*313919267ll - pn[33]*771761672ll-pn[32]*680768495ll + pn[31]*907033575ll + pn[30]*841953326ll -pn[29]*216446766ll -pn[28]*42286803ll + pn[27]*671653591ll +pn[26]*582972635ll - pn[25]*210285741ll-pn[24]*940215182ll + pn[23]*15465633ll +pn[22]*554608633ll - pn[21]*839645766ll-pn[20]*843897511ll + pn[19]*185669139ll +pn[18]*985928915ll - pn[17]*571727935ll-pn[16]*63745280ll + pn[15]*881481891ll +pn[14]*506446606ll - pn[13]*700410851ll-pn[12]*113641815ll + pn[11]*520668148ll +pn[10]*546802858ll - pn[9]*80538354ll-pn[8]*899574962ll + pn[7]*389631613ll +pn[6]*493206309ll - pn[5]*934625270ll-pn[4]*477226858ll + pn[3]*183152915ll +pn[2]*66549971ll - pn[1]*191401414ll+397133807)*n).div<9870>();
	 case 47: return ((n + 1).sqr()*(pn[44]*210ll +pn[43]*4620ll + pn[42]*30030ll- pn[41]*64680ll - pn[40]*1262730ll + pn[39]*2590140ll +pn[38]*57440010ll -pn[37]*117470160ll - pn[36]*463942634ll + pn[35]*45355421ll +pn[34]*430074864ll -pn[33]*905505149ll - pn[32]*769601535ll +pn[31]*444708205ll + pn[30]*432051749ll -pn[29]*308811696ll -pn[28]*652369231ll + pn[27]*613550151ll + pn[26]*447059685ll-pn[25]*507669514ll - pn[24]*594546274ll +pn[23]*696762055ll + pn[22]*444835677ll-pn[21]*586433402ll - pn[20]*576216205ll +pn[19]*738865805ll + pn[18]*411141457ll-pn[17]*561148712ll - pn[16]*345033106ll +pn[15]*251214917ll + pn[14]*425519489ll-pn[13]*102253888ll - pn[12]*687220409ll +pn[11]*476694699ll + pn[10]*449150995ll-pn[9]*374996682ll - pn[8]*675006108ll +pn[7]*725008891ll + pn[6]*252504267ll-pn[5]*230017418ll - pn[4]*383208600ll +pn[3]*996434618ll - pn[2]*967006011ll-pn[1]*62422603ll + 531211305)*n.sqr()).div<10080>();
	 case 48: return ((n + 1)*(pn[1]*2ll + 1)*(pn[46]*3315ll+ pn[45]*76245ll + pn[44]*533715ll -pn[43]*838695ll - pn[42]*22421113ll + pn[41]*34051017ll+ pn[40]*63856644ll -pn[39]*612810478ll - pn[38]*945788562ll + pn[37]*725088075ll+pn[36]*679316431ll - pn[35]*381518677ll - pn[34]*630632473ll +pn[33]*136708041ll +pn[32]*106506480ll - pn[31]*728113744ll -pn[30]*389787528ll + pn[29]*948738164ll+pn[28]*492920215ll - pn[27]*713749401ll -pn[26]*277408719ll + pn[25]*772987779ll+pn[24]*38102164ll - pn[23]*943647139ll -pn[22]*16992553ll + pn[21]*497312399ll+pn[20]*799052717ll - pn[19]*447235268ll -pn[18]*964970715ll + pn[17]*171073696ll+pn[16]*693542748ll - pn[15]*125850963ll -pn[14]*870490454ll + pn[13]*868661159ll+pn[12]*52253745ll - pn[11]*512711197ll -pn[10]*820044063ll + pn[9]*486421686ll+pn[8]*297078125ll - pn[7]*188828027ll -pn[6]*913824143ll + pn[5]*465150221ll+pn[4]*272522309ll - pn[3]*641358574ll -pn[2]*205217080ll + pn[1]*628504907ll-876168307)*n).div<324870>();
	 case 49: return ((n + 1).sqr()*(pn[46]*1326ll +pn[45]*30498ll +pn[44]*208403ll - pn[43]*447304ll - pn[42]*9493055ll + pn[41]*19433414ll +pn[40]*472318327ll- pn[39]*964070068ll - pn[38]*274214367ll + pn[37]*512498795ll +pn[36]*146243910ll -pn[35]*804986615ll - pn[34]*727456099ll +pn[33]*259898799ll + pn[32]*427798672ll -pn[31]*115496136ll -pn[30]*507809281ll + pn[29]*131114691ll +pn[28]*946288457ll -pn[27]*23691591ll -pn[26]*299953741ll + pn[25]*623599073ll +pn[24]*523383795ll -pn[23]*670366656ll -pn[22]*423736776ll + pn[21]*517840201ll +pn[20]*168493903ll -pn[19]*854828007ll -pn[18]*310017220ll + pn[17]*474862440ll +pn[16]*327960278ll -pn[15]*130782989ll -pn[14]*746944882ll + pn[13]*624672746ll +pn[12]*272599708ll -pn[11]*169872155ll -pn[10]*879975369ll + pn[9]*929822886ll +pn[8]*881477307ll -pn[7]*692777486ll -pn[6]*592976570ll + pn[5]*878730619ll +pn[4]*618854258ll -pn[3]*116439121ll+ pn[2]*177378057ll + pn[1]*761683014ll -380841507)*n.sqr()).div<66300>();
	 case 50: return ((n + 1)*(pn[1]*2ll +1)*(pn[48]*429ll + pn[47]*10296ll + pn[46]*75504ll -pn[45]*118404ll - pn[44]*3433716ll +pn[43]*5209776ll + pn[42]*177855964ll -pn[41]*269388834ll - pn[40]*790556290ll +pn[39]*320528845ll + pn[38]*690117751ll -pn[37]*195441042ll -pn[36]*902014220ll + pn[35]*450741844ll + pn[34]*210902801ll-pn[33]*41725120ll - pn[32]*989479370ll + pn[31]*505081608ll +pn[30]*87471552ll -pn[29]*383748132ll -pn[28]*246090995ll + pn[27]*61010555ll +pn[26]*488956052ll -pn[25]*263939352ll -pn[24]*107010618ll + pn[23]*292485603ll +pn[22]*609865677ll -pn[21]*61041310ll -pn[20]*454434299ll + pn[19]*212172100ll +pn[18]*883555238ll -pn[17]*431418900ll -pn[16]*754074777ll + pn[15]*846821612ll +pn[14]*359011165ll -pn[13]*461927550ll -pn[12]*728446227ll + pn[11]*823633112ll+ pn[10]*221768607ll-pn[9]*244469463ll - pn[8]*889761458ll+ pn[7]*956876915ll +pn[6]*445686708ll -pn[5]*646968516ll- pn[4]*710198856ll +pn[3]*388782535ll + pn[2]*427604107ll- pn[1]*835797428ll+ 945265814)*n).div<43758>();
	}
	return n;
}
long long F(long long n, int k){
	TIM ret=F_(n,k);
	return ret.value;
}

int main(){
	long long n;int k;
	while(scanf("%lld%d",&n,&k)==2) printf("%lld\n",F(n,k));
}