Language: C++

#define _CRT_SECURE_NO_WARNINGS
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define rep(i,n) for(int i=0;i<(lint)(n);i++)
#define REP(i,n) for(int i=1;i<=(lint)(n);i++)
#define all(V) V.begin(),V.end()
#define stackReplaceBegin(size)\
	void* p=malloc(size);\
	esp_new=(lint)p+size-1;\
	void * stack_extend_memory_ = malloc(size);\
	void * stack_extend_origin_memory_;\
	char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);\
	*stack_extend_dummy_memory_ = 0;\
	asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
typedef long long lint;
typedef unsigned long long ulint;
typedef std::pair<lint, lint> P;
constexpr int INF = INT_MAX/2;
constexpr lint LINF = LLONG_MAX/2;
constexpr double eps = DBL_EPSILON;
constexpr double PI=3.141592653589793238462643383279;
lint esp_new;
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
inline lint gcd(lint a, lint b) {
	while (b) {
		lint c = a;
		a = b; b = c % b;
	}
	return a;
}
inline lint lcm(lint a, lint b) {
	return a / gcd(a, b) * b;
}
bool isprime(lint n) {
	if (n == 1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}
template<typename T>
T mypow(T a, unsigned int b) {
	T res(1),now(a);
	while(b){
		if(b&1)res*=now;
		b>>=1;
		now*=now;
	}
	return res;
}
template<typename T>
void printArray(std::vector<T>& vec) {
	rep(i, vec.size() - 1)std::cout << vec[i] << " ";
	std::cout << vec.back() << std::endl;
}
template<typename T>
void printArray(T l, T r) {
	T rprev = r;
	rprev--;
	for (T i = l; i != rprev; i++) {
		std::cout << *i << " ";
	}
	std::cout << *rprev << std::endl;
}
lint modpow(lint a,lint b,int m){
	lint res(1),now(a);
	while(b){
		if(b&1){
			res*=now;
			res%=m;
		}
		b>>=1;
		now*=now;
		now%=m;
	}
	return res;
}
constexpr int mod=1000000007;
int k,n=-1;
constexpr int cnt=13;
char c[15];
lint fact[2000010],inv[2000010];
constexpr lint fact25[1000]={1,25,625,15625,390625,9765625,244140625,103515583,587889561,697238927,430973056,774326330,358158117,953952869,848821564,220538953,513473790,836844666,921116510,27912589,697814725,445368006,134200073,355001804,875045044,876125953,903148678,578716796,467919802,697994973,449874206,246855073,171376783,284419547,110488626,762215636,55390767,384769168,619229137,480728320,18207916,455197900,379947423,498685512,467137716,678442823,961070463,26761407,669035175,725879263,146981449,674536204,863404988,585124553,628113727,702843070,571076631,276915677,922891883,72296914,807422843,185570935,639273347,981833570,545839082,645976959,149423863,735596554,389913724,747843037,696075799,401894856,47371330,184283243,607081047,177026070,425651722,641292980,32324388,808109700,202742360,68558965,713974118,849352831,233820628,845515665,137891478,447286929,182173148,554328672,858216709,455417578,385439373,635984262,899606445,490160971,254024191,350604733,765118269,127956592,198914779,972869447,321736007,43400119,85002968,125074186,126854629,171365704,284142572,103564251,589106261,727656427,191410549,785263697,631592292,789807195,745179742,629493424,737335495,433387249,834681155,867028735,675718228,892955588,323889546,97238594,430964836,774120830,353020617,825515369,637884085,947102020,677550339,938758363,468958914,723972773,99319199,482979961,74498941,862473518,561837803,45944977,148624418,715610429,890260606,256514996,412874858,321871380,46784444,169611093,240277297,6932383,173309575,332739347,318483619,962090426,52260482,306512043,662801026,570025538,250638352,265958758,648968908,224222588,605564665,139116520,477912979,947824398,695609789,390244606,756115087,902877049,571926071,298151677,453791876,344796823,619920519,498012870,450321666,258041573,451039283,275981998,899549908,488747546,218688566,467214115,680352798,8819831,220495775,512394340,809858416,246460260,161506458,37661422,941535550,538388589,459714634,492865773,321644241,41105969,27649218,691230450,280761131,19028226,475705650,892641173,316029171,900729226,518230496,955762316,894057739,351443321,786082969,652074092,301852188,546304651,657616184,440404488,10112123,252803075,320076833,1920769,48019225,200480618,12015415,300385375,509634326,740858066,521451524,36288009,907200225,680005471,136656,3416400,85410000,135249986,381249629,531240662,281016459,25411426,635285650,882141145,53528471,338211768,455294144,382353523,558838012,970950209,273755057,843876383,96909428,422735686,568392080,209801902,245047515,126187833,154695804,867395079,684876828,121920581,48014504,200362593,9064790,226619750,665493715,637342763,933568970,339224089,480602169,15054141,376353525,408838062,220951480,523786965,94674034,366850836,171270837,281770897,44272376,106809393,670234811,755870163,896753949,418848571,471214205,780355048,508876067,721901591,47539649,188491218,712280422,807010431,175260635,381515847,537896112,447402709,185067648,626691172,667279195,681979763,49493956,237348893,933722290,343057089,576427169,410679127,266978105,674452583,861314463,532861428,321535609,38390169,959754225,993855464,846386432,159660653,991516304,787907432,697685667,442141556,53538823,338470568,461764144,544103523,602587984,64699495,617487368,437184095,929602305,240057464,1436558,35913950,897848750,446218596,155464823,886620554,165513696,137842372,446059279,151481898,787047429,676185592,904639688,615992046,399801045,995026062,875651382,891284403,282109921,52747976,318699393,967484776,187119232,677980772,949519188,737979539,449488349,237208648,930216165,255403964,385099058,627476387,686909570,172739131,318478247,961956126,48902982,222574543,564363540,109088402,727210036,180250774,506269322,656732966,418324038,458100880,452521923,313047998,826199901,654997385,374934513,373362762,334068987,351724619,793115419,827885342,697133410,428335131,708378205,709455006,736375031,409375649,234391155,859778840,494470853,361771241,44280962,107024043,675601061,890026413,250660171,266504233,662605783,565144463,128611477,215286904,382172565,554314062,857851459,446286328,157158123,928953054,223826189,595654690,891367152,284178646,104466101,611652511,291312670,282816701,70417476,760436893,10922192,273054800,826369958,659248810,481220138,30503366,762584150,64603617,615090418,377260345,431508562,787713980,692849367,321234056,30851344,771283600,282089867,52246626,306165643,654141026,353525538,838138394,953459710,836492589,912314585,807864471,196611635,915290847,882271021,56775371,419384268,484606630,115165666,879141636,978540753,463518657,587966348,699158602,478964931,974123198,353079782,826994494,674862210,871555138,788878303,721957442,48935924,223398093,584952290,623807152,595178695,879467277,986681778,667044282,676106938,902673338,566833296,170832302,270807522,770188008,254700067,367501633,187540762,688519022,212975431,324385740,109643444,741086086,527152024,178800509,470012697,750317348,757933574,948339224,708480439,712010856,800271281,6781885,169547125,238678097,966952390,173809582,345239522,630987994,774699745,367493492,187337237,683430897,85772306,144307636,607690879,192271870,806796722,169917910,247947722,198693008,967325172,183129132,578228272,455706702,392667473,816686762,417168910,429222680,730566930,264173124,604328058,108201345,705033611,625840156,646003795,150094763,752369054,809226224,230655460,766386465,159661492,991537279,788431807,710795042,769875931,246898142,172453508,311337672,783441751,586043642,651090952,277273688,931842158,296053789,401344676,33616830,840420750,10518603,262965075,574126833,353170727,829268119,731702835,292570749,314268676,856716851,417921128,448028130,200703173,17579290,439482250,987056180,676404332,910108188,752704546,817613524,440337960,8448923,211223075,280576840,14420951,360523775,13094312,327357800,183944944,598623572,965589202,139729882,493247029,331175641,279390969,984774183,619354407,483860070,96501666,412541636,313540830,838520701,963017385,75434457,885861418,146535296,663382379,584559363,613983977,349599320,739982944,499573474,489336766,233419066,835476615,886915235,172880721,322017997,50449869,261246718,531167908,279197609,979940183,498504407,462610091,565252198,131304852,282621279,65531926,638298143,957453470,936336589,408414564,210364030,259100715,477517833,937945748,448643539,216088398,402209915,55247805,381195118,529877887,246947084,173677058,341926422,548160494,704012259,600306356,7658795,191469875,786746847,668671042,716775938,919398331,984958121,623952857,598821320,970532902,263322382,583059508,576487602,412189952,304748730,618718201,467954920,698872923,471822956,795573823,889345442,233635896,840897365,22433978,560849450,21236152,530903800,272594909,814872683,371816935,295423312,385582751,639568712,989217695,730442207,261055049,526376183,159404484,985112079,627801807,695045070,376126631,403165712,79142730,978568243,464205907,605147598,128689845,217246104,431152565,778814055,470351242,758780973,969524199,238104807,952620140,815503339,387583335,689583312,239582681,989566990,739174582,479364424,984110523,602762907,69072570,726814243,170355949,258898697,472467383,811684498,292112310,302807701,570192476,254811802,370295008,257375137,434378383,859459505,486487478,162186866,54671622,366790543,169763512,244087772,102194258,554856436,871410809,785270078,631751817,793795320,844882867,122071528,51788179,294704468,367611651,190291212,757280272,932006674,300166689,504167176,604179316,104482795,612069861,301746420,543660451,591511184,787779502,694487417,362185306,54632587,365814668,145366637,634165904,854147495,353687228,842180644,54515953,362898818,72470387,811759668,293991560,349788951,744723719,618092849,452321120,308027923,700698026,517450531,936263191,406579614,164490280,112256972,806424286,160607010,15175222,379380550,484513687,112842091,821052261,526306385,157659534,941488329,537208064,430201509,755037655,875941249,898531078,463276796,581919823,547995477,699886834,497170731,429268191,731704705,292617499,315437426,885935601,148389871,709746754,743668731,591718149,792953627,823840542,596013410,900335152,508378646,709466066,736651531,416288149,407203655,180091305,502282597,557064841,926620934,165523189,138079697,451992404,299810023,495250526,381263066,531576587,289414584,235364551,884113740,102843346,571083636,277090802,927270008,181750039,543750947,593773584,844339502,108487403,712185061,804626406,115660010,891500236,287505746,187643601,691089997,277249806,931245108,281127539,28188426,704710650,617766131,444153170,103829173,595729311,893232677,330816771,270419219,760480433,12010692,300267300,506682451,667061191,676529663,913241463,831036421,775910385,397759492,943987237,599680764,992019002,800474882,11871910,296797750,419943701,498592455,464811291,620282198,507054845,676371041,909275913,731897671,297441649,436041176,901029330,525733096,143327309,583182704,579567502,489187452,229686216,742155365,553883999,847099884,177496953,437423797,935594855,389871214,746780287,669507049,737676113,441902699,47567398,189184943,729623547,240588549,14713683,367842075,196051812,901295272,532381646,309541059,738526426,463160524,579013023,475325477,883136848,78421046,960526143,13153407,328835175,220879319,521982940,49573409,239335218,983380415,584510207,612755077,318876820,971920451,298011107,450277626,256940573,423514283,587857005,696425027,410625556,265638830,640970708,24267588,606689700,167242395,181059847,526496147,162403584,60089572,502239293,555982241,899555934,488898196,222454816,561370365,34259027,856475675,411891728,297293130,432328201,808204955,205123735,128093340,202333479,58336940,458423493,460587248,514681123,867027991,675699628,892490588,312264546,806613601,165339885,133497097,337427404,435685044,892126030,303150596,578764851,469121177,728029348,200733574,18339315,458482875,462071798,551794873,794871734,871793217,794830278,870756817,768920278,223006817,575170390,379259652,481491237,37280841,932021025,300525464,513136551,828413691,710342135,758553256,963831274,95781682};
constexpr lint fact25_1000[1001]={1,394542036,81381377,949304961,476055633,378321089,670952207,955441523,124627941,240431149,380258006,842345854,926932829,28902103,482480050,923871187,569174620,842383143,4810242,659047818,114922986,562245860,784163592,979054833,463512000,910307238,551975292,2932334,18493521,377073459,194023221,108765744,784426185,955188953,643292971,746186144,427936598,471960703,370152963,631166354,618705152,645033156,874296772,78480010,713954726,236066093,310819376,576870380,640096396,546287725,754573817,987493803,845748224,904561503,582627370,180028411,316583371,883745234,486933937,556664397,23699771,837619871,985063634,27375761,406383180,111007758,546534706,140485018,641225940,132679738,600032437,702855613,625905494,217723602,617025888,412129432,58586864,443610244,633056575,255314704,431770670,34422374,426845953,176119618,178856104,929223994,926486323,643809049,209615647,565922011,874194256,207400563,820768595,289365450,991888376,612381944,304125065,503801493,396663693,947995455,316278002,977597317,137394781,252058004,392123805,305801719,981998467,806981115,896934357,891982724,540313325,831195481,92148431,326450513,150675325,84327457,342587370,521529501,718246873,640403361,141520688,988789755,382807340,262109138,236833464,425407412,285083097,732224644,830881391,384928645,249927510,957562011,771605162,472575149,144308044,92388461,250688679,122459897,752521260,975376491,931886515,375365740,267563706,585989520,677080248,711348609,536029442,922220897,797141943,970673934,531687955,813963658,609327556,852306692,204209207,735741647,345406257,929978250,622308437,35269880,167267530,380932583,823501583,931701072,317095947,660974339,627339091,492947796,714132281,146777702,981111468,418040857,697422029,346774909,672853785,405922560,159657576,656923368,292410081,897088447,873884399,596607475,231612018,504123916,822646458,175528246,67575959,261881632,557019575,673981255,712137642,220141481,513809847,733191425,572317455,353415336,243003661,495267690,409789393,313670168,848889593,16972966,515722940,335185201,713896686,16456946,935731364,917319626,371350486,790435871,688752131,161887054,440103215,280771221,408113620,427004481,135564804,405698853,345027958,73346264,128986216,920342395,798619907,892286805,276322430,361521789,691973617,798375473,404934254,900956063,954309016,510191443,261954165,874316444,509357875,648391863,963128167,277166197,909281094,611820107,991796616,435412005,749023821,281189889,532085394,205111813,742194651,664060534,277608673,289980198,917737496,650779737,626204812,750028399,527856261,472457022,77547714,754534880,704345605,99094151,817553787,404575001,491889135,450682287,857424597,848829191,889081318,917823798,417332259,1753498,666199132,80807832,338851350,594510900,268275627,344834495,787969906,843757880,535958037,648337521,759957935,850408224,779451541,796792711,267322084,550834438,146144395,749667478,22677891,224694409,984117008,280619613,679538444,359286631,910044977,563796207,841768345,351859462,551581203,327595525,513237472,736916707,906983147,930166474,901972667,963467109,142996020,475771140,931659056,239027410,341062240,630376917,539611682,175368122,419045727,150362101,50508453,742336359,426506652,669699865,396451918,808906433,775284472,920888815,456421925,303995862,489481017,678684767,899977943,500758059,758277410,100000583,341825957,88375496,880274927,507193159,196368584,395467404,653594953,670849541,903057089,24235344,897987357,652982553,129694460,948131155,670188429,430378909,819700741,1003897,563541739,519654283,395761989,818456431,403625268,903035717,871900983,615210286,107498077,868777209,469873642,79720798,734292293,271364330,506523442,689494396,904188616,987479278,122715434,840068852,928165368,472007491,202804111,303006774,698909508,335834042,761284997,590121382,911619929,328128784,603340045,88330564,317637464,879187394,26159510,263915178,930542998,446495646,4846156,241629532,845676110,900376563,846047475,2550063,40905519,636924062,439817034,847157082,604425413,385862251,59410897,98885620,572820589,864766611,980452564,94172068,182966575,515130672,714243278,128841043,69751099,420059384,444148243,852396698,354452846,547908634,487127922,792982112,790006614,759190399,636384703,643311710,69346990,433549526,497500359,176597303,990003502,592024114,663607325,277266819,517749586,368679278,954913711,104980417,173374703,833690059,968339734,517703335,405099978,984872432,801536555,124446946,105125199,758031001,392132392,238241135,803877873,488624158,786626312,535151224,6874500,207496047,272270308,908712528,426149992,308125124,914734280,703886226,774407222,922230599,643948419,532788058,688355107,505682691,80507337,430573436,897800470,876016766,8397524,193126632,61726734,137513887,575468876,402344916,221695109,63825651,118292122,329941894,709224569,475750163,623427816,101894030,771034741,411433378,498183281,611020408,122358050,830062049,526331188,70200329,537650984,399882040,117041529,824968430,729530433,344968648,785354911,399550135,643499606,939224322,668655281,101203818,125189328,8844644,827028103,302756265,368705036,568605858,326474511,370388977,74599032,762881981,904530267,667677142,151354233,827029146,810096936,249480652,693673251,852496258,959282046,877746040,288383491,891471820,437363792,760451719,393748715,601030814,394373871,920361880,450137551,608406548,483358036,305465862,278341178,302037350,182879590,276369445,755214486,837386490,370804464,160363075,666830889,772100306,593080848,644559267,744707551,339384819,538440452,709778542,109529229,708673056,415372860,736368596,78602915,902549869,414136264,636234363,194034675,193214455,926711819,294136129,384475182,35909212,514461781,99088537,858579188,529527722,93875384,874377336,962845819,123165455,40408737,256567917,636871223,233322759,736607879,279942254,82446242,951529163,655468118,998540187,649038207,839059481,641533685,470698632,311721987,556033550,365657551,640442925,802523729,761566843,684021438,927041312,132293884,978339345,373234462,512047851,248793836,912572721,821061884,127751849,254400246,313139726,183694648,916896515,297125035,434873055,320210087,788362766,626935840,23502453,592705373,974629154,72392368,61648424,550891006,599880617,331369386,305335839,739553450,851329753,704799511,95233172,312603769,619186402,998529045,661703867,87763289,485732262,258872874,58177854,806595488,836282807,35934019,918680324,926893650,266581865,41532883,105064512,185659870,600540966,768476205,415880232,316856728,710325129,655850804,711071981,162458821,554821725,466228663,653950240,326212641,648144890,733553226,274485069,216789205,724794209,898137064,357152543,491415718,544932756,530339077,745253373,61050961,284086406,238574420,745425668,680667742,888338474,735684995,750139249,512240716,598034325,531737954,521083533,596767696,150719476,509636960,411738146,284569221,50352323,894686879,352204584,687176440,830991917,537694332,7938847,836947036,296129801,788965265,807419827,221420352,878399227,15448253,148598213,92583981,109027412,809179560,857196724,372089098,270690005,949960092,192833010,840843271,775003665,756161293,996250657,827678339,736280946,469389589,824905750,834887063,360293995,350815945,232682568,477807077,655183947,594412850,421916622,900875505,437195409,589268969,153441245,784901680,719283552,80878707,505457109,499565399,256915528,787587190,294965083,581096127,453426643,653594065,317524023,636394817,41435877,160588207,703857873,324138816,516064667,577591,927520095,150593772,997890788,447195348,854587001,953480592,420848115,976566250,866809969,600406115,380751997,55887223,594457022,132608818,679035184,135639170,918542649,352467576,85581818,481942080,146250024,830096397,256088852,357717960,264223163,958649867,689715543,691213144,234732711,65456149,114402950,501448796,538690267,227811941,398082174,325845214,252498273,18555554,3021322,524947326,342999241,943301357,347138607,821258455,649767520,472946534,137322215,914874045,871161765,42484002,529176004,559028912,579422011,322910030,789210027,704559276,289878193,657637031,343476959,774335845,695524154,885442953,993061074,265676319,81502159,525163535,881463644,329317978,622014720,332893256,73526542,377654335,192122497,597181092,249092018,245127751,282648629,777651296,474165795,851310268,53281860,379113429,105568163,675242329,412161477,158041983,309817953,110318873,457967404,730982814,697745189,550236169,878461012,794971881,296940962,899188802,206106426,377499800,639016034,326174429,407970790,988397072,433569262,179068346,319442533,472582646,25931230,208567560,189931477,111515515,25705634,104037153,876934305,711032879,779875145,380240545,743903481,926718979,215094114,75130421,59382393,72770198,878066821,876347680,490784515,429926700,361392122,610149718,319437878,879417925,195623948,194005038,150975374,26858547,743203917,523778724,733873010,504042117,678869605,260317622,871614691,387430452,270477086,454785043,551544843,779266987,486390465,8776359,524288430,175466719,79896912,109934002,671092984,399254694,750657678,543990366,63635721,749919194,565116483,219243946,230007392,99497024,150110558,763841620,826764945,410373366,208446382,375427739,479082443,149946821,634945295,684332371,65062161,287811497,215711761,778333904,22390457,429912620,209564127,760369580,105680560,16152199,434728117,186996607,534425705,265461552,472649692,491091722,504331710,289901154,737262214,941261180,765392787,408836950,515906673,726578159,158332356,663635433,64737077,985478293,432336285,926552408,954075598,297877046,383830551,10480834,556392121,697057810,641970925,29311702,504752386,654275672,929173421,752239366,943458840,10159057,4562827,41894183,141673476,276964149,480549378,667475112,824379123,347548923,730168622,730618908,484597605,379064912,109741545,295002056,983691046,367057401,305671425,522319725,301920498,157211639,699770811,572688210,784948570,795222092,53619525,414766808,748040515,732654565,736353193,947664953,385208709,269924335,951370595,914341604,516442379,261036062,649974346,23513056,921883800,861363444,552823396,679489794};
constexpr lint fact26[1000]={1,26,676,17576,456976,11881376,308915776,31810120,827063120,503640973,94665207,461295368,993679491,835666591,727331219,910611568,675900607,573415663,908807140,628985479,353622342,194180829,48701519,266239487,922226620,977891959,425190759,54959657,428951075,152727873,970924677,244041427,345077060,972003504,272090929,74364105,933466723,270134630,23500331,611008606,886223651,41814765,87183883,266780944,936304502,343916884,941838928,487811960,683110876,760882657,782948949,356672534,273485821,110631297,876413708,786756254,455662464,847223987,27823508,723411208,808691282,25973185,675302810,557872941,504696368,122105477,174742381,543301878,125848730,272066959,73740885,917263003,848837917,69785688,814427881,175124759,553243706,384336258,992742645,811308595,94023323,444606384,559765907,553913484,401750486,445512566,583326639,166492509,328805206,548935300,272317702,80260203,86765264,255896850,653318058,986269396,643004121,718107034,670782758,440351589,449141237,677672085,619474091,106326254,764482590,876547207,790227228,545907788,193602390,33662105,875214730,755582826,645153343,773986806,123656816,215077195,592007035,392182805,196752860,115574325,4932429,128243154,334321983,692371502,1658926,43132076,121433969,157283173,89362470,323424206,409029300,634761730,503804868,98926477,572088388,874297990,731747586,25437103,661364678,195481509,82519199,145499160,782978139,357431474,293218261,623674737,215543050,604119265,707100785,384620284,127314,3310164,86064264,237670850,179442058,665493480,302830361,873589337,713322608,546387682,206079634,358070449,309831611,55621830,446167573,600356821,609277241,841208161,871412039,656712860,74534241,937890259,385146566,13810646,359076796,335996633,735912402,133722319,476780273,396287014,303462294,890019595,140509309,653242013,984292226,591597701,381540121,920043083,921119997,949119761,677113618,604953949,728802569,948866668,670533200,433863081,280440029,291440705,577458281,13915201,361795226,406675813,573571068,912847670,734039259,85020601,210535612,473925877,322072718,373890612,721155849,750051948,501350515,35113299,912945774,736589963,151338905,934811509,305099066,932575667,246967174,421146482,949808462,695019844,70515818,833411261,668692639,386008495,36220800,941740800,485260632,616776348,36184936,940808336,461016568,986430691,647197791,827142454,505703657,148294991,855669745,247413216,432743574,251332847,534653980,901003389,426087953,78286701,35454212,921809512,967047151,143225751,723869505,820607004,335781957,730330826,988601350,703634925,294507924,657205975,87355231,271235992,52135743,355529311,243762023,337812556,783126400,361286260,393442697,229510052,967261317,148794067,868645721,584788592,204503287,317085427,244221046,349747154,93425941,429074452,155935675,54327522,412515565,725404620,860519994,373519690,711511877,499308676,982025492,532662617,849227951,79926572,78090858,30362294,789419644,524910604,647675613,839565826,828711329,546494407,208854484,430216549,185630197,826385094,486012297,636319638,544310476,152072278,953879207,800859214,822339424,380824877,901446739,437615053,377991301,827773763,522117691,575059875,951556652,740472784,252292251,559598484,549560486,288572538,502885939,75034323,950892391,723201998,803251822,884547232,998227878,953924653,802040810,853060920,179583766,669177888,398624969,364249124,470477161,232406102,42558610,106523853,769620164,10124124,263227224,843907782,941602185,481656642,523072608,599887717,597080537,524093857,626440191,287444854,473566155,312719946,130718540,398682019,365732424,509042961,235116895,113039228,939019914,414517596,777457426,213892936,561216301,591623728,382216823,937637335,378570542,842834029,913684607,755799621,650790013,920540226,934045715,285188422,414898923,787371928,471669988,263419604,848909662,71651058,862927501,436114872,338986595,813651414,154936617,28352014,737152364,165961331,314994578,189858972,936333244,344664176,961268520,992981352,817514977,255389255,640120588,643135176,721514464,759375938,743774255,338130497,791392866,576214376,981573678,520915453,543801687,138843764,609937843,858383813,317978984,267453528,953791686,798583668,763175228,842555795,906450523,567713437,760549264,774280731,131298866,413770495,758032800,708852667,430169216,184399539,794387986,654087496,6274777,163144202,241749224,285479782,422474283,984331288,592613313,407946033,606596788,771516383,59425818,545071261,171852688,468169860,172416276,482823148,553401764,388445766,99589846,589335982,322735427,391121046,169147126,397825248,343456378,929865772,176509904,589257476,320694271,338050990,789325684,522467644,584158653,188124873,891246670,172413259,482744706,551362272,335418974,720893268,743224842,323845759,419989678,919731558,913020347,738528861,201750253,245506543,383170076,962421913,22969563,597208638,527424483,713036467,538948016,12648318,328856268,550262912,306835614,977725915,420873615,942713920,510561752,274605461,139741937,633290341,465548754,104267520,710955506,484843030,605918696,753885991,601035633,626926353,300085066,802211667,857503202,295083098,672160499,476172855,380494146,892847733,214040897,565063287,691645364,982779345,552262795,358832572,329646809,570816978,841241330,872274433,679135104,657512585,95327091,478504352,441113068,468939691,192431882,3228897,83951322,182734358,751093280,528425147,739053731,215396873,600318663,608285133,815413353,200747031,219422771,704992011,329792160,574596104,939498606,426963588,101053211,627383472,311970160,111224104,891826690,187493779,874838226,745793722,390636639,156552544,70366116,829519009,567494087,754846164,626000131,276003294,176085595,578225442,33861387,880396062,890297458,147733747,841077401,868012279,568319100,776296502,183708912,776431684,187223644,867814716,563182462,642743914,711341652,494882826,866953392,540788038,60488890,572711133,890489360,152723199,970803153,240881803,262926836,836097694,738539897,202037189,252966879,577138812,5609007,145834182,791688711,583906346,181564891,720687138,737865462,184501879,797048826,723269336,805002610,930067720,181760552,725774324,870132298,623439594,209429332,445162597,574227445,929913472,177750104,621502676,159069464,135806036,530956915,804879699,926872034,98672716,565490602,702755554,271644278,62751179,631530647,419796710,914714390,782573979,346923314,20006101,520158626,524124185,627228719,307946582,6611076,171887976,469087348,196270964,103045029,679170740,658439121,119417027,104842681,725909692,873651866,714948362,588657286,305089331,932322557,240386314,250044122,501147130,29825289,775457514,161895224,209275796,441170661,470437109,231364750,15483458,402569908,466817538,137255904,568653483,784990460,409751820,653547250,992228388,797937913,746385598,406025415,556660720,473178622,302644088,868746239,587402060,272453455,83789781,178534292,641891564,689180552,918694233,886049897,37297161,969726186,212880661,534897151,907325835,590471549,352260169,158764331,127872578,324687007,441862126,488415199,698795090,168672214,385477536,22415866,582812516,153125311,981258065,512709515,330447299,591629718,382372563,941686575,483850782,580120248,83126343,161284904,193407476,28594341,743452866,329774383,574133902,927481354,114515036,977390922,412163797,716258652,622724826,190845364,961979436,11465161,298094186,750448787,511668329,303376463,887787989,82487553,144676364,761585443,801221385,831755870,625652473,266964186,941068794,467788476,162500292,225007564,850196629,105112200,732917186,55846703,452014271,752370969,561645061,602771488,672058583,473523039,311598930,101572124,640875210,662755348,231638929,22612112,587914912,285787607,430477733,192420981,2945471,76582246,991138389,769597939,9546274,248203124,453281182,785310655,418076890,869999070,619975666,119367204,103547283,692229344,997962825,947033275,622864982,194489420,56724885,474847003,346021994,996571788,910866313,682523977,745623283,386205225,41335780,74730273,942987091,517664198,459269057,940995405,465880362,112889328,935122514,313185196,142815040,713191019,542966368,117125470,45262199,176817167,597246314,528404059,738505443,201141385,229675975,971575315,260958015,784908348,407616908,598039538,549027883,274724860,142846311,714004065,564105564,666744566,335358597,719323466,702409990,262659614,829149922,557897825,505343352,138927061,612103565,914692585,782007049,332183134,636761428,555797016,450722318,718780191,688284840,895405721,280548585,294263161,650842137,921895450,969281539,201319839,234315779,92210212,397465498,334102878,686674772,853543953,192142624,995708196,888412921,98735785,567130396,745390198,380145015,883770327,978028348,428736873,147158621,826124125,479227103,459904594,957519367,895503374,283087563,360276589,367191251,546972463,221283940,753382405,587942397,286502217,449057593,675497341,562930747,636199324,541182312,70740014,839240357,820249135,326477363,488411382,698695848,166091922,318389944,278138488,231600639,21616572,562030872,612802574,932866819,254537126,617965234,67095972,744495265,356876757,278795619,248686045,465837128,111765244,905896330,553304419,385914796,33784626,878400276,838407022,798582425,763142910,841715527,884603555,999692276,991999001,791973851,591319986,374319531,732307743,40001185,40030803,40800871,60822639,581388607,116103677,18695581,486085106,638212672,593529360,431763255,225844553,871958343,670916764,443835745,539729293,32961520,856999520,281987366,331671467,623458086,209910124,457663189,899242837,380313601,888153563,91992477,391804388,186914018,859764440,353875286,200757373,219691663,711983203,511563152,300641861,816688337,233896615,81311948,114110634,966876470,138788045,608489149,820717769,338661847,805207966,935406976,320581208,335111352,712895096,535272370,917081529,844119593,947109271,624840878,245862716,392430574,203194854,283066169,359720345,352728907,170951519,444739466,563226039,643876916,740799704,260792171,780596404,295506364,683165415,762300671,819817313,315249991,196499710,108992425,833803036,678878789,650848395,922058158};
constexpr lint fact26_1000[1001]={1,973511947,317652281,380633091,918182171,733867795,950043445,402386956,240863790,523312705,768228473,255909794,69390238,225307811,225539109,590280118,927056552,599122390,297423730,449483446,596686855,894184246,206693682,387887485,95991609,519109884,342266458,587970345,332438658,942216112,267079619,76671807,590091796,211456949,686678655,712962202,547886782,146764286,813787354,890896303,437544625,801450463,197630296,898378148,879661185,915152533,966428332,535475764,933908165,664152012,780167973,65753572,451841475,983490335,179455157,67348513,559232744,626654297,497998179,447094302,385864507,858259201,947495294,978491551,269047341,938637341,967390321,313302791,931916028,508166856,922483125,807056023,789056063,806196175,494311511,129594811,894572352,31751282,143194290,81373173,526273546,834719002,146654489,123290811,623643485,66344642,154326867,715906720,978977667,999362520,793787025,801759653,354416226,806453033,824243659,658616772,548376047,466179106,955962907,338860801,834294302,625657746,200494460,751027370,101050606,503972085,267639601,239960718,148465578,889529282,171560415,465665221,772580723,597581775,199694974,584016291,551300753,678711036,481614013,216114367,720113137,153876580,944896451,287324258,867915161,301448063,676265645,144692055,192464984,991595135,752269924,256375757,613574859,434083316,161279215,506230918,164024445,689786130,729289879,62877578,952939862,935642983,701200596,671130348,198793707,398221200,34964749,637086103,196696045,394747979,920562023,71741934,360994095,818928538,901586523,250753566,545071872,651216959,237736778,4209622,280667215,21087410,422585355,839992969,993298355,759032529,970633360,502289765,660426874,458329549,491296887,670425294,711318222,388460760,153501404,629225445,775982034,468365773,389672327,94336028,647665773,264917490,678950657,386233182,372807056,401373192,882333666,78571189,646065053,232023890,323267641,389072671,818332207,552783811,349698537,234871632,162835138,124740029,650575114,466488471,477338365,836084476,389667232,51000783,209305404,939332425,540822158,329843830,901488668,239846722,681332205,800357883,522022516,371632588,780007509,445783662,696579895,75603650,996599165,706315953,788941400,6598689,531070169,597786993,373035946,549362233,312422800,186160318,361714102,230445615,765871506,738786797,130839383,596992794,163652627,427210267,894299784,829238829,296872756,681751728,450040287,958971645,706750393,316235549,862590329,769966675,657363968,895663999,420718874,300363749,50355431,331682866,405919492,215998620,633572495,855565049,806820873,456321460,872841897,623589403,593595538,883786085,317223353,851153244,961551153,544554195,910557595,959016635,8939330,492257702,545234544,785550802,369229899,349955348,809742593,762199997,888788580,930441202,787470961,82784386,231918426,860007930,509143794,730303984,388979312,717108436,853689524,825204620,666169290,999841331,19379139,207012872,664075270,526854262,794575716,907376430,847816694,697525500,833802686,579671552,257811505,434672189,58032021,356590832,712651880,375584562,656309829,992548885,765221765,117258780,421574906,673544554,565860983,435556940,720623013,527890562,218189859,963872449,917258844,874672216,24437630,594833342,857395354,578501940,10427358,517587927,30317680,478720599,139214720,169569496,47223209,815371424,949985816,882786014,257690183,19065011,848266312,189047783,16081583,67582810,486282366,602614779,688695939,773707200,407426021,185734215,3465273,641502143,865032456,563915864,863975426,237781671,875740372,644418328,782322064,374499518,366683282,293376183,116521782,68682132,579390879,741023847,16631168,627229616,413913712,838467684,833612641,502999014,30491436,19399453,128565798,452466333,707410712,747066846,697659704,30223324,786092466,740798495,153886505,50902785,986191119,651316890,259431447,314080032,325817677,882975333,564694148,630830691,923916914,518262529,132190643,341287738,981872077,694154589,726000323,18969000,993377171,76110178,52637397,479780021,105909834,982055389,114933854,200527385,631657974,802329325,848405536,415408159,836941959,328673243,479962839,611790655,536356736,694877190,427490243,873265136,843641540,426412596,651460141,818374952,320667035,396354836,396232537,859459804,303417721,257347369,496802291,199969843,837503118,315515751,915068747,295007952,721646203,209968876,853311123,933526519,726228009,58582057,970122662,901460956,276960304,901382754,696213927,857877879,427439907,176243958,498537047,879278140,34024204,849304412,934154269,846679405,276583965,391325311,755271483,782046759,669806774,106074734,100991958,975704094,596793923,870596018,600877720,11389395,23988081,275634926,593123685,354273772,136525855,986522842,952651019,826304006,64041970,467996236,707832031,824193826,638101512,982367784,377488079,184155749,505288563,319631018,476619762,235331411,509181651,971823585,751296954,343933553,475893751,858125461,460614893,162727985,399813343,255947380,489174050,503857904,700797293,385117747,81806334,931796204,413446078,555831015,827879302,529368299,832143640,489354697,515316579,632001419,610626304,935289909,946431572,910453639,551762717,148646848,398926689,134218,825587812,653552820,811850229,573764626,267019824,930208426,572082359,255939924,984148031,88467344,700490663,418898693,363565118,407919865,216323142,675425347,8378129,617913707,768732932,115743788,620289523,12416482,482097303,801686581,889923001,319138278,203212798,251487111,361235182,892052020,736519896,940121128,328582215,635071642,360158192,267591724,408800462,910314604,319159036,364067168,77489951,542882853,517424218,364101868,941814391,76956392,485589462,285212541,154122629,584267130,312864921,258667035,104859016,112093624,382654561,99908779,285845990,319121142,102605780,962038003,832633467,922479902,178072801,995761568,25752464,193195091,873708088,904570551,138601173,839204559,444536767,525922399,37458708,501918983,956221047,711100267,593537649,251080687,744457267,382302583,314226198,672066821,845954969,180683802,645097628,443290015,567472351,423589634,437770436,506175670,576353084,36688285,512425514,334649266,225285510,935761039,626811125,428553577,218670251,311841997,530764810,965243917,390841053,810141174,124831036,51715564,47423075,752808522,840335746,495619288,654194678,238753756,230115508,659832718,497996743,483948196,237192183,269144347,437906964,144345302,6669869,110972564,86990296,836263675,755836521,21705241,278102050,265041688,914897807,163952656,241112156,789848798,794099061,573527348,300876509,32804905,714148273,828294441,302704931,681502609,129013234,740935137,772417325,693579359,452647464,898648438,421973898,149583010,283874548,992738129,58830209,905103553,949743886,139096951,641885803,456003990,37191227,554646248,7041641,591999180,309975570,560780364,175524048,517678164,827264197,467400548,327206858,173554045,74977070,885117786,141480211,708452099,425920714,651297858,380185839,755910362,116880473,40019179,592917477,404112018,695423928,398643337,444858803,417091949,506706759,59154213,667771387,558676563,782250033,335936022,555390738,911390288,537025447,837910521,483108,406399099,357095128,890039626,149162401,400225101,585414249,356178476,223044779,552517428,318536125,67894328,978865050,5194652,747108059,45250561,433588540,817562040,782347031,47110125,191127492,559692659,370624671,545791643,313916154,136083970,662834007,175443889,774064843,138249752,299672656,763076876,65386422,543002400,949337567,741072757,485625640,184567,178264203,128136931,307214833,127568695,776371636,667285893,352788183,506817745,255347633,623583668,502618574,147967297,386461749,76439414,229776284,45435256,221381084,605190652,810597169,701995889,902576230,832538658,228942858,883174291,553289558,92911489,921905982,205361587,999926197,83694915,85303512,471749955,974432894,218430219,293815411,818985547,843784553,289514332,56804791,298237083,306569074,30586500,958481246,424795403,956375869,776703654,154642371,627082979,543540744,261264740,939438379,24932560,859389312,499730172,312911861,909139343,702824786,29260095,853459608,853964950,324842125,362703566,248829238,260238748,476903660,328126171,355821722,944335876,831454822,941740062,907954356,709360290,208389646,592012106,925314411,534135828,238823874,940337434,802315965,728884658,580963707,578881794,414954552,6290267,31454299,646662208,754665316,969800387,340937697,888817633,372839405,539126251,615899803,178345757,920906818,121158165,278454815,204621196,521020373,195359353,772397657,660739792,867628492,607067052,615161083,437891988,829529090,846142919,749841655,390893657,432242685,905303797,874694374,102008259,134026467,925366694,658904543,52915141,580094880,120426316,538542060,702050945,575955076,496398971,364254262,320427003,378328250,684453274,738000440,202091000,504010993,670208338,454823353,820666543,521188475,499528404,755764533,844155179,125857491,250278587,817234545,489496006,514072240,757863039,491705914,338783512,69949306,598683394,449730094,369709706,193439891,596665476,182415017,118625720,833091962,279495210,159630402,363597980,957298242,905508298,39974226,310670320,981224185,96203975,355799299,886101098,114407813,6000307,509278139,191908190,384371532,869360879,36589041,293433751,251894377,675066738,865020183,651873969,317557999,727888532,26034565,885033342,899203199,879423103,245409304,676592679,648538656,287802357,953005869,538278799,975165794,119392110,648930662,809426685,552199901,992704875,892771289,696225120,377024371,909396255,602401701,711505111,61450070,870229658,766471392,922536867,285745464,57822061,789629505,440199978,652357628,129036136,111389259,644905862,952568422,660580510,938771879,316798982,615584817,546354516,900224144,27195697,751164714,124963432,138548353,938523966,51171793,486196514,655525981,605258424,661807414,632233125,168238903,874196081,916797453,227078122,121880693,913573108,870300980,585069295,518363757,798871737,646163721,708138108,438309955,694632567,16146263,819874008,235673624,950768326,711100503,342355531,217018478};
int main(){
	while(true){
		*c=getchar_unlocked();
		if(*c=='\n')break;
		k*=10;
		k+=*c-'0';
	}
	while(getchar_unlocked()!=-1)n++;
	fact[0]=1;
	for(int i=1;i<=n+k-1;i++)fact[i]=fact[i-1]*i%mod;
	inv[n+k-1]=1;
	lint now=fact[n+k-1];
	int b=mod-2;
	while(b){
		if(b&1){
			inv[n+k-1]*=now;
			inv[n+k-1]%=mod;
		}
		b>>=1;
		now*=now;
		now%=mod;
	}
	for(int i=n+k-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
	lint ans=0,irem=0,iquotitent=0,kirem=k%1000,kiquotitent=k/1000;
	for(int i=0;i<=k;i++){
		ans+=fact26_1000[iquotitent]*fact26[irem]%mod*fact25_1000[kiquotitent]%mod*fact25[kirem]%mod*fact[n+k-i-1]%mod*inv[k-i]%mod*inv[n-1]%mod;
		if(ans>mod)ans-=mod;
		irem++;kirem--;
		if(irem==1000){
			irem=0;
			iquotitent++;
		}
		if(kirem==-1){
			kirem=999;
			kiquotitent--;
		}
	}
	*(c+14)='\n';
	while(ans){
		*(c+cnt)=ans%10+'0';
		ans/=10;
		cnt--;
	}
	fwrite(c+cnt+1,1,14-cnt,stdout);
	return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:172:17: error: decrement of read-only variable 'cnt'
  172 |                 cnt--;
      |                 ^~~