#include <bits/stdc++.h>
using std::cerr;using std::cin;using std::cout;using std::abs;using std::min;using std::max;using std::swap;using std::map;using std::unordered_map;using std::unordered_set;using std::bitset;using std::pair;using std::set;using std::string;using std::vector;using std::sort;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...U>void _(const char*s,T h,U...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}//break continue pop_back
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);std::iostream::sync_with_stdio(0);cout<<std::fixed<<std::setprecision(10);cerr<<std::fixed<<std::setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...)
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}
const int M=1e9+7;
int32_t main(){

    int n,k;
    cin>>n>>k;
    vector<vector<int>>a={{1},{1,1},{1,2,3},{1,3,7,9,4},{1,4,12,24,35,24,20},{1,5,18,46,93,137,148,136,100,36},{1,6,25,76,187,366,591,744,884,832,716,360,252},{1,7,33,115,327,765,1523,2553,3696,4852,5708,5892,5452,4212,2844,1764,576},{1,8,42,164,524,1400,3226,6436,11323,17640,25472,33280,40520,44240,45512,40608,35496,25632,18108,8064,5184},{1,9,52,224,790,2350,6072,13768,27821,50461,83420,127840,182256,242272,301648,350864,382576,389232,373536,332640,273060,208548,136512,81792,46656,14400},{1,10,63,296,1138,3708,10538,26480,59673,121626,226787,390144,628744,949472,1355952,1826464,2341600,2833632,3282464,3584160,3765600,3719664,3531924,3093336,2642364,2010240,1508544,963072,621504,259200,158400},{1,11,75,381,1582,5582,17222,47194,116457,261163,537459,1022981,1817652,3040352,4810720,7230928,10360160,14178912,18577792,23327872,28132048,32571504,36310464,38903904,40028724,39552156,37457388,33941412,29314944,24179904,18835776,13777344,9452736,5716800,3211200,1742400,518400},{1,12,88,480,2137,8096,26860,79376,211811,515308,1153268,2391936,4633331,8438664,14557048,23874176,37407760,56117824,80906752,112162240,150052400,193572736,241706624,291576384,341323776,386160048,424359540,450394992,464545584,461528208,446428476,413557632,373573440,321120000,268449408,210332160,162330624,112550400,77788800,46540800,28497600,11404800,6739200},{1,13,102,594,2819,11391,40344,127508,364587,952559,2293742,5126898,10710633,21042989,39117852,69175664,116857024,189256368,294745440,442503456,641759376,900689616,225195321,617201401,74227554,586823330,140227131,711888699,274217080,795069832,242715461,585116357,796764497,861974465,769155485,525176285,146566301,650715556,73773796,455145195,828946802,226153586,685663993,216281593,828705600,536385600,309484800,166924800,87609600,25401600},{1,14,117,724,3645,15626,58741,197280,600215,1671266,4295107,10259436,22922995,48184950,95816051,181136304,327071752,566117888,942525072,513281017,349163810,532145419,154557773,309226767,88509354,563257605,789064441,766807654,474675580,795689314,599134613,627066840,658988947,307608398,337632800,295701193,44870369,150212311,705302359,336038622,452522163,797367958,62674553,57993322,777736994,845298906,452367755,90655804,810196653,976943895,564798323,582118351,994783972,869862386,697759993,660441600,381024000},{1,15,133,871,4633,20979,83313,295803,952299,2809009,7656027,19414457,46086247,102967901,217634463,437195525,838372452,540635289,722168530,638311860,640827391,196046908,898688562,478199884,793020369,808862771,562236075,94791602,385333320,237794527,197694759,398043392,504456766,579736664,78137089,793367253,961295251,280517488,179779783,947563092,901772777,859566930,199212409,920781370,362900807,735004334,297264154,482748036,653703312,140400674,623159781,320434095,373194802,13313867,205909676,360223815,570584277,68075848,372652149,961247580,23084534,261139053,151302323,715359965,625702393},{1,16,150,1036,5802,27648,115538,431844,1464468,4554040,13096378,35069940,87969166,207781760,464351910,986188668,998611836,879505923,237509223,15110629,621334822,88677622,257578542,963016850,235638961,442107823,429101453,483004748,329733855,718448185,266304376,413950543,256286771,626720357,318467482,59069608,81901162,352730851,104241055,503595237,956355036,534522134,457799859,108929893,887297322,424614770,265024591,876853471,515703045,692038809,210906163,20070317,468291405,145357835,797577421,232358134,747771239,343859985,833879609,78548665,289896769,449285934,313197004,379603290,397630660,609910102,442642726,627950853,722186028,705163253,998661511,771071664,636940611},{1,17,168,1220,7172,35852,157132,616084,2192506,7159090,21631676,60902460,160707468,399489140,939796228,101060910,481320121,151453550,952463061,931694473,957528293,554162053,990142499,644946993,651797781,791594351,556120466,271969917,107619398,710253075,280526462,615698879,99748930,775178221,257586036,645364809,806795120,340635512,801741075,790520661,68328385,331513794,351728404,931812262,91105169,176869824,445724501,370449983,359815736,918724628,869062973,659791249,657727222,395793733,32692523,78858425,151369211,628504487,842750087,152091477,889718876,908002421,944598446,656459208,712920845,47550280,92244967,110652620,951703750,217822851,901098263,655149074,861896271,859184013,992613245,768042116,807916959,335381553,909568095,153171069,827990317,681893483},{1,18,187,1424,8764,45832,210072,861400,3206786,10957868,34666130,102239488,282743580,736889224,817936097,262532028,534038590,412279142,965109380,86702267,846482566,945052509,644517943,548776024,679330947,152291502,882910517,188127435,636778925,902059202,132531208,193904122,893705022,246193070,652079051,958060250,148697872,504141990,371410212,807466717,514477363,565424570,560794838,11419155,215137208,665710713,791504234,359367396,224050172,509091270,125989128,782600310,957126038,667219607,386301613,605448653,296557741,618019404,194294675,222923480,765962783,743934970,24324611,512643153,214242880,286900578,228877964,91240846,430467141,533029377,904804693,373207899,916503101,83598539,560288494,363356684,68282446,152683809,284461190,124425011,167972327,428909487,373215034,420008537,513304383,874743039,487193257,97337408,532639641,184378261,955976093},{1,19,207,1649,10600,57852,276620,1183172,4595034,16384606,54107670,166643130,481442164,311240781,381378831,288429444,380463632,370477330,171662912,688513797,626045604,789881798,844990830,70546834,230422087,267733218,970080423,75064762,104073936,888990608,393490487,819401315,362017415,197941501,97730360,491049732,790022455,142301163,381999002,81566974,255547256,500580164,503785886,874661360,953064009,357278689,416715628,656421867,311332859,849655408,575613107,850236831,533549113,255339339,611845477,501164398,135987981,672393680,678611757,552403430,470027818,333312311,203812034,929380798,133842121,497262544,839881753,29703780,133717366,249364505,959337844,632980495,72879056,356819838,662140760,182352973,260787823,329159184,423643610,488600943,164109163,8143787,184454683,684285006,693158498,382122550,488552031,777204359,564238497,598675373,603916585,720234840,93182262,238936257,486420235,352604922,958291193,880928218,736558676,163545641,189347824},{1,20,228,1896,12703,72200,359348,1599616,6465450,23997032,82508708,264654080,796563486,260832418,76986106,528774007,854313906,307546108,722735109,61004626,805619536,18191861,511411798,993782454,401030744,633897378,70862649,96855526,314416445,92910833,135520920,492052755,24334887,643976444,574388511,317610455,122930943,637889505,255461238,950861369,48876234,149504663,198682481,942670278,866921314,563621302,960474580,980132644,624295523,399490883,351714973,945626033,827908349,157456205,481861323,472454109,343580291,683697065,95059407,841332348,464714941,596887160,38681949,757883329,590303711,64921694,730086270,15240461,714742087,32874447,175996750,277466516,788882909,11880203,95097385,778398376,531252352,479554466,557013590,609738833,798714176,859324339,721484640,268442938,861267595,806087188,31691029,950412807,580575404,849451646,691790951,264837637,967322620,365040170,622467624,456436788,658680316,60575186,387550026,215002020,31349904,449373833,559514745,640364153,807042078,450172023,562637973,109112418,545193132,195217263,976304283},{1,21,250,2166,15097,89189,461164,2132144,8950214,34503182,123236828,410729140,284813823,790835929,594736274,153822108,374418504,157537842,147846917,133568389,483576696,508616649,656867821,84463125,640047601,955370715,182167616,49108700,229345632,795610484,502493987,857101031,142485158,996679960,742503997,723858587,317526153,365342533,250775491,442738912,408346120,881242865,135363327,231979623,347291745,824934645,995772018,164592917,354883487,450805745,963969802,171006181,92161176,169883419,961669090,26844445,393784092,571606470,464707158,34144520,652396373,745405475,202923498,135935314,703695236,776259115,48310283,874186699,219390686,510394758,751965065,418424556,8781061,736058807,674014147,674780706,590530540,4352977,803825827,167292329,541083402,260679638,665083995,939990721,816665296,886017767,669822229,694816125,643235536,937314556,115942268,261159535,687177905,12245758,694615643,977706180,217949106,118952653,898868241,856650616,42954342,330321980,535121720,982503521,719423135,714354007,18745970,333448882,302037622,935654015,778423936,317991952,284756555,504736970,155871365,118263505,797065125,640838446,258037348,34344762,502389803,911086550},{1,22,273,2460,17807,109158,585339,2805752,12209406,48792492,180680070,624410736,25734764,199973794,977710523,571365953,412869707,328237414,214863466,633048751,257394955,317735309,673309005,193600985,704135816,514918834,650479735,33606857,490034801,698396427,67986999,220797055,218864611,931163713,940790978,675674698,85542051,543018292,61247584,910803604,831296179,923943160,89478028,104500393,161998091,254912705,539249258,547749719,357852173,690014841,206926249,893887199,747112232,382059625,148865046,301618706,260333115,442306036,247371284,782005651,233300621,920894203,317455792,678639547,427050277,482884001,854060466,980543322,860769666,701293636,771136168,670745480,486701027,168461356,848787800,289825171,498776317,33320170,430165721,821516580,115533370,398776967,333310602,563097053,553134182,219816464,216637272,206027601,933677337,925510467,267639197,43693887,486722546,270929495,877730912,261947307,375318068,692508932,989184491,226696206,288508969,739837562,849035543,782296408,273955665,801085382,431898190,935043965,202752072,867866169,151133676,67940990,78118516,742654574,165553271,254022475,668960857,929973305,656759571,877339826,925206924,133648890,623964326,796176354,256442424,844384225,955053908,35821657,33969824,328610099,171474448,265634834,954990510},{1,23,297,2779,20859,132473,735535,3649437,16435370,67971642,260491974,931772466,129241853,915880695,773220207,21124907,663657824,89235883,562087424,395633225,79602143,818737728,503346111,923762587,810187543,71950684,872552891,722894374,788701216,792043650,839896539,577542972,345484502,350106805,159630680,594479078,806985602,451202244,562057157,345406448,404888318,371479292,122121086,196184273,855722413,625056343,209132008,580725504,234791519,683270249,879431955,820639155,890517789,877206124,780147370,943542736,532169988,134361777,389279830,486085405,212150153,60309713,36144061,220641769,167907687,433032241,672669299,4840381,543970499,860603358,920463673,899153827,269139419,99866794,833550296,732963165,649634036,220976898,948879986,81746947,249278044,943429751,227240067,617290217,857759442,317672542,702411387,392102340,598392406,771484657,20769431,772211314,777981688,103043307,336611982,922346108,46010568,620920750,740298345,143296430,127113300,229361025,452883985,298773134,583669967,430943791,878469881,498554889,377075156,399618101,518539100,610655946,762624102,339746521,193491143,582788075,58498274,139175929,439487543,659039143,969039085,205473123,149794944,735361805,144310487,952281582,885994682,290034640,449859219,870975475,717604104,930837761,466542500,510501275,368063612,61813298,959329905,938922014,660077190,12025968,335011033,657136343,351072920,964781583,196462283},{1,24,322,3124,24280,159528,915834,4696644,21857553,93405656,369882084,367190881,745178532,541448535,237690972,408537702,191376116,678513161,493570976,397907192,9101765,658714208,122356973,514532531,911169029,6916896,782796,910119724,942560918,62371227,773940129,523667340,669757203,42568262,891666384,467022993,486796667,727294526,413613585,787453753,599953158,417187968,359849625,117069116,879478181,12380000,910899870,838986319,102687453,103327364,376800830,429223538,780159138,706916356,587575355,971169352,36010810,483798044,344462034,787276711,359714668,737585540,514856433,506547585,7966248,935961,931790046,725219981,437246235,737823353,539625329,101294921,998345360,158678756,14552916,434899855,58679632,771567929,908041362,370603042,958461645,473954165,329932246,645017860,950250115,632956030,39737256,308287817,593859369,848980890,73354610,67983312,794665532,744501399,571146358,79777328,768540650,301591668,87146707,749547055,542914952,113807115,981646049,443442346,689844336,226785366,664441023,644644459,65534356,186334852,433121661,818953887,687026114,344822747,464015963,110899493,294091084,65199948,37449794,719226153,501099656,413337315,725255533,799293560,259962068,954615054,373654234,764439094,914044890,22085466,539035590,698634111,313016212,98993468,941478268,955683335,902077766,420565422,767959775,128648986,355285226,534029655,104714136,932643222,778200211,56428536,225880543,792355687,449940761,181471652,529937629,325235521,6575392,94094707,441392085,37264955,911557047},{1,25,348,3496,28098,190746,1130768,5985744,28747851,126764795,517958180,975500521,75313899,914923483,611051644,458281681,932346365,712529240,185024083,463834094,950836649,286357381,871292163,434939852,58330077,629835295,27932676,66354549,10923173,590226200,526183672,176005584,809584977,222348292,260397896,396327746,178971085,774808076,78650222,507195902,144802453,299847298,581537053,724817078,350425193,503589319,654904119,595937600,992781673,82554146,868891604,769490422,119334199,287573489,85347169,118147346,949694675,540939467,927324362,545027201,610310429,769058023,21423,262519735,786795808,240407039,428554518,447092428,788617633,367724192,374279457,343082569,856162651,150954733,962857235,700751807,895999415,533537747,537990547,268357366,869434038,633081543,603452058,947934680,987367826,743179254,710352935,835787228,706586787,845202323,238777269,405136472,480736674,155194042,871452828,677921910,616952227,984554304,602482844,894952109,161534829,782737895,850072208,670793244,828100052,222399146,284700626,231919567,306545173,673216888,772842480,314744315,347738200,25002680,730048408,649455506,745857274,196252843,529935260,419302767,276709210,732855171,343508231,624945362,861002432,484757974,367927715,209929226,661865936,531107025,413469524,479519565,741904536,610072165,606639245,934344602,716197790,587584177,185414563,306822687,841034662,971868532,919896238,158358640,773475266,936203252,665923149,911486615,197651366,774528535,82937079,883806524,130206852,774201811,995994000,245370199,842572718,793423605,740588350,687616120,657690139,857790226,37323118,88399209,523321086,117621631,71036645,222192424,788926021,202125596},{1,26,375,3896,32342,226580,1385350,7560544,37426495,170077814,716127109,814596482,388283574,187079164,480126707,290089727,38629756,54115650,64891257,901599546,718222041,911275669,323565019,817912019,805459451,803612364,201797073,732830955,80380678,23464457,701195891,272214917,913862649,132026200,669751010,759341231,973676755,794065196,967438659,308299894,10712690,949669597,781686555,88559004,727530543,318751597,278470531,434911202,804701133,324324750,981099143,232682614,987104568,776649739,786487389,442468777,569068005,663709268,881510700,203686642,57967683,568729400,236001193,623959074,703861418,908672716,70204475,867825588,827103298,241630317,362696969,415618616,805038660,598704556,10082872,643477587,415164213,703084166,477367476,20036406,629980785,802614294,952521645,17601466,311433959,830294700,548394039,535645146,521413012,929141249,283365227,727229980,443388093,410708269,286618040,319768543,938841603,93475597,394693465,931196821,495806189,902879580,707905623,303901454,576396872,484544924,486011674,564305854,311518869,856442237,372745088,366968335,813470622,720542245,551543931,596748971,778551123,354920979,984250497,691689872,327423759,52302396,920309409,457393341,162758194,401889329,760192486,361045291,58998809,845800809,8575285,649668894,501939170,542308042,574502757,192463535,690505425,204738512,689813836,483570629,525148782,216925832,952334594,68584858,946061868,229986068,113082103,705545851,563504064,430610853,209937938,608555345,578039088,750439353,944169681,417934823,74422181,960090808,568355902,435674968,894299009,15861008,618713868,509911155,168869978,339481775,369451744,600513141,71634326,781507214,857107917,106564183,736233715,362800524,615467708,519437498,342065337,206666492,505918934,308299385,20927738,106279730,457391057},{1,27,403,4325,37042,267514,1685106,9470830,48268511,225792189,978561725,958557158,38052071,919433401,254995547,546697380,704487939,32839999,508901654,551556389,663564198,695178769,814009554,547143595,371559020,945387943,670094820,616330760,976064124,607380120,8699769,998280938,580008436,958036252,912203574,544195790,396609897,954428754,708902921,801338681,431017191,381717232,344144422,131861617,874277396,830300192,596462835,318671397,244894238,904557382,834593756,283869037,697514761,969250693,509524190,913260759,384371901,692021356,509945770,32685910,505430483,907189201,193340383,693205397,603006308,305262013,925218957,968092842,27052064,47727228,477199307,293774777,98292616,663047137,995897620,288543890,998081856,524487172,892499155,556044593,972323813,578208602,933674462,509188659,985492681,986901126,628028841,519717277,311965185,897395442,829761538,9680527,161715155,343759581,402616197,861303980,911400557,358697993,515548395,553147014,892738525,205604013,762111690,442223169,7841804,517369986,84729818,152655938,700957258,898706126,75157861,271201265,543855670,440588279,204308612,236683234,208667572,404506592,809547310,853106482,518815458,16491026,491832633,360120645,923872102,602086347,641452842,18221609,229080666,428455406,569262655,856993308,230900297,490066099,367669571,96292417,52365382,469261002,374633464,900617667,182287939,49700390,796588976,949085023,222503562,658471212,94278399,66098044,72459139,603916441,257635815,234793049,951525459,549173423,938321308,13662267,288258509,65326301,11071916,364716823,929353581,839483911,199241395,29486252,482468148,829994735,370892643,687560607,531658704,568187724,486108828,475403750,227529481,124500798,228110006,56292488,958873404,963718586,481659835,183136868,593123751,622015148,469053734,211587807,928091671,481375722,612130911,134707706,334981252,784422204,712253942,698883770,390222722,25478322,28778175,349558455,616616543},{1,28,432,4784,42229,314064,2036108,11772944,61710789,296841956,322742117,501368237,486564198,208215103,787564548,236938424,301578523,866593178,461034739,153403692,741061604,268366308,41671958,999969805,820629183,540097933,348143198,290585123,709901036,830657214,397773343,205345230,80836479,744283025,767371096,13280133,166091858,688213267,405245759,999129285,957885801,125598090,229197648,232621259,771781842,15692966,623498734,209019752,451480479,405116698,905232949,522429827,160392239,911337480,463779522,870625842,997849245,364479050,834828,300785526,10186705,265101999,566806573,614983712,685595755,48653250,344390997,673637797,896886255,108856368,31386606,486989879,489263782,517653845,976993581,117774221,829510874,294191687,233225993,831800739,448583977,657291524,649603801,456575978,536862581,855051723,994222346,302476269,502749737,322446053,790323255,357338908,887312147,181428924,536100952,55330164,160205355,190454705,365581727,201998030,826748536,400273437,624522779,849319472,800147953,80982274,447705256,168185200,97822479,309878269,678607548,912097410,927785144,334246635,662138658,715198385,260363473,461374975,89468114,651175074,575096135,130470890,71518840,879845193,486812125,128678982,647847215,49005945,59417027,550597313,85275582,589669875,488581288,579391253,238935007,307933774,801626662,991248834,831660242,2289249,939337934,170802252,112167473,712496239,45742853,482400666,341362938,957391891,147812751,376451585,832724562,418101830,38563919,274362964,819817184,400041713,313141267,806456583,999307614,670677205,585839782,845991536,831623045,109161241,554327240,822718306,173814042,363700239,22366070,479904205,190929878,554951008,774006606,279182950,109357938,401823952,575672540,860574847,593910748,547825741,217594637,989467389,184852185,331539318,325720467,383229710,654245987,146654996,209385163,560462909,965812836,65583448,508391947,709539829,955465325,214525022,394005813,531700924,773028650,417539579,326670161,406612199,165245,699092510,550837077,14964582,527720684,440459594,268905155,297293091,881879628},{1,29,462,5274,47935,366779,2445008,14530396,78259797,386723841,770080067,561338901,331351593,839635833,167817400,497149119,881282118,352201610,471630724,181160121,88806794,987377178,289689361,946592969,656979867,594487341,196240769,948508749,810784209,709855728,576276359,518417791,87667236,667014934,181628700,79050911,337053925,373883684,560120551,458872893,815731972,827954345,771964062,380463298,190074568,335845313,308369049,297128477,730684746,742600059,263592454,96421517,206168581,306386280,238588046,136275025,509837233,285349782,467079296,44733505,132275281,829959933,391862643,62600608,253168338,426879146,365435454,91732486,471304236,543190875,798110387,894371900,696428631,750022470,726550236,936549828,542410178,939184541,791578453,983635297,823881369,150676558,585328209,653882077,963087655,950795211,936066317,71868369,440124326,965151462,175368387,40663323,699428294,108367130,332044307,970432796,572024201,885659377,539317691,132218646,139253073,467726930,45351751,297376822,508633325,703469419,746467332,503668629,112630766,930570931,962347630,576196343,698904389,167199167,333129737,608922442,222067115,688206452,802821275,954540394,911151138,906746447,902608727,890863920,307268385,54404696,104370759,495676754,441341576,829087999,88911607,975336543,381836343,298727399,758323163,709721214,146811076,322114121,909574264,955852236,803216000,511491931,157225317,671670053,367885171,612666342,842261160,508147005,345029386,809990068,981225972,241279545,458275632,172983843,48836190,961296645,538132589,271432367,877708377,386417805,815731556,463571419,404450924,113136747,549319603,219464194,220054123,907114544,328856175,265047793,589592614,328159953,809008569,510434161,420313068,107873733,868895119,895337042,156863206,48004547,666506430,727609186,85858741,59205240,78940637,545962715,139572749,421355881,858507471,952603331,401020118,942925111,296295597,997986384,115737481,677010850,282276283,274892540,163700485,118592549,846472792,136765224,236032397,179431589,539549211,214067143,923131121,999465547,232088789,610013691,896204760,478686995,218989077,91096939,221616643,243944261,454787573,542927414,355318220,147354818,482630,675619041,634351197,478341164,574509037,738721209},{1,30,493,5796,54193,426242,2919073,17814512,98499977,499582398,346636279,286311246,338970899,482987014,740494022,522312682,389124982,438269373,295660905,384589942,269003911,190728878,21841107,394443500,159301748,885681179,869073529,396029106,969827087,16747334,474716791,259235367,753984455,365768194,423375006,957390875,407261764,592999097,928039310,529328158,133251022,533719572,434981329,779487889,212784950,467080112,287628298,91658981,576061624,322787361,682746649,234833733,676878118,220869554,982232103,879428014,742840902,65876039,230084790,68776407,988541480,113769367,288661011,898604342,790158821,811679832,416532461,643426286,357304561,904850873,143689492,643378934,217587561,816799579,741653213,950522177,519192837,195766899,875531753,913462122,931740864,147485151,73473743,881407231,943949423,19375017,95185407,658198820,654223830,78841384,487272636,810454297,156111172,108214345,594083015,721613382,413639222,199581479,219296986,983776208,50034813,434669652,336761553,553659069,443256837,867959007,649693919,829394710,511124003,801382432,809258820,440312724,549557631,57091967,619973166,38255131,989252595,296849831,126449228,992478958,948085171,398912012,308493194,585304989,581850817,704472537,457658359,706849064,974235300,322942033,801441410,806760539,930211369,674605925,140615032,804334982,654022727,747554604,304695097,670935186,973200118,899755340,43016718,33443894,486649937,183173093,28680647,612676891,17478829,208078434,467131016,651933212,464433186,3993644,959280435,310671435,524438940,540166082,143663989,984026973,596317769,299039541,925611762,115137245,238184581,798462400,902062936,499673997,696053154,121959061,376644235,378356623,996412950,115590297,517087995,817795384,731733847,61225249,930096903,292653780,149516053,503527083,233497811,781589564,87992011,514696635,495015483,151617728,478098704,773499685,621536652,787266199,440325002,249898342,747360642,671517137,216648293,686506084,544204132,949750238,249236969,319054830,756596931,233403453,594672369,158463779,809106181,249481644,610711719,262167344,179138909,270160113,278492510,490828032,946977816,803242084,541036271,624688984,204404014,881539240,779609382,561095932,524976628,888316278,139701497,712146362,413036824,810411985,241441787,247390036,695355554,122993697,227371919,399947791,833892197,899399938,781528108,656359733,551706967,845829828,900357325},{1,31,525,6351,61037,493071,3466221,21705119,123102861,640304911,83941000,859775332,485271727,929183599,393442380,976105677,287805815,238271867,74391877,765979021,335546599,709265303,808915958,907593582,463983041,147572225,888153362,391439968,221443415,801779213,245226914,866175931,810047153,267980729,805674759,955321032,906824500,367243333,486256638,145115859,530769671,290945081,932311137,51068986,807551107,185085629,261181005,959829857,118218336,295880881,506261294,848742193,936582961,153400705,578662225,341741810,161659811,816049772,839223846,559301757,400427189,216771109,207016492,505237766,795055758,945605740,555992642,907845643,982951177,401043526,597396374,84431994,362552441,746539639,303946121,357484364,893505269,526515449,560103044,121894895,445706213,592793631,713670463,810676671,143889731,392244416,73126772,488568958,542583029,752584772,7383345,155007498,994039957,804821801,379264833,525210782,239847467,126254398,219331239,753237922,434345445,635807399,872366121,133933893,590603804,32230684,70841222,840236255,909722819,689521789,529248821,178846494,980363222,548654005,434479841,697553680,35011089,544881135,260563063,695816358,44173506,726085055,671716390,781464159,450226987,146813053,877951734,991641337,221699230,419417817,794832550,810418558,969705412,219055178,274301546,503413612,695160244,74090275,26176299,695070748,341801549,897892431,470380437,3467372,448525308,439337134,724845391,9187155,585558376,372261444,277930003,34819054,431482585,279947765,492267585,818516372,484582901,390623889,856573701,179325546,611189228,688765384,847931848,534263758,557397045,116495491,85868985,610969731,478650084,585159686,14772190,776211983,474268574,460744792,134988124,912707317,105964987,809266690,785401545,161419686,653370610,499797235,534961655,323936668,802659551,370287438,326963010,342959476,313044094,148582386,976795271,120954501,724957759,860215558,270001726,640931921,833230238,701256342,242231076,286286219,13632467,253663042,129411109,603714672,564008356,523901279,216864213,524434304,182659511,983267072,644616701,707181007,618980658,405751838,571460922,136629759,744395053,539608518,963053644,97893406,866038338,265757870,944699732,964525924,892464175,168006507,562926324,742708490,132927348,526909479,79557205,129052432,157042523,659309142,834183171,802572815,517259737,256356803,353227137,87135975,224995979,596580540,402931204,515099940,793833445,691900231,589149123,114327507,887760880,389703467,830251700,783657579,433484966,412892473,432995349,911076886,112628181},{1,32,558,6940,68502,567920,4095058,26291268,152836946,814626856,19929138,508014078,3627542,383619686,178749032,257695016,714018516,472708243,782289684,785010736,673452130,967313791,416615851,594708501,823838568,374885539,520875465,462873691,866641568,110422771,371334024,597629306,954905318,192386746,711820060,202869372,886359460,670157944,884126969,502946720,582271977,402610790,343533084,511648372,517557636,170605372,597697292,829559995,983984749,601678152,265076525,200313780,586898347,936910249,473920775,97417050,844866738,973357211,106398807,531568235,220592830,72245680,709223174,966562898,364453034,204299565,516186616,388239153,70201813,72763421,794896998,14537122,759848271,370782607,723372604,610938893,161728308,212501210,376508968,271352258,323852567,552136716,801650724,615740271,208656790,224034222,747809272,617340476,153891047,285642015,901118362,123777425,16228193,623027527,937436377,60747289,714381298,882770713,15381170,999192137,197256049,480638655,953137460,883599778,148656904,722191509,39402136,582147050,757441169,260428827,253172482,508174417,834955862,157349819,261175551,247577251,264652493,595186522,812752039,875384578,747313263,224431706,462673707,39074204,237357876,896371707,361524710,10299862,761952483,924315000,304463541,831385606,228637562,845205390,599099308,177524018,209006125,256908838,355221513,792061054,713446694,397486564,756107839,527866716,337624854,575430320,456754471,959728018,921786900,102983773,936936381,473475121,131588049,189268154,863126769,700571091,871530822,832046604,609629520,45186676,853387560,464311797,368430192,151536782,691919878,176735598,972465597,804610607,50289062,722819065,20410813,11987321,648373171,889715409,778512390,280809979,767453391,155472064,275305459,296611231,377220752,229158487,259857310,987705391,873889855,448418244,657467052,301028637,400332864,304525446,853531448,201469133,757430782,288842043,292821474,389580374,148645279,450672899,404696472,399758661,549392647,972607841,459482261,344863732,405989209,14412475,913865943,988039851,302203080,293916756,28383491,502818531,791480646,619991127,151573496,311251301,362738947,457688580,884177111,390413172,889218635,530910268,818241216,542232757,765042883,885001834,10229128,574524301,836418812,984923781,235783687,868003012,379478756,832878398,751487743,496700139,587857943,624473538,510088706,778144708,214176553,953029206,646822434,252787767,281229254,401166205,434753895,343430684,941989547,465870277,861407908,387687010,216509894,375279811,453878600,982073623,677731113,95924240,198468867,861679672,204003039,472066136,228890861,880462406,133638984,924365283,274136081,742318625,898640542,85174164,775817726,982947180,716729952},{1,33,592,7564,76624,651480,4814916,31671996,188578368,29248753,200002145,508415428,442411092,823607844,339155380,84465338,814093820,347929398,722645092,146033429,312847170,460125097,915837300,530134554,683613860,22911398,950166343,297700883,874171812,779302544,705201416,91735442,764568060,448540109,794383951,50664826,501387621,764478731,392332791,697065547,136584719,904822171,811342153,498086442,66346910,903864157,648069920,294527566,68277872,192952288,465503414,89641650,342876181,975687654,849073744,732768838,299144725,960087859,432060633,521050995,669642411,783220798,964761936,888496451,578822675,774117896,595815330,556187991,328078421,497539038,461150544,593197759,454579240,228665398,675695769,189021504,506127036,683711210,767254008,372876392,950363733,781425867,518441353,618578159,210702480,146366158,211092828,25645664,252569415,768287264,315751220,46304131,875313001,63062094,41563387,521548621,882111752,325592507,674715724,754661696,386558110,154963091,238088464,48050421,639662963,70331570,315682289,290604457,553625701,114470501,286499320,302628334,934963054,90280656,946037777,701374947,21339121,663053978,944685826,452543047,117230904,560747251,199227363,16627409,318622953,147892287,924956445,813803967,785002825,524657750,94619872,228326183,399365341,370689535,675442405,908504726,873312142,624281896,910865167,214431914,356568789,649815619,48684312,203060656,723151845,388405201,798060040,729614446,977682164,533436928,146813819,149571082,895803037,777214043,552248021,204656845,982800841,733286978,63964308,481147156,389291330,76639625,311176854,441157810,671041225,83215916,462900391,792922861,933493638,911064426,640299582,658369868,816565473,95242536,385493380,848295064,737403618,437312030,117969370,718173112,995019578,309321859,756181744,40101942,426476878,702396178,795715493,835764511,743326504,209546865,430615231,826070511,334341237,118979238,371120144,839568659,676120384,72519,845333099,357629799,910834209,593346831,104377605,380654497,634970517,115890735,793059350,887063630,651636452,507749972,783577804,143656503,242083869,911105370,970085702,524972130,465698950,325374351,536364599,196104291,139239152,633851401,256158579,919175466,894613648,315818683,5141779,876022828,934709255,681050535,191918360,662583345,207316521,848780031,272975543,702356884,769886013,961041057,6500208,70262300,494310602,739703998,384177576,343193798,693062586,969762392,66952659,685150241,630304511,413041585,515441116,191001103,912006289,473846745,605301455,795067847,856671001,508821454,735406667,258084054,117733205,780290039,23367661,593944851,692132515,4650353,187487602,151055135,898863554,673507355,215091232,603704193,594167428,682519378,496434131,965159536,430378180,248402836,470772870,307340881,347656961,749714755,122062081,558277910,169666679,941915597,277380477,270070849,652088255,549544085},{1,34,627,8224,85440,744480,5635892,37957128,231322416,291965329,678229698,199102832,733159273,432255582,825398987,945721657,530531857,605903605,198451639,405128341,881104650,95712824,87475937,88052462,854657880,671362129,345256719,279913923,405600244,791623773,184158289,548244621,559931899,811302745,822463013,829884052,612803610,114370483,717655175,250670751,158660853,996989593,922821653,403693850,640224917,726696528,558324649,504260316,457498775,235424755,214797729,595578763,703649058,668639597,273743575,830864733,8621856,152359528,351252345,54682531,631863641,533130514,548187372,212107229,690348600,269650465,644636821,588449397,716956418,569059993,571818753,620732748,238441683,628780105,73251606,77232245,265685085,860541096,181038883,995121568,787161997,984175916,994855981,70309595,279951259,412871815,881913054,268261177,575207129,196951994,610045829,705950877,200402175,179100085,912730914,795237101,264189519,756871237,840795855,477498958,568161700,101820158,478938140,546807900,824972458,320572966,375535061,712736750,146215080,296045377,892271196,198915619,973312163,292266224,766955048,774760742,724672108,189810671,590576941,955913056,705860403,956268133,120026477,977289531,897970234,594373646,802624855,16139526,294245189,661099173,505327457,687552139,570417673,288750674,928298666,124243321,103493234,782666425,810561902,479140046,567654010,66398299,87173858,171094018,401077961,201022453,649177770,751032860,458665510,583069945,3741921,644139368,777863779,427938859,574083500,968708036,5259009,14753514,566158894,428971413,29779639,601893398,934948155,463945886,442386091,787098075,294593703,467511028,998601384,749411810,495421040,283658473,287441865,687819162,964614928,353638623,648210867,238886215,893364457,158958124,29345292,800368429,595552294,572640574,913495958,705720935,850127566,83220185,799386246,848828465,335228800,498492912,819731260,972790229,191002130,289923062,997108332,479589354,13686350,377632380,915241611,38445376,115515812,312111610,862313776,36444206,491509332,899038496,494299749,577210085,925017398,377889538,129014425,544007299,134491550,77644047,150186363,549177782,243194000,889811949,476414356,302027816,934223010,116351600,936035078,728736728,99057293,233685532,715949090,484999785,527817757,40017975,403976200,963752121,230480821,165554215,501580240,480519751,374582722,588438105,13652788,835399525,909982574,63720437,165170490,768431894,385829327,268804006,950180874,398363435,512876602,149304949,858796870,305796565,80654592,209088881,365995652,741417209,580938286,849913699,209592153,430983500,292682916,89781822,346251985,899920810,490814818,319818650,865676138,199552930,49606030,396988194,289382805,394082926,680976370,125444750,312554820,11884810,730982055,36906819,144996838,532313029,339360681,509568859,763509787,79118993,930179491,756170211,627420026,161269793,542072728,498021200,392693531,523036960,919765468,367278574,755839168,466305341,613534367,534169086,166110829,107021592,280650539,268761091,590645300,269909358,234042842},{1,35,663,8921,94988,847688,6568888,45268120,282195928,611807809,518705216,990050297,271051698,122408000,405189613,94926808,864141322,53735275,24011733,736554738,929218491,904644261,780020466,504939462,734736582,905177688,612557341,964587741,714487014,841745335,939266470,221175663,553510265,427922711,816845808,551876447,104782423,432788437,75343637,98990584,780296494,401590023,184896774,39759619,46187357,134251301,342702573,517720,358976055,583636644,962541900,167548822,161325057,550357824,277594189,165080443,231182951,735855208,908711807,571176463,42569340,237272417,790920442,624258522,720842250,768667158,451444080,122083868,366641147,308868590,806102171,616667978,212552319,508058403,321794596,570313528,460066496,737582233,710064955,691296552,63281621,675218599,955697061,110510427,512018248,153536802,745040214,175960352,594730127,864516601,686994354,671193730,758082482,651219990,268055455,209604272,794711886,922988292,233697499,855180879,757331520,952855529,712373324,501054908,610479660,988305583,359797155,981016202,392046260,222705767,339379031,255395660,760704862,824907580,377018926,100950434,568292199,345612839,702169410,76425882,316244660,633878521,345805531,43908232,498746978,171201976,618174067,828038701,451921110,452033897,911744318,64098066,83924105,595571257,147937863,948006101,514496555,77289879,282007238,421799065,804334778,765393189,193008022,263503242,355816072,278012511,227861525,902054870,618486736,979710805,971590402,61042704,664850817,113175896,488535341,617582794,612947413,45804546,259073867,263038734,265569066,162645795,60875191,359494871,979749311,139358127,29529290,309151363,279422923,345089768,87598058,700337527,479652910,994907927,933976635,324751070,167729179,810904540,230096199,33195878,559883815,674302503,158162721,997344757,974400760,476723636,933671908,372458552,487353300,603836216,903251923,461631785,620155186,664707969,139328434,135802315,547850780,544085832,243757336,714792500,277247444,736724545,7257213,104433298,33077964,133546300,658470668,407613385,15549086,409602732,220607605,154437658,434924060,212726357,432662346,953726155,55947205,221865215,896738564,702917595,219549259,784888336,998968443,737927890,111474776,479544893,204531672,722344756,339644359,296335713,172390948,145219000,740849986,175518952,876047366,775536223,909308844,333180421,96764559,528034987,396799645,413114766,622993858,563074288,710510893,900874806,315196225,993816000,623166550,642968249,328645521,844280596,556521945,272458659,580772239,284457451,186994948,909094031,935768265,319893231,114481887,109302906,586737223,466388545,717893242,342269015,164207650,394855609,330099455,836592042,939058426,541984626,852636994,524042858,358495217,921118657,464191254,284341637,363378706,679058686,917272314,562488937,105215359,614330571,404183151,365378837,280141835,594380252,79371576,739360814,210010442,10232401,449147207,97531383,696215921,900156881,51327507,224992261,946786023,685932368,729503576,741723150,479111191,872812474,454570174,217639787,553029674,745481673,194164134,241094015,672191097,520725696,177728245,485102929,511421076,349030122,157631252,431267952,813510823,604978728,799539100,871169236,265066919,191499414,52282294},{1,36,700,9656,105307,961912,7625652,53738944,342470612,999200441,797070294,375863958,9523173,166271514,481765400,879554808,535680694,467340394,413500052,692064693,580959888,369347871,169821810,621921924,137911737,940784828,741570244,905517670,551817302,657369119,721648393,536831850,500879720,726253305,296162041,891225164,880747817,182180719,544050763,654393489,357200480,356889637,635049309,374948412,486169649,407475615,51228607,535369936,325305756,74215114,944988254,919680639,647644667,526651696,763479161,278201627,103508412,387580497,561661113,38190290,310583115,569811056,351262691,985051203,403138813,643132429,289980808,570569544,550559442,934893929,352045239,810200946,61218795,42358563,89293505,506603831,400595820,117891860,469015294,166372283,320554017,155147268,955469333,896730515,826039051,931193995,36098122,893366407,522834450,917130400,759016216,23584371,48884561,844352920,604253909,886656394,548946691,688504947,972899398,721435398,409845929,399680456,284950632,796741351,217452678,611033399,592790059,219084711,504058472,277505825,120276345,694287126,35416589,305976723,447309020,969824889,565684997,62139306,857693940,901163636,262850397,927594387,721909425,958991660,471789360,260033992,544270783,877013007,153311613,85679796,660447085,213261352,954007371,8266647,75417194,28241545,733410215,579803150,41901427,876245480,900022334,813145019,668096269,73987267,175135030,724217744,139403302,77167168,775504145,397863476,816272710,221129133,242347768,885383757,728565085,947647994,605379205,598139075,269419404,178994132,603450690,652850980,19254430,182635911,57268581,239936865,878358438,515315850,141611162,665647032,700517198,807335907,965806030,897617342,773532343,924389029,419741954,420757062,581633294,179995348,34733596,923518220,731757774,573741822,531242380,813544540,336821038,442738016,551572674,470067223,638102335,989538200,956007535,613954394,401563904,103519975,569290006,144046622,689996849,638589501,358099514,725282594,691632053,702244532,284031792,473014945,465414316,116886234,142777936,342518645,138051544,347505254,57716395,939744642,114873890,359397343,671360195,724489266,683013222,345781236,550104449,877003874,63443231,224660360,658626409,133687251,933261032,273131705,48202694,144323990,559827621,779609382,930553156,35267489,493151974,645090534,517431516,368634145,540405134,215255527,144656993,549192120,659960465,217236722,742258783,538378955,211409043,760044403,389330065,692548510,583181570,627949137,829194932,234693932,651493437,707321269,828284674,652751037,873736576,267300299,729754896,429920674,875733754,60888792,225478637,39002446,407176220,761384762,131879783,661443680,51638267,568172852,186052558,637968267,556455031,313451921,238551452,644714578,449541818,640800540,923965193,38909678,41940756,338485997,888949941,526610135,48150535,778944981,480892059,874500608,900322190,973783674,468787609,618167632,913754856,327797543,845404908,752246622,831422464,484541178,501948673,647306990,882577308,771072569,171273117,620085552,385025714,126556571,472404266,664907284,284895728,860747643,285481155,480968189,426457284,579997870,253315436,264967992,325506073,407074927,289125366,710111895,168902913,39893459,264014099,335462311,284068808,624620216,265346008,330183605,301153063,136165951,223572391,416076696,791322793,440956632,812128221,56870528,529001955,157225171,153110824,659760559,934444871},{1,37,738,10430,116437,1088001,8818820,63517016,413577336,466132154,602224077,950429493,571044537,948550192,759622519,360792951,40404471,549575252,331339348,353289303,642561133,959520386,811439523,113998222,306747368,686402540,608623079,625536502,102898449,513583096,310389938,861964034,144673299,459932354,368865341,656127608,909171212,807159815,446679967,582385365,827063804,980667706,264330272,600794253,740948802,906942889,945728377,18846332,985664112,7701519,115050801,870345183,606442987,443069595,817056595,621418778,690512206,255049968,161633922,402904753,372549674,317848199,779510849,454579621,366999138,955388684,940196190,710141532,289889641,400266971,473006189,518001144,203532149,277752196,73653399,957077834,580796815,797359407,33679102,974181950,229170666,221016673,753153481,718492334,480056326,134801483,829292600,87160542,624566954,157188714,912350324,248797376,864861712,311625650,564724833,638897879,211767349,670618766,182357348,406247054,335828971,235855014,766599169,873180801,943988159,797515463,949064434,37355164,366387587,992037332,39085136,457008562,710738441,147115812,245127944,221285308,44913339,750687382,166494925,487773254,2533400,294773545,964749926,838352064,354747747,983055334,906311260,773970452,136280712,732037766,304757958,868694356,9717274,686595153,845171773,715645486,457517675,868876321,257821804,398717354,952878758,459394839,735151005,982831573,597714383,483469574,396276440,147004054,275175512,449695021,280047682,322443740,657859781,236891682,338855034,771308208,208042945,611383416,470020781,959351211,871193372,314812327,417008584,157794928,30304137,772193806,92880268,735754383,725090032,678769251,695572650,713627047,220917673,996272940,711499227,615337951,732510553,265860373,10346269,946167168,327969286,691646116,588894836,556718107,891256057,29035235,193826291,413628097,951441661,812044940,432676044,866499015,139084375,351784477,900166473,781089061,914118385,818686834,857340116,329139077,237478891,284468211,215304591,458481845,227432873,865995208,554027168,463893384,221077016,374577314,119759917,360383422,704486222,404678036,137104816,809074680,755219457,826569646,867839827,768754773,89100960,257194726,724398193,973188469,858913715,18463743,680309520,450458743,140048366,764912130,371007014,456635116,735728421,778688084,152973997,434969799,574794869,212648988,728361716,542931287,302379989,751579729,92390154,220181191,407743441,315151252,520426045,407908622,679231575,395003916,794034847,347654216,68808817,829211530,81601558,162714123,30761100,394951130,268715057,283612447,241955302,623210420,275963878,159211117,252162685,595441437,529655660,437222092,841111836,179960886,135660761,917237477,768051317,444580903,506791801,487181239,875489229,680194597,205928376,680445786,683783933,969592088,132367844,396994570,832926454,630581401,505495558,385734337,641541057,95095471,989574773,911275608,518514268,282262989,419271827,469001628,420271862,947083037,407529572,59976989,434008630,863717239,945875935,75676474,215313835,250745830,87811894,264747800,37018493,98597371,710706515,142785594,391940962,336466122,341268838,21508490,413865364,232101532,92701632,8053527,412757119,757312194,403681966,949009531,880975038,37050684,272465075,678404684,193438246,672480427,700064004,142628578,802581416,279140871,973655892,800905741,598005728,935768930,668573394,207197197,649003003,270174246,76144766,315632510,875459369,359185050,528086919,473525359,758981160,249109513,189948776,344668617,795917722,549344159,348920520,486734532,302843834,285724416,810790165,350603652,574459989,873908008},{1,38,777,11244,128419,1226846,10161959,74764168,497121432,26344483,38234873,423642505,376339808,863392989,917340710,353019266,355701734,828153534,204362640,374924405,607928554,963790885,940721850,687219775,764705852,876861874,763291630,981930457,551085656,980270580,505906881,983294521,135354674,135665519,630173290,212355830,143623144,227056594,817242891,163435465,418550307,731605596,289566443,285968813,433396374,290335437,260134359,257166798,296375223,99595679,459082068,507135523,972388714,133158519,975205558,982374421,644050428,996778111,162109063,746906113,514292299,926426755,356009260,196659267,409916170,325494529,655002543,558511285,36446396,471095084,174722764,671116976,160891233,868903396,304037581,23612943,337881011,234387037,370561646,356075504,698718914,535181667,514726084,815242029,608023573,448544035,835833664,991058290,399256230,20531824,669361826,539724566,760387110,830813942,547045707,178050500,929198630,6813905,110412371,858816899,809729618,833864785,232951975,485491061,613385270,553071180,627954610,952757220,692906182,748961577,662247263,52513186,149763764,145530822,33882391,453364543,997405166,992558694,759602854,84367345,100239977,854081961,858205595,486024240,91555639,177882871,949083392,519037398,556513157,228484413,492836072,589348909,196163508,266626335,11245627,157404436,270481031,638406640,490889097,527976504,370488458,823400678,322868722,206357234,647142926,768625346,265191551,148038615,363341916,267722164,893118504,738977503,565582757,762106365,849369394,766495732,13155357,515888816,523640060,647203814,437352666,546684558,961386555,7614498,893885274,936701598,428062192,113231261,402917050,409965843,165984892,799921270,659405770,509144023,774701607,842603658,487390464,251731862,581859608,922860080,258383681,201597752,292594441,460903867,638298912,848020590,765105850,965506327,844776867,575276415,85481014,653985938,197424999,197600210,989591463,112466859,918937916,878289962,30252094,561367106,701604983,794157139,205106586,358551581,218730442,820317821,718077344,742273426,343977802,723940137,91227055,889419899,835334285,445942872,874169472,806494972,841559090,34902341,936247116,742348345,932764662,776531786,136341990,609226011,962126351,692609037,492230872,512261831,61424189,202712100,557188069,23267751,10862209,780311892,698216821,610626474,445698906,548927052,791636623,278469086,802570473,843652647,214889050,950325814,545811188,732525066,799299048,547938769,119233118,836166054,515368215,821018309,703809789,385697728,474302192,326687407,701322950,753939342,860741461,608860184,481069405,497217661,107822505,538149776,65872865,267685484,630211463,833714775,127007356,988488267,704390393,326686679,330510067,968474337,860095258,865223840,3530159,602833824,943838253,510792598,862215682,804647558,57277705,379631476,611335785,827032941,500396827,166974973,950996383,97277257,336237474,527425945,836169765,13569792,45600126,103702022,589110361,158793934,917834123,750227633,450511448,228174293,380815071,984828008,35225572,19924799,316530723,169463852,11894443,83625994,27918722,725825514,510537357,901592447,560692763,386943274,409576331,409681305,19743037,901841314,504205848,287987501,95070522,999713439,52172335,458657276,716446234,960325619,967217606,29400294,323715881,571473809,542099425,838958945,826022366,215456133,111542899,27057122,264098733,414451664,367598279,660361161,317432327,788309656,482969647,453723335,307123116,46250346,156036134,550671015,501877998,918162544,672414507,744250791,519150731,449335541,717241257,798831268,772517138,286300330,910111510,66350225,850058429,996528049,454249733,463645138,33673728,195487971,700828817,25012182,447505308,968790402,312778627,684898658,698549052,965513947,825161447,410399245,428579579,669192144,82412074},{1,39,817,12099,141295,1379381,11669611,87657665,594899060,695536795,226472285,640458905,794561570,378189352,472728269,218438573,56516519,255055733,845027144,588332091,652544873,575593478,251899261,421780632,446749115,397384403,967249876,562965804,307548860,910064219,267557957,532097834,694036707,378870548,124206593,109699395,5415029,722948552,875697847,694452268,7553293,132421363,106964105,391245927,870340375,243365738,69805673,199865008,75486973,171179760,109991897,220793643,513746719,106419838,540171765,580499245,759007158,982900537,645687882,590392656,601803737,221575615,697448067,153409333,368742411,593478736,779784392,983542304,533669091,167997680,729893362,841704349,760614624,47743042,998724205,972938209,77600320,536850090,695359058,769331095,966134679,528777379,695035445,387545073,911151592,242062595,521446824,889535341,920252167,112865832,806555197,118151259,625842139,701618487,790273468,694977537,572862214,473466414,246109368,48621359,353657541,554932622,499105369,867797665,487345603,842033962,519557065,245850790,335288378,782811146,892240358,338051309,826545456,41171254,334148733,152569170,144665017,941279118,897754414,89241104,416864510,41530804,299074740,73588196,959211062,109470038,500259918,366443802,403320596,183957534,992196343,652194487,652679636,980112362,896443763,694053263,85474084,793481845,36502549,113761902,13660255,295744749,768030597,559676644,267907464,329732897,34721556,481917917,470669881,496023609,35319413,426881953,436183525,539581676,797395436,949513087,636400441,684066319,283217124,456809507,742722246,708837224,1825110,845476655,721485134,509524702,571748192,313097600,164720049,83489702,463694600,122519767,438333196,350973050,742760174,292313656,699166885,733491013,480543050,245749577,741817620,207993307,244579067,622422144,604751887,899189402,151409381,217727618,880477312,214663719,394263729,196688383,548030201,726215545,464673145,261250632,625458514,838784252,982491280,700533618,585918514,160625577,639912412,329107337,639996475,820595096,822718095,278815123,496262265,918547360,8027724,726754416,823448457,260321413,863184482,650858805,276099402,685460415,954079520,733965175,676833996,368637623,143549481,304621819,472579474,749596748,116386311,410243381,633945382,411647917,177570608,616578162,767744928,61290651,523112125,276619822,15151789,253528389,167816966,891846580,541892511,341041750,391023167,293092921,243156326,622723871,473135257,726189187,379573236,555335821,257038714,482079083,723871307,606515981,65251208,632383753,147352575,594192641,924833549,483314326,808069004,770319259,427864560,25642674,464671587,569308215,637300329,923466624,23057035,86870702,983746124,846059215,574808201,554549209,446310553,959681948,778636627,211592095,516682914,291911580,587928798,427680003,894209596,866648165,679666232,460484096,854394115,982195268,822495481,835383529,431162040,830468499,195346596,57036658,866149457,860543178,818146210,279107618,892401239,225036974,868558986,685134666,744469605,156127522,187537334,788919638,909025900,672187019,217419201,384265406,616374282,378322214,141913342,501653295,461070473,25985020,589549638,109433868,888240019,931367280,762349235,234613827,765084315,611038359,758764450,286873014,382512476,382119459,20294058,943700532,211933192,58390954,180966724,929698288,805610393,509211182,866583662,775212548,88368846,726939816,185342247,229877142,705155204,200856219,36832958,610458570,660966337,749737121,592806565,894272325,480779946,649154472,88597955,74084666,744113332,528684751,282107891,100372245,756922141,58776739,981772435,924634098,951039927,397719622,577729727,762973087,736969640,674672356,297937804,986319572,149411109,496025335,118765897,173573997,13186371,696131467,139811703,497652080,238358226,252091863,126575962,416549513,112043953,769546766,210139961,218718185,975953506,930028805,845629302,57030776,852433935,836915594,400219298,622051773,829969111,114603161,10751254,909008878,579282117,214070865,563200757},{1,40,858,12996,155108,1546584,13357338,102391268,708914679,491589996,307979410,602522471,317222127,290284759,54099411,989042041,349750818,106531062,706143382,63807262,819412921,144007031,937903432,671633208,144280187,535961584,391683158,665684992,173615217,173957993,353557533,689224661,70346145,249590014,418977958,826283746,394602103,916349862,513826761,491750575,183159109,757685121,418341803,274891227,642914114,790796259,588464975,740365449,551222753,10565934,35820801,515689568,211177017,828019707,68961130,155306993,295844962,698696703,264483577,967049520,615265667,559761896,719262960,509462378,575657367,591920899,676732702,723371825,327050158,311506131,94078284,608080285,992236405,137506625,399044419,458634324,553334522,801149022,685520978,446537546,993927587,293142441,349812890,364132070,129851348,857298051,877404263,877505804,63808796,43779853,597054006,757518688,847719064,814336009,295491019,566317327,427355879,99632937,271930495,211594531,907085661,370381473,40651392,893659649,363630034,486697292,957988008,762036357,927839193,855832860,336383816,307639758,266751066,682795763,757933830,702637096,416587519,241670221,803239702,991067388,753770489,69318095,379601638,829408102,918333643,833524181,647446668,999853061,600717076,736359930,166694847,912637361,883248816,334184966,360770954,907814459,571070899,760625736,543003305,12232839,27415041,235755079,155935992,895456358,299525687,387663753,430722193,845849975,389897647,157165043,232374231,709459451,819494807,873294798,982307907,723241456,529916420,190269000,832006535,157577121,119818595,751958343,818604698,923214476,455357809,664208514,204222119,358021985,507909159,532713722,447934290,550255949,9030523,204809569,704696131,798537153,779574805,146334295,422444856,763243391,968318292,409596303,730176788,661449533,145680243,291092743,406566554,840725280,859336604,385485264,540592314,491573347,430591599,799102625,349645352,953856191,685505744,968883032,548153198,991972402,298640488,335784052,560792641,200482497,534424478,835919822,256133832,789502694,815463653,367192054,711296060,505894941,749371649,586599852,478956964,771301542,936596369,641013477,895880622,275251735,709512313,675062513,900057226,864601515,604121575,213439255,718556713,352300658,293209273,62461535,212741657,925233457,601757735,357273411,900952265,337965737,654516053,138964736,683012438,388413281,151113816,328964247,191920444,84786019,179152386,346561188,643354711,718267295,169193229,252223726,887596939,657097686,142103925,40078284,150004901,459569297,459199105,789641065,6481222,858687076,375816137,147145108,520309635,748217920,667457550,716254093,186260954,725808394,626037945,743543562,764478177,601933842,797462265,777370200,654651513,156072819,707272486,178868661,27986290,925976600,457000898,540704905,843382395,769084631,760118502,476552208,749317409,710185045,964800796,516878606,266237510,913933501,813693982,336046538,762072594,997287607,756174558,615699332,325935068,478725181,294206110,71125626,862744505,369229533,687983312,908265361,496504119,960935105,69879109,315010091,778995602,757128123,249975621,699329744,984761141,255696873,966070938,214893935,551564463,316442626,532269369,314110968,128028415,969165598,561496103,817486578,282697706,480617072,509205119,834540584,277705122,660874354,778117470,366056531,831243822,903068403,672944646,441340373,340680954,617276976,849516577,560088434,230800586,10428026,372559113,922230949,889642650,244184042,533938488,841639506,817920213,336934324,44823033,565545678,701086145,241957483,114182239,850726147,526783422,115816117,835376982,659266467,815849396,168028335,255187925,748491938,622185783,663040863,743392515,163408177,383060357,31556416,794030948,934245344,258437764,379321408,40236316,660469577,655665845,690942361,375378322,568352979,602028119,317437606,657543398,100015852,252684947,481051042,964341166,522946308,280791483,467949044,475945690,972019230,462068105,580258224,819125286,65219413,675919204,938373431,246074242,416112669,990084376,992206586,174382581,694468435,670357482,52707698,430228891,194064984,374269653,873105421,89789806,360326019,422866288,247972613,990139142,766813630,25619403,929658745,91230876},{1,41,900,13936,169902,1729478,15241768,119176344,841399673,434809990,446105964,492649140,758977149,206041682,323715565,660084286,595902939,912996958,734408694,639760787,253066665,208103163,518638879,141246298,316067064,932295902,638352197,835906694,518593201,772224592,710767801,155069328,87760296,888628863,85616127,159719113,852745152,116208329,603162784,598162586,214665773,928212607,364268988,422947444,91651894,294508512,306449339,29129368,721764444,23720919,155935808,134434641,906918132,581645037,673925534,656820458,712140580,940311261,639783029,193680127,625191701,485391283,454129733,912047676,531795443,151893083,16212124,506754047,491882623,143293012,25311790,265858487,730580376,281408346,313354998,904477185,246774679,76212745,790588368,952519623,156839403,194467618,872887052,91963369,534129628,238356180,632320800,58443419,722943306,618550091,33518175,519583410,960079192,538023159,305123951,486152058,294482726,518323725,455607677,182021187,748135143,512410493,35362801,719659644,317014598,528329960,583008290,443175574,659178079,174647583,349497845,577399146,818913619,271472027,656817275,494680790,969710982,229444476,267631925,175671131,35511369,58752774,135202754,944159958,464206230,475819996,314325811,754861491,276808552,810159244,91192489,626570800,590621471,514780234,305537247,801654104,149383516,787215362,114530579,859617326,613074050,468568467,919259772,617744284,340905322,985953212,372028816,217079653,938494776,284906842,769978385,515786223,285120775,375534381,675385916,665832700,133450834,3874364,408375526,770616302,276273159,413928636,723794836,198571707,678091222,296508406,529916658,588863591,413257244,498474249,915935032,120501359,836927142,230121084,774509032,870826787,489996192,917057075,196187219,383821852,922336284,22274995,748507616,607632780,183109949,339998525,507933598,698781318,498085612,803731847,473820207,901546035,302928184,865394080,114078163,2199878,779942965,594445523,91527221,272107811,718335802,365412741,52329171,414520032,494974650,300177708,811610962,146810674,337728819,506402762,403329973,694340600,766854981,757139989,188368338,788752320,918847437,928046733,527551285,479184799,517252899,712149490,791491255,238449676,667119615,757940899,445679476,734062646,326185889,40504124,623294475,807102585,697275776,960233124,90479243,277423126,459856976,523164613,283246190,353589088,214300387,783487356,692462518,267488040,851918218,799153667,810257248,109085516,633189413,670646041,913414538,526057886,701571781,823895555,366072317,141394361,832809290,464577360,305577012,512815120,121404516,195457318,321946163,309097012,239601477,94799504,314416433,43085740,639634392,892727867,559091131,668748148,422889784,711508368,676630033,634668710,364293294,844937242,751071408,322260215,891789141,187899827,511558264,521391391,670781806,509672700,51147255,62331255,681097643,668432081,698715101,46454740,726474418,934462337,72103891,408373632,957100449,670661469,786800623,834620545,287400489,490496888,497846381,189806313,912940390,809020495,703284720,835793884,605744360,923348658,214377202,697918809,343995053,445012242,544883273,475774494,73159748,664916820,945806189,388033609,184443581,891139166,132967061,662232592,630310273,296941879,926467100,732662520,755030683,373067237,200501225,132039597,621016442,864116597,199168443,229224627,19895297,392227721,512572983,888183257,954225811,362992884,408318299,664465052,828120392,703374891,61248349,16358204,241119413,30565637,838212406,921697699,543334430,89858526,273185879,355471309,304528048,507574008,476038937,789196651,57644735,932966132,292240565,284284800,198355642,844613937,375170024,881957600,108981244,644631978,730251746,563646094,15703371,891969119,462467018,842418885,184776107,20489508,525173823,93913531,199936707,49296883,500271791,9386940,42793104,102301079,299925062,242848544,157270543,567750735,512260765,540910896,473863432,123756576,867793612,940752336,189701376,338838501,163690216,120916067,790468763,680974009,939542025,299064055,752326705,668302564,775312490,929999123,713601128,593704708,595301628,539445680,220384571,492539730,572951883,264745653,946510661,751486844,372815432,445849920,481560920,887629330,46438187,433046906,550746520,68280122,549536967,98170304,942092421,657076175,85959544,736296914,244774210,196059783,968298850,183375217,810099519,413635020,636120983,396309504,740465895,371532101},{1,42,943,14920,185722,1929132,17340642,138243024,994832181,548192008,829424358,702470585,488681655,275370643,835638795,810867407,286977068,950047225,83539435,44629372,288790619,507410843,264046736,483012816,672138691,875194556,651203850,66911617,918075656,674825734,94581776,415282344,303997379,819537616,622429217,698967413,751254549,420414807,687830513,601402264,434289505,724948167,754889253,808542135,995391960,178813332,724416372,177739106,814105099,753597104,45856871,272275296,786414287,511285559,160720229,317562390,790336119,868224061,359611251,78736463,773457035,927802445,421722380,116775238,364696053,502866895,626441652,490807991,713262576,797949369,598695934,260170588,82830001,494545919,272206045,443643728,598266021,33015507,884148700,307476402,959867411,216334812,800291904,985570368,488188448,107147695,538136243,662412600,979298525,134498654,226734918,727004323,749341953,119616289,344235011,179701806,771727176,867138213,462181714,886155872,120844409,637609736,732957723,950929297,917858187,787591285,658307576,752393246,363474545,410621001,994736846,177814531,780475306,862888709,592093607,579502147,557845688,288775481,603183203,577960148,788283409,673824051,683888139,877184660,633236685,114600324,443874806,243845462,737247494,816215602,301818289,678209727,613605938,858234475,818583083,638002191,955539556,166659792,402119583,136117938,121601666,755992562,47984728,295575049,499852111,307179145,332974068,315732357,716712867,640162541,867854182,934376752,313718034,59903781,946384843,119557570,525136020,151571916,798992199,641098837,260839275,993458171,824535499,355644177,761912070,816737774,16159145,269418274,606453921,360745230,8968332,697762673,987763777,660889863,735951723,644168107,694447061,112348183,530007620,3042837,764274326,848173528,194620935,635775962,259196720,713828904,940082694,457694335,838811079,742877821,825043434,999682813,323541591,50872352,337477908,513975090,485543671,991738379,437900643,771900426,686428428,563411325,914169111,935692665,43568184,490175371,749564693,101137943,245839802,603981104,626386341,386920859,413292672,913439917,70347116,434898910,144090153,824132212,891175519,132402569,347193520,969072546,16729602,608672301,618817500,911982521,688615529,732174336,500282116,497352932,456415575,878875953,316115544,915703538,598465482,596140294,730305232,164832432,897815573,166896959,324516472,764718824,566396641,914517008,874306816,779763109,852306547,611269114,292511571,915381300,758955270,257373679,74625589,121789415,230596845,205840454,916544901,23902587,416402779,293269031,510816400,975368660,955188220,72244504,561311434,137072009,127537010,860723336,883260674,394382836,913512596,497775666,206616201,483790701,11643758,543373789,107216374,536706614,345207484,197739695,416959310,802020491,883579389,155472766,707726533,878636875,137339984,387604391,170286771,862464509,93116703,698306089,277231574,157624181,518482505,545923209,301838767,429107456,65466197,400869145,603396151,201146053,29560436,908247428,740900666,645622178,468181946,182006817,585006092,39427009,901513909,575103140,643739693,969005418,413112711,121940507,949419798,274176335,533655948,73448571,447893873,303200166,406062958,327948494,399154885,680966803,676784794,346165530,118434942,634041854,219847494,927409557,731595298,204066166,484721091,397391612,62697528,613046235,363210072,588627148,359818291,176675393,710790103,31891420,193284227,13322649,80677012,364175866,156203486,303397217,540753075,969185318,762928705,479974322,873609278,714679223,243389411,893917661,730412727,540295939,380888528,199480073,111615382,501213077,699982545,83674978,340471893,589623231,135448371,354059110,416125008,490338358,869847423,644581498,153365962,261322947,680966984,400282844,542955010,604680600,412088220,680278649,139286485,860834305,469429775,280658323,253030904,2560916,10309871,297479762,823144855,871982081,47058346,963847165,382927224,356584190,324565827,306141977,910279795,453817674,601981427,979339306,222338413,904561649,382529080,408856660,854658577,411827225,670817056,827144476,223389693,471934610,930635535,587441381,722797748,95690794,663628478,287716698,646651719,701670514,288321331,90367689,303151955,540716833,449495113,614473847,768187147,779428778,859329178,317839203,24311574,208713726,534909824,569617669,779723332,951823587,262620278,508684571,644816282,124674019,369884532,146396384,993989514,828097325,353947367,356630001,483119775,36683277,829372562,480348153,416969202,237164413,917166508,673670902,955993972,550159722,115253791,571208381,883450110,234414978,338605160,465632072,975880238},{1,43,987,15949,202614,2146662,19672862,159841410,171958174,857707214,674952199,863564473,694487987,218927913,150857334,64522123,242512102,726888439,233627107,811786714,114239005,343074532,372330107,720689358,467711835,904517093,48140523,445520536,151023837,477389409,167654505,524330326,826025786,750662832,873751815,63739722,191556854,667326112,50500515,441625511,782830742,400734038,564497630,921910383,845548941,368028935,749018447,103585045,796556849,628596101,868979841,539520158,627354569,90231323,417433082,56768496,355579497,422451590,886349503,72956900,803725461,415871073,683643384,621063238,193330057,325926450,277754812,24871409,448472012,886190243,823962291,441987145,894908057,837390023,862747763,91512877,722912649,93349481,545810047,913016979,515556016,298546360,734212089,844284728,136068973,71028614,122223407,751306630,44843394,423748616,386401231,812571458,811253207,883210298,108253088,777750730,94398075,357510258,341016668,444595182,421469474,846006439,697364303,430219357,145159,329923811,555736286,145037472,50858159,758063180,409311835,199515197,849732459,429458586,110831608,601311986,405029768,899721594,362036575,3616348,447767827,718164293,455022502,154627334,632024645,923207902,841801838,418932384,595460287,460605434,188513457,767682601,51793196,194981425,929803954,504733978,22197692,870666331,333136663,819520200,530915500,599537526,53266589,48676597,387019415,413134249,89916173,988538195,741237674,580557472,340811443,13472882,840030352,781975641,296220934,702357371,942050407,935085214,845987731,799577627,872670633,692587304,440284632,702895036,10589510,109084537,901549736,680965380,523560865,14608855,766098800,955736031,229070295,918139336,762087315,15060087,769624318,210516326,269537431,932448778,651446512,367308406,624037144,927670291,415521073,854675140,947034643,395133007,858104556,792426709,918444166,282314711,96653546,423079321,469451942,792999037,308400615,330587501,691818222,53917678,568461122,362577365,775464857,904714011,845440210,795470521,568880508,666239878,183860147,125507811,545400921,401495311,3467092,430876347,332849310,96436924,957680475,836934713,150232592,891109199,995835861,145792868,255284669,853681633,801676454,45857933,127560794,137690320,534209092,436059291,890838261,134212816,302504982,936257832,761720727,269396963,28197218,59083210,947207164,442972791,384169121,488722025,351406087,443097712,82956552,698141640,145942108,188889308,734290094,387705377,912805029,973822420,47485510,507370861,221674431,786661915,91335607,856760661,173031704,864904090,599152735,495185408,938099393,556362344,990758140,995900803,254599934,462199704,5008078,665636661,527028350,642386127,1829553,551952980,424017355,108488740,701380336,806666866,700141562,59441909,362171728,894757457,445400929,773238426,127546419,723395394,338826564,332919619,340737249,850054615,184058121,13063831,278558952,698063140,498777528,72607237,345269132,902279995,183690503,772520236,708689187,233896476,458831695,230994551,41124197,206351350,689101399,262700029,620939252,892377787,428085255,694339277,213848040,916329377,192795757,474268014,561285670,220016093,638297144,193877561,647642810,64716523,5417153,709160560,438820650,471896153,456049785,424945489,102312939,179871925,155527933,66018018,519349428,575834851,366155295,196027859,709388961,444696414,108229719,111474967,169464130,765045351,916818004,674916990,958919968,932259128,849009441,829390390,846317162,253991616,482990034,163822353,775754269,532037321,49173712,212326050,301906174,678424573,534302771,375782334,160287870,855370313,341617592,25457804,708941176,246832732,903916100,546588049,96029971,706821232,940560978,101534792,337492719,856837601,613769045,707646199,812028723,616833643,679800396,535428679,224426630,413895724,784683428,431644219,111092914,661756720,639659700,41894591,68359952,43802473,952730000,823133424,376059765,707785553,822330735,771301262,948220958,908479296,864547297,515908783,27167717,175015260,401476125,721945851,298498970,707819205,838011772,889483594,356594984,693435347,967781679,401435494,355846180,333596320,628919505,303558980,984974994,113643042,89409518,612893129,122412730,114900098,810658251,247580260,945287301,609126629,492005778,772356444,361927818,440145503,858752994,174471327,210890472,769016792,638211867,546015263,377533141,892710683,705066724,412035898,913706912,989583745,102815427,296051463,435828877,627348761,994079761,369313875,909339708,172995194,816793393,474860389,821690532,962160124,246051373,970475428,561698902,165844443,708639335,918973613,861542417,207950600,197794802,563223285,448456804,787570186,926930606,566070711,279041721,162328562,287318056,191225488,14318341,585550504,409974535,697728497,891226405,200433586,381575055,638337683,483277973,755030264,867834356,962849947,821535631},{1,44,1032,17024,220625,2383232,22258540,184242832,375813872,392612893,231706087,882424931,687132034,689650073,577977876,303878988,24310937,406963663,625468735,582435950,41660062,421950986,98962940,938709884,758565048,969234571,703952131,900436492,658647225,285611947,399326780,419454732,205387170,983950227,49990302,189001672,62673927,586296391,184361166,506353667,438069708,256171907,825943859,951340167,368115756,522855639,198647246,263328246,450011807,434855284,725807775,648411666,18383140,128787399,387148373,905324825,158891954,656234845,213026076,490012707,365468167,200221292,298615515,290107567,35072337,317672326,60118064,676291945,898619095,494511021,35193707,681989460,255539191,6318676,181981289,309123618,769843578,942743189,29734288,954472400,463236670,747980714,175643037,260101113,77874147,589524374,710018290,567729062,854908844,767838566,521233813,535397022,395450772,519565978,430844324,691804767,750969410,915664434,335442962,327801393,599337662,151524696,372580414,756807473,202845724,578628778,324772867,495203100,594805038,176866440,134364432,797477913,981614510,128692174,938852792,42148884,122641852,370944239,473851910,935488807,532851475,689984371,438315593,696398812,66001022,428174065,54501471,80878480,666016821,47295976,813797397,317765605,714997505,258919731,82884010,661027522,582655484,361252385,24311003,432884688,368733632,23821090,792526029,846601436,536812192,29313630,382435159,426147993,517181759,645690342,270896281,775661220,283600768,240876557,135665693,104458079,616729602,497103691,828815240,86098789,998656307,754065783,488969594,91503702,52278308,883359011,733253122,448869387,985543203,116773170,582006344,860482711,481797421,498040658,240829616,836032529,195942841,508465042,970760583,262117458,515914406,802808161,784332475,374122343,146224696,841597534,586439935,244148601,788204315,767547799,776362337,510076278,624681830,364806405,36907700,539421266,800828005,512242954,899834647,163376162,50294413,18654970,84289561,55576943,421249957,34930346,752291330,162276973,265235612,648593820,174309283,472188614,715911113,367773012,121970433,269868616,883985007,980070897,514347496,412293057,574601560,116830355,45453500,562859501,189078677,827602581,712444490,316586780,733065979,840949184,60074648,135398686,424428452,321968689,410040315,273128858,471407472,574966766,873880166,875045586,51088331,163730111,878321231,726127318,966070068,992549896,363335253,89848987,723352311,66759579,406269326,227087300,150259572,36586234,121181736,671327424,433664784,948164313,657988535,451431758,352880293,341991927,179834471,17796695,709446365,576526708,534876965,620591563,749402589,628280366,213414310,982746106,780180633,458647121,527146575,210950823,363805011,571210392,912463620,153315485,532024632,427468951,230879114,869803861,964025520,480715223,895116735,766188327,419338263,475074013,158183698,899486620,551866464,830407504,385674668,305150124,25769566,438519248,46473036,427624180,723264512,651472006,264633252,457374493,476392005,982968243,594462543,141658727,489344824,433530156,442633667,193279091,506366676,618868695,731227096,902261819,499005142,38842574,647293009,470120821,963932040,826530559,427769181,52186234,243569284,806914289,77294303,605077946,125786816,193185124,669741115,146483601,421911450,244025223,607708016,920909811,503255382,458139691,962827176,614853461,60315827,350564197,429760397,252570002,854719144,336843776,342192419,596659989,924243516,172320579,980212083,387574794,749118912,796421442,338721201,731277700,423355068,842226704,398877706,643899462,276311394,413568057,530987554,558156380,825270018,71652153,764304967,575174245,41877959,189656159,729954858,472722511,759829544,285982254,921037034,543320666,873711613,829723375,146980729,88768980,242470712,9284436,325379730,426922557,253585643,473459335,496125795,212116723,579959160,525505189,681915634,797942363,691505794,454823298,342255990,994255712,284908161,275004161,935102263,472107098,948357256,856671615,528973823,649773881,963952149,308388016,911396221,251193820,721175020,199750213,907595892,491208059,66513541,911357998,28185931,408941602,745821213,601730782,8869191,260152446,11616084,492782894,282010506,115926945,586669273,760307966,135350671,730510115,701832702,230080848,284697593,182609947,968668397,822892958,20031466,582030222,113170973,44631330,117449096,742186715,393019551,475653487,44400405,854169605,417464027,638137059,767027912,156446839,993857936,340495049,620457258,138844665,409760846,178352112,82788960,388732194,649306589,798058368,662337136,564354859,463324080,651997437,151329929,798760314,140393196,82249686,534814725,624568021,130746531,950081340,74895509,582830295,80288213,896322580,930247101,961634195,343840503,151542664,791653321,891526646,512046490,292522561,321986893,483787584,926080170,410378864,504638099,532986681,138953386,701001827,64586773,800287681,592917926,845148767,612516645,103437292,360749745,802262044,905182790,741928176,827192105,608668686,275550867,759837767,768468707,652063776,969103143},{1,45,1078,18146,239803,2640055,25119048,211741156,609749448,185787670,784612981,979654374,245960280,15201333,958496287,21110097,315107827,742613444,350112648,551346765,22689059,646342016,52427180,113726997,20972491,531552248,493279562,92962089,319571072,658193556,921146440,975234478,32484025,175484024,620442122,566033382,228886883,301912152,137109958,37427138,531183271,684452057,239066445,806400806,345167706,766401402,659593100,342864185,793254425,754419464,829307575,253460669,788296808,455700810,203460090,299960617,672027544,662169751,130171479,226661975,16040291,641167104,11608362,92735361,828424038,151425031,757058935,838944903,705030989,271605017,832315720,525711262,695893337,524834613,616761109,89325780,498691877,390082387,413410547,86170624,733987779,857386717,121183471,378540433,791481061,602874536,895775257,706223069,9499,916233199,610175789,305910126,402086898,380865911,987929263,784720236,752249361,533065111,750214951,512527924,120069833,497034065,691332267,542878776,324018841,841280375,368737196,213532423,972352910,856518833,695976280,832491001,482258020,288928023,37469870,669147935,728824530,312167670,98462828,664815478,37466991,488559701,805407681,555656112,449333572,115257333,422614443,217564969,709154128,523463461,73425486,892488653,72758100,139084611,245397266,356349189,258341975,374070936,726599734,907199192,145474167,868900328,80767170,435742131,604761267,550372021,238314098,858506407,406280874,734533546,294613351,569709112,578499728,811514468,971780315,806793934,105431100,109183449,48863833,577768093,679710969,415227663,41263734,575857153,381654592,178237376,962188807,96401085,816699360,379978,698529453,815682387,657011537,324418972,693645417,573047105,308103161,882958960,454854080,319280881,638681315,366562235,558670399,767575020,418970310,599121706,533764150,589341596,935247125,342450103,752510984,17885861,270962366,936052758,754048953,578853463,395299411,975776432,660809842,714104917,664542262,888472526,460099640,981638523,92874960,177231620,389704303,815325394,892076514,810821143,435904186,382196425,459031152,355917826,128881343,657597142,768648132,489510758,615223177,785945817,514595120,566588750,607013232,187911920,428934627,690400146,385480557,274884476,214574226,202705516,78809920,768678876,104566183,54811645,783466377,78714677,225394661,571378521,194681502,425310485,768219090,304793231,206900396,615627160,652872143,605935098,888495311,608958308,684600222,150382009,670451269,632074742,29926906,676412361,727588975,541140282,152873820,396851079,644404346,44361987,675992732,795525664,898044746,408945421,518637916,428148139,754863856,398182352,901207212,713356422,978366083,314876385,700685480,450639991,507197672,750335365,694787156,659670168,536065922,58255852,874808151,601680063,300562698,308983506,144763409,291800793,77526020,485403753,904665596,240987930,592380858,131116194,318805303,40941643,253699630,655235690,431599614,508389196,766960976,64307752,83604788,642165815,298107337,143184667,782909601,97135064,800759539,594114128,462420032,946857620,578998109,847963761,556321528,57391815,681855904,181815656,486333346,837072759,524567487,328595763,549915998,810586503,921107919,625157836,520890292,832156974,502972509,844559735,189855766,821823028,625190873,310510259,495827691,683011136,462720297,218315456,558392392,789434995,973556645,730884239,996176654,617108310,869866261,672230385,823462275,454316955,569646417,836576125,486906178,189726176,941091111,447563926,715506888,259006307,152570437,178255829,705545293,756368978,655390691,445318929,656847742,582354283,964611397,757172000,601301680,424348696,51484783,19240319,282677827,308226295,848392338,155829926,371112122,224524783,972970693,890401898,186586738,229535528,744395297,436751188,287103606,767393594,221149011,725319915,148703291,142739608,565503173,66967587,579759051,568848401,146971072,400042251,42796974,930117091,516575412,958322295,49672443,25502320,669481138,837449618,7837933,569472200,125364493,253977071,938687542,347213905,923213402,374713215,103889249,423021360,42560340,446498368,893011213,263552847,473020638,594960497,638188472,306243047,631678307,460262893,114330448,196301356,120279822,408786998,213927614,687965452,221650209,761159253,159653422,237951119,705996510,183076481,962207888,939920456,729428244,527536009,933629825,48104537,426892607,222940406,156477133,294062878,856995315,562470362,935041969,210948751,968306167,842365144,520781012,542464204,753086923,742421303,62000597,644679235,71406991,633199433,272647461,452692051,412108892,971466694,51102980,982720545,17172841,800141833,835541670,112517201,389287762,451060806,667438631,372888210,71363616,925222882,974951293,516878304,717488009,957226897,42671831,558776576,623171604,305500795,631070922,102790598,482941055,578335399,805101814,173951677,379242816,368922629,730730546,873191134,654555294,282999571,122452789,92227034,843713012,807240125,801145367,399481174,81195926,292593849,487745170,77737545,120468361,275563695,294725580,329691567,323060707,128192468,940264172,278390124,237020514,693096287,868976326,357620751,777387506,600499325,283061659,552760619,551343042,374674126,67456147,355451755,309520773,188033652,438124708,963234900,524570431,966112342,609641134,592345761},{1,46,1125,19316,260197,2918394,28277069,242654144,877454212,274093151,658806941,733787098,12686768,373279778,972151771,700803085,323660829,529034010,15342046,14519348,617205005,151932388,986173050,673700068,544467810,964286681,515278420,556139518,340574896,558301369,203169010,995039572,456888812,641435231,165153057,140522292,660622205,195293121,536816710,963078287,7389104,204944482,754195920,468292992,782743724,983001140,866703245,496885028,44229335,385957410,278539952,468949573,420982388,313452346,869856814,98935497,204399132,112520568,660616311,229799510,228233497,492491671,631417681,54933646,149425728,621332861,339088208,164640489,629238436,824895721,154091091,876001533,408513031,998443240,581987593,639413342,564182232,919538600,946772636,882410774,972663920,656083562,92818,266781815,775781699,746031288,222736672,245153398,853395663,612580130,998160370,644539418,268757618,522753001,961290581,775849265,167666621,207332842,699178165,754169098,895892786,110804927,209717022,224332021,783584762,168756823,846734143,820517435,567375827,214226237,514413130,94334242,56417678,452070622,302779049,643793464,45275321,465081583,721848633,905142006,304646178,594655979,909007937,734286949,886228757,175346016,613908391,543890160,182181133,880150750,840065256,833202286,948664835,99995047,986587901,143761895,873393215,472341142,369663112,813013714,860504625,731747262,545041246,583231233,427381591,37913038,537312918,219404202,592801409,727962123,878247573,121527391,62101177,856133295,688561557,4927109,639161755,216890863,944378755,396352437,878653962,905668778,386987830,935008847,899701147,100650401,955831377,336099358,325599961,655390214,368725260,410912881,868037904,255016544,51552711,320078126,868474642,332377928,241406268,35418479,170587950,775390874,598922434,616742075,563583865,362204509,606438997,894815935,49721736,43588534,841088924,703571407,258771291,525460849,233015242,491199815,325653075,858892862,519655123,115437087,727491564,149427446,582972761,204458210,871579136,737982490,129452738,424878982,856725917,336920826,730532856,841738688,738232572,913319995,816486040,235770118,427698004,930569686,569011751,212446463,508105319,803897811,496189040,948372030,432798655,784691260,809769369,691850475,577558004,62715847,947764060,196109904,506172286,447735266,980867772,417186123,46557919,986790130,277584037,822619391,621076591,388367593,68342324,236699370,119970164,657351210,878868802,794459312,436412351,290870119,503296346,564802634,58773734,218770767,842309450,694735121,712067611,605426442,634737321,598847809,189964014,104895974,463967300,12836011,374171101,422839429,769990513,562838372,23465799,935303296,758855803,832260567,373886738,362866660,831747060,745193763,842521525,971131364,323409153,328965945,810807795,987986960,514599613,697337301,518676386,255182547,320862033,438306682,656059329,246817307,296427451,518314128,212813255,401599307,322632262,651271379,102975853,978392574,171788197,425477753,865141598,200230496,352371432,128877128,483645145,487174027,207964600,565016864,366179929,769999162,980709292,279413092,778963675,322935221,775556840,152203885,621120920,754303914,144652778,603456104,397495432,911648885,161631342,183072379,436197254,410415743,654211646,998944149,660332881,659092994,407158213,993390015,62237745,342306369,807083806,460112259,598009122,34231667,354435262,237881432,155417941,495370397,996923439,566380833,854227389,702509945,42544433,284265702,294553519,149363293,27077251,84953964,442875086,52560456,900402134,145229989,73758817,191009440,854994962,638721915,122661714,185868970,77283521,869275152,18655948,313026284,709600476,473812539,310414874,881320952,952459523,248120422,525865505,878780555,987277088,840681160,676792790,412115993,140030918,974129475,721196483,656805079,905290349,47935904,451920705,209356056,551066765,377150442,379611973,957219941,151470005,815021467,645207971,427463516,863082600,325313522,124436219,624577057,614877838,455973640,851822937,25478672,694724523,841056623,311625157,733217559,234679922,488590424,672460808,393534712,496209755,929085969,673429468,675205481,477828672,541309112,421475544,478494486,773959869,620756099,817295158,343366608,474968096,138789669,1261477,581929663,193727536,890932863,10823177,566850894,774883564,16714666,326523886,969386350,297903394,330603328,602435368,640131734,422205271,722651837,536164302,931111157,119137488,728875089,985577117,985476890,17918009,917723365,472997173,89115107,916366434,502538821,230961609,303908854,617061492,736625515,131713887,339453221,738950163,633262610,426758031,238112917,779917917,838020550,66019448,650675847,778117049,610691432,213274580,385410347,146924004,364868172,467790003,719723336,134820272,752419541,477278067,249134595,704095466,475445405,736299900,879265925,152926089,845846141,495967193,279498385,571884448,188818617,160584873,477296264,718325160,376134972,29944771,994040918,900529668,502667072,63109761,493032874,781301515,461834757,82343644,481132313,514447042,33858163,779555233,748165656,15592733,72424287,572256728,868353288,210902382,873738113,462082508,116372507,317994063,320661573,43412947,698165915,782179405,544478699,376533191,591100852,669522818,718785967,689856669,868867194,692259782,326169003,372530014,278822874,245059471,536750832,337386716,351509954,600150419,771930319,812137400,268506281,52663290,576040882,250206016,182636529,238498760,83748189,556944302,408365242,877381661,687598532,206936328,93325077,375585930,311118119,840250578},{1,47,1173,20535,281857,3219563,31756649,277324867,182983217,698763572,224340727,130185913,938338213,457596872,500667258,726272186,242531386,490324006,697265581,186365736,123707347,149163288,89978475,985283339,584841356,785509005,693590689,256394211,919078587,671307265,271140497,146527772,508423202,678732983,767147115,418422439,470469749,411147184,246424306,580998273,228726677,964726100,955513349,444565758,668191949,622619432,792082487,929348032,601983375,875985614,424117930,730694027,740975250,920167707,500437835,690210005,493329701,913508192,695611331,515433292,682059417,760833644,299135864,144219873,937695856,872711671,176916492,348891212,334587033,49595521,749704350,806067034,773327860,183297942,590517602,642228939,275941227,305722242,165986509,644370063,71211109,994092320,193064301,728492690,76982066,397536959,240992716,459846893,745186728,715105963,864528752,8495685,753272988,61740216,691254120,133693721,536597663,806042634,964981978,37162518,164112239,637759779,841824460,829311498,573961610,622092127,856298148,23010232,90428839,608194623,46765621,381935126,362962166,452925715,585602790,768818647,88708532,942042803,418311021,521378251,499003594,126819649,281499536,951375086,146412815,883657287,598780576,163659546,959278876,560517421,665346319,929162776,164983787,77699826,451232846,342897676,483260356,399557298,954841649,593150358,617703430,292815034,3827776,631211917,629217856,387782790,117795063,964508694,824603912,347867132,217932218,808071571,466159291,919428338,306867765,310085680,347929669,103137973,445637697,645585557,573817817,596387955,672995733,578127218,402908135,115353766,244018895,365778204,555835033,188328988,247770780,214263457,844226086,575129810,998900133,642186262,886066131,9933705,609621463,398319031,223920768,209742125,519163806,74615456,814536291,217678251,205417278,306418059,464475526,330591049,614947407,841330174,17421893,462387593,572435987,550253368,393354277,125715312,124567536,533400012,599797708,528236566,670562226,867851657,488086533,312725786,238592338,37063455,385067665,487783197,118051898,700641656,71282753,435781034,103306472,894876554,845215295,848516,105817111,455104275,971250603,659938256,173306291,702024160,716038595,487118454,170680030,880373959,881689085,153725278,74926408,143593976,537712434,635112688,530810156,750175992,211491335,495469862,938874667,906814766,530322450,654580872,345961757,642596517,63791230,944154048,670877958,937127089,186748489,915912734,209561832,276486399,229476817,558761321,226557040,227364465,312169979,745218623,741668605,732242764,141121784,862165956,612899824,26577011,945385273,251793938,946782241,731260038,244678083,406380914,904932224,539791264,681567161,903979395,522313639,307479666,592336384,274405785,808155145,116439879,610551965,466693001,783212908,356926408,441684284,460337698,929744044,6376955,718008169,946348344,771828366,973818233,895371075,977137826,380169268,772257849,31334848,472603919,411133545,814229722,268412684,269984826,925865608,465876593,90547760,192297128,107314233,564985934,624177562,939350415,164843750,127698384,375467125,733175906,272735725,449176665,148653187,981408173,518395662,539465581,376426572,523018009,244326749,117372211,788925566,998562683,66998700,958836224,912519308,243826028,372775429,817271079,249393258,980817911,290157076,803249202,54296904,967950499,259586185,891527285,197070576,229312354,227197980,799697366,938796541,780082061,90937344,484280959,41280132,365255061,357940368,463355056,931322797,484716584,549219150,927360223,836260928,974511964,168938341,138740543,617041490,552137623,940491117,311751083,797191757,581186247,747525174,464341615,45074367,877273095,118604361,820377975,651223472,330450797,299712101,798402816,155978336,76119913,279749437,94544299,576902970,337821847,762491092,205421212,628488971,912880168,293200919,74345429,106904237,117214135,997309646,440117215,601730010,44099662,275878624,579837056,734358196,740396992,105320711,497734455,593389397,892951024,375888233,469355971,904918031,759963217,159920933,656339936,82028185,635763012,494109863,887577439,747214684,51704021,870514178,310168296,344440919,671389360,63636271,867520663,253359253,809561479,515218518,735486509,595414813,855063768,809133514,296905455,403829884,13706060,521945271,406722813,508410711,177195219,735377028,927006199,631467156,561281245,747357347,2938426,465345595,461810717,851331500,936133185,709629669,764183492,336958888,999734612,886346709,929391292,283117585,489898780,493902211,377860665,233672406,313970515,130449778,925311516,829665465,27964512,47478431,502231137,77997958,450616449,231073347,922519036,577962078,74763491,840109600,825429573,325716083,462423227,684091307,610980133,146344297,230702558,840583842,568780809,837872774,467777629,918753619,868791683,692922864,937076083,487643358,553595896,717484731,882361644,739294901,547711612,781629368,821302751,368923697,499416921,374122329,146178192,867117817,743635071,435195107,43377741,23687167,878990481,99110158,262344925,137035868,292609610,625408058,171070693,281506530,350758492,515834894,237732608,828774443,840832942,431386878,857791323,291378943,894741249,559570546,881728336,216217018,497590589,210577047,706853900,528807154,595327246,243687205,679896105,276389715,520651743,981854062,782051052,628779694,482906971,308000266,98460224,329039027,663453182,866909422,358447817,756042580,103701857,530184673,82157052,864831037,833622836,129557279,680891914,903510655,223117879,584910098,872789802,683398377,818673921,424793316,162530200,461191009,233747923,764377859,866276050,20068038,599500015,419525268,504837656,702339633,161478719,731429464,9977417,955013204,944736389,868359658,303235910,570685307,762022093,973456873,491776893,191155949},{1,48,1222,21804,304834,3544928,35583250,316123172,530785426,505824986,901343166,615485588,789348648,698747334,657848248,964586458,476943547,698458295,801769019,257736525,542576587,933572174,9542546,488292838,779820677,404677231,568188493,931045218,340825658,205993974,185959269,78058729,445883053,431770274,625502333,180277174,804167964,894493650,995189957,934651928,779076648,286076285,196236261,433504295,796345349,46608071,262327913,615865530,569486410,232121371,86175778,154003167,455565337,592635041,449778081,946011559,315342730,523152035,660192808,984322053,918448908,362530845,976500024,826353996,979299043,20455239,106430716,169990095,856925551,339927417,872925000,454748405,844111855,778706572,953334777,367875579,54603227,952723870,746089521,114899675,378338080,515017450,901556480,75514717,118586517,750778341,164215503,398032943,932771419,175973529,371281707,414155738,136305212,176477492,529591042,473449712,104580388,917944592,711611694,275529831,657391663,618370464,182199238,863262145,671572410,926093081,964697471,20599847,886336884,976845790,332330830,936899217,469444206,333826539,382006323,404644652,86283892,711449573,711524895,240243757,137744674,52585102,502954368,568353873,424768720,673699213,453807002,277591996,614231800,858886730,933633627,855960053,795294602,320736325,160050137,741837408,875372187,933116510,439299086,339530899,998809886,988163112,414204450,626581582,425958595,547450689,257877182,25212376,487090639,693248108,736165691,261048117,530252319,667332870,224234420,283256778,493030047,381167115,959191937,567700201,408470930,456733167,877572444,640070139,177231251,53889209,630925282,764167042,903138510,822950867,161878067,741376139,620673064,828400388,989198090,398235498,335164252,650259410,895482301,288920533,986020511,960531109,692510577,743863232,159848129,639142915,658806616,286815941,569150064,996156909,474086872,377428234,108191201,968576455,934066962,520785392,648351310,322768543,500047228,717012630,366640002,617370336,747113890,647615517,420668064,485924194,28548015,242698362,20265134,481161073,780894508,716872330,925052871,809234518,209608950,454869307,42621234,266915957,548835092,11648368,200676498,803279760,609790836,522043768,787672824,264643232,571421826,762085826,854807719,119023111,660310435,945098645,838260736,592383406,728604232,586121308,18945549,62079587,8000021,137221342,936745518,867913927,937623778,183088542,624248829,606106136,815005922,728188591,164502140,885086995,646575964,60630781,250914884,619961376,835493684,1794097,350786557,222634027,605402916,871984975,140157610,784428245,701028584,784157139,199990301,49282014,806191394,544636448,696393844,625422532,306981977,200109353,819880255,622554727,966234587,1715755,884432882,186517679,414057470,559202957,356291776,440462056,76496043,54502936,82793754,693820485,333532789,139408482,538301356,908601203,663844984,277481039,494620179,126148065,101563902,543304970,40138848,255494176,250466774,181548534,183041503,553027506,468172977,571880068,685135214,70030015,431414252,965377675,285528459,577690235,3039911,424468115,149219671,315258608,442938842,340124780,620577523,697442435,606981307,195766252,513624332,160814831,144529981,626344971,929525101,167384034,985564306,757660450,674490248,404160553,218780132,253152109,588527766,276135385,293545669,229980166,406532593,544661736,944987368,74067610,979465423,367319108,691015763,308068787,270297211,892899529,571121326,682341094,508186314,992592910,570463576,551864557,443417375,102996223,180706669,66278518,547390018,97982020,377733797,642211092,809569594,442856622,912786312,563198351,549331531,576357131,891027263,77805689,816522985,731749256,313952972,411776160,795006290,22615421,348238413,716260746,223962550,78670864,47765882,267128253,587371111,927656165,192469863,806624234,136996971,759497678,646978177,833527505,472805550,754214240,960030895,232746388,490616131,420542303,904038549,210637836,74285318,144447351,742135765,244372617,87595635,852731251,594678505,794681848,228154101,363702627,673985808,239196945,836249623,602064792,462168907,430511049,331217937,84426505,529390112,953694258,768941491,296949641,617567965,759210871,554347066,314959464,855978152,459336095,416019714,554419893,643616814,307318600,193723511,342506504,737708842,961578294,644413804,283651295,449519877,262823100,438065978,195660179,15479674,929627357,712657286,867475048,618979059,615899609,290553872,46585860,675146342,899293157,138576244,932939832,413352510,228638502,577046541,52412367,271101119,704058715,716195674,113738084,976781966,417637854,201849275,137988263,703452509,833173534,774723430,98520292,647910333,702073064,101667724,93613248,4773372,993672667,598539625,298728331,547262186,609550837,42278975,203431476,764589375,791435299,273439277,15186943,247517820,332116413,672582410,88991345,573172714,370502342,495515460,486357723,529038430,112617630,9655079,54905538,630913486,94540925,694069860,101033114,601510215,405093272,877399916,606786230,712700446,365826653,440611748,222502187,628732942,260127071,415183336,331627148,603111841,484627861,252203062,603610758,918118836,775502591,558836403,458735214,903545723,229008632,239177179,70767308,751925156,652119146,980361868,450630793,63075950,714904102,795480239,196855664,446357279,343343138,751184330,353543327,265335039,291055365,141693974,952501609,772988967,982806649,295006336,142133453,389243658,551050114,837354729,288032982,926886748,940810321,996269340,544323652,123254721,449847916,164321665,408440169,540527971,235735087,384560805,888470688,711171300,414716347,219479361,559050803,610845133,321258507,296543705,253557800,771631909,466270561,966519146,100544233,474799959,147649345,956135303,808272257,279282920,472357219,422709994,530025514,999788009,64593897,709199531,479060735,311654131,943520011,427742758,799287390,782392773,191335024,830990096,336010037,237942831,237453992,695887098,398366572,529644737,344086296,862051533,684436865,317549101,968659087,366641438},{1,49,1272,23124,329180,3895908,39783804,359447204,925733384,746545659,165655001,158091124,719304162,111160209,171158550,935012406,874008903,988755604,608336289,351327718,211049418,970686245,441380023,920727544,396494781,218114186,934368772,753990221,203263446,488226646,946324350,642441651,816607227,122420091,629716118,498106515,488881569,100763230,814241373,430998026,986590664,188596813,238499794,887765759,719310391,819612870,840885905,584773429,811468143,396065785,368868801,299761844,617462619,308704442,206242421,833439007,106715469,970135543,972244832,66232618,207050932,577078708,955731123,103929249,632790957,297717977,280927805,856143814,140717794,889342899,570959166,553036683,311778062,833874032,321035571,629235909,60666525,19636232,889773198,837811568,283828621,499062871,459250525,468391935,389843786,80632526,462481073,859711240,66143264,831825780,518914304,998480225,496960804,480385724,483317701,923742113,771054094,630267330,478946945,527928962,674723787,882998613,123711144,324674723,964132061,961988031,65215295,858250635,924300325,577545014,241841560,172586320,726876085,210684082,897202470,742850020,161301259,120853804,344539574,836860211,667275920,72688787,930704832,179668299,861726583,168665810,834696469,672920894,419563732,302874180,454615268,934181182,119694911,779976833,216225187,244379028,586838513,942544272,397970796,155525782,435250288,609294947,697035870,790138207,313089121,451259481,904475234,15500998,428233316,352796372,805867626,355791012,191743365,390372515,86113794,224579645,34292553,472538607,244805809,799547326,350596592,550928379,248605526,858957317,809083222,418025439,717379009,843111164,748566980,795763411,344249103,246799165,468081584,533360568,97839725,814208152,370784820,149643652,648814350,586462723,179226570,323415874,413399345,830824722,901264775,785155020,673315179,883230707,320461657,209574161,896187167,641537195,580708044,615201169,907420567,226969633,44823693,653925850,618905940,556249274,683808190,595045606,406684866,817926872,498013040,741888764,255307898,750076370,226664326,45791371,138249186,182084615,925519009,32002450,507648904,36302093,164244320,134446595,176304234,443232913,204696272,377207389,330407781,317016375,255990328,346121343,776903928,865285835,180645765,94169320,523805568,66571932,958229276,706032441,157122799,174128102,265560802,960871567,814597354,840895548,702037,848074074,17426708,276377856,55696613,206160180,32721003,453495162,587538197,204676036,610254246,936113705,842825687,202272844,145230437,624393323,739106533,700708897,523328161,691038973,656087189,213848962,927815456,921255504,609475698,113463094,529085932,807792149,579407091,163833313,694176222,471399591,346973697,718259544,297359882,892552532,451373341,120883534,8029910,624607649,606649877,815313728,231664869,673443919,615486405,94571095,110823650,950289120,646876432,928906934,684469503,297251947,919054473,285157267,967739040,274416446,465229888,656873003,825576691,53305194,539107135,609069516,669008004,585520763,526072937,91836656,101778461,538228891,424599066,719851020,234795290,701214554,914481398,497763115,504286064,212679726,409710596,134500525,154608785,554889670,267547678,851784437,749366191,681515762,587313005,604179607,297539881,51380469,30897443,988568867,430543091,168358864,325894509,131217074,122226126,289735266,2541560,697428098,339809826,339814711,568813016,256466301,865405619,710940331,7424767,660900037,729644940,444,450105203,690939247,459755659,92556107,42398758,782901298,483436309,73995240,784415989,602791285,655683750,744368335,684929720,939318197,1937536,94209990,544006669,195169186,297173575,151918090,559870646,425964491,818978660,571568643,60393204,415731654,547756555,991386612,383053326,997830526,963081859,107336308,898219937,906988404,550036125,981857264,691293427,481189647,501756531,316529056,476096058,168221459,165690115,553028411,960794528,453386272,963889156,71983103,494867184,462967097,635240847,989817132,23786457,968645733,163475174,884798755,971346358,8231228,947835970,751371876,21594745,702982989,997528759,30899466,874470660,839706683,64336797,183002010,415355406,851375333,802315034,662347966,459017349,83113197,807783874,686211775,665742332,548408223,38712773,947065654,224142524,544199777,554457822,161813447,59932464,324817969,826816639,159675767,610260222,802832692,962264291,230527850,654881259,493134625,56109407,491401533,163680598,892934948,889185132,78662275,741528574,616484511,204394884,120980232,4959172,884202370,468625389,987185268,797914336,292935354,542176515,965256954,25044127,701524209,669825969,264620823,983915826,463815578,325409981,142164710,946513145,626025918,890502327,456729879,921471703,889764153,10834930,550258959,888111963,456661896,560525119,254574198,379302005,359197537,748972811,432885247,174603143,495215302,304225805,499574,89067439,956588800,479903186,900293862,918419160,874312513,779518268,750190343,34999197,204187488,29703716,310295240,212734818,705461990,880565621,542764103,578132976,871657196,920555643,635330221,603836039,905337022,446003049,531829391,914627500,109964459,793773872,883594493,588890899,761763418,850946563,47045637,406265955,398330580,175033998,98562597,74022406,109783010,888406279,62923507,851720727,920064661,659715101,731241623,740764931,68490942,26861674,832409630,156628069,65837301,277330611,504531610,621094682,513712789,824543274,863846088,522929299,50674845,205053841,391074024,703020653,598865065,977680558,126857946,571772915,596794646,195429545,328266420,36051456,451216030,522276964,948367998,561406981,389510759,585943971,108053297,459413669,288907310,136029766,802792879,520247265,414339912,337619243,597859489,40005835,350918,321070418,199829979,141119131,515535428,350920730,314377413,808898947,900198037,799762368,570476717,244997759,402733111,626061442,103647198,938528989,898060580,652361018,641847472,149112119,134262079,887185896,606038263,859408453,950373236,692335861,405660442,565431386,959094106,393940636,423632434,612413824,143336067,663257107,9730523,471491852,112828340,936303905,998673093,55233966,416039620,144081002,565258672,539355694,202448366,14002378,539019751,307827209,288622328,788194350,570120788,965430343,472467292}};
    if(k&1){
        cout<<"0\n";
    }else{
        if(k/2>=a[n-1].size())cout<<"0\n";
        else cout<<a[n-1][k/2]<<'\n';
    }


    return 0;
}


Measured memory_bytes: 384