#include //#include # include using namespace std; //using namespace atcoder; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; i--) #define rep2(i, s, n) for (int i = (s); i < (int)(n); i++) #define rrep2(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) #define sz(x) (int)((x).size()) #define ALL(x) (x).begin(), (x).end() using ll = long long; using vi = vector; using vvi = vector; using vl = vector; using vvl = vector; using vs = vector; const int inf = 1073741823;/*2^30-1*/ const ll infl = 1LL << 60; void ansYN(bool ok) { cout << (ok ? "Yes" : "No") << endl; } bool isKaibun(string str) { string str2 = str;reverse(str.begin(), str.end());return str == str2; } //memo double型: printf("%.10f\n",ans); long double型: printf("%.10Lf\n", ans); long long fastPow(long long x, long long n, long long MOD) { long long ans = 1;while (n > 0) { if (n & 1) { ans *= x;ans %= MOD; }x *= x;x %= MOD;n >>= 1; }return ans; } long long modinv(long long A, long long MOD) { return fastPow(A, MOD - 2, MOD); } long long modDiv(long long A, long long B, long long MOD) { return (A * modinv(B, MOD)) % MOD; } templateistream& operator>>(istream& is, pair& p) { return is >> p.first >> p.second; } templateostream& operator<<(ostream& os, const pair& p) { return os << p.first << ' ' << p.second; } templateistream& operator>>(istream& is, vector& v) { for (auto& x : v) is >> x;return is; } templateostream& operator<<(ostream& os, const vector& v) { for (size_t i = 0; i < v.size(); ++i) { if (i) os << ' ';os << v[i]; }return os; } struct Point { int x, y;Point() : x(0), y(0) {}Point(int x_, int y_) : x(x_), y(y_) {}Point operator+(const Point& r) const { return { x + r.x, y + r.y }; }Point operator-(const Point& r) const { return { x - r.x, y - r.y }; }Point operator*(int k) const { return { x * k, y * k }; }Point operator/(int k) const { return { x / k, y / k }; }bool operator==(const Point& r) const { return x == r.x && y == r.y; }bool operator!=(const Point& r) const { return !(*this == r); } }; inline long long dot(const Point& a, const Point& b) { return 1LL * a.x * b.x + 1LL * a.y * b.y; } inline long long cross(const Point& a, const Point& b) { return 1LL * a.x * b.y - 1LL * a.y * b.x; } inline long long abs2(const Point& a) { return dot(a, a); } inline istream& operator>>(istream& is, Point& p) { return is >> p.x >> p.y; }inline ostream& operator<<(ostream& os, const Point& p) { return os << p.x << ' ' << p.y; } const vi dx = { 1, -1, 0, 0 }; const vi dx8 = { 1, 1, 0, -1, -1, -1, 0, 1 }; const vi dy = { 0, 0, 1, -1 }; const vi dy8 = { 0, 1, 1, 1, 0, -1, -1, -1 }; const int mod = 998'244'353; const vector f = { 1,638474417,876712294,949283602,187142323,373341033,70007868,501927483,796024455,542991096,45596018,283287674,596316874,417528165,191166323,834980587,914550501,688948565,104964765,393032085,623627864,982424362,446366139,407729297,330880448,428937595,897706118,536236563,860856448,945501487,442819817,57092875,14554181,511596111,142128101,499710224,406984354,372247494,788080221,634098066,833655840,62174429,217507999,826634010,531854347,83857087,391931702,60435539,346814021,201876905,295201906,841028503,595254166,288961565,372617820,788488293,214785669,586941976,798836079,121559584,671639287,905745233,598047083,524126609,332670261,849315549,108180821,330441070,822163165,644097424,597398273,433824922,821516475,558211762,643537971,813259672,980160849,572408921,491147937,662387095,732727656,426783046,336239771,915978376,384818512,244038325,482374615,763456553,670866031,970700529,122642896,307259936,552245646,334904481,700983666,310517972,122041708,158837842,526576992,154265204,160030060,545120840,594484528,125533240,932427947,483239722,888547621,159892150,204604906,953194755,683879839,710198568,40172755,230420112,590157392,712910418,853172441,199660950,89366316,958564551,384710263,193777777,252902665,629222215,513947030,433880730,305993854,844300169,150494228,12034969,844360005,736620499,880392466,621197845,316234919,513089677,600187555,162637844,695714167,580355949,101492974,190978288,622545330,630593004,159596479,959253371,446760507,188808028,19289865,438270265,957629942,411489774,833415116,639147854,1858960,678615452,368475610,97606564,682682315,412424033,34035221,37308241,510346646,745591849,319020540,56734233,74617988,329751033,819215905,147266093,524027922,36811456,183951017,90677883,584237732,31729117,528753617,356071602,259079578,313473995,102311167,365600946,493073744,775455687,826897016,330331487,882716777,345961537,393771832,816774574,8332991,908086460,824079438,223282259,736669190,832392662,649905009,546421210,220312447,872186518,545208507,526440874,564560841,901016661,820215494,594075875,630254812,497843223,451653192,281875122,318497156,281077520,391564011,985402237,281589650,859275605,350331071,110566178,929486824,82719024,300738984,340522732,805325367,223689578,40359077,767818091,906934019,216541952,658294019,303213536,864118508,997822898,348600216,835484573,573706739,878131539,195969604,73732226,756919022,619535652,316588744,178145620,401222720,940074300,885534177,812496962,722316264,348438629,575985717,599834990,213689172,103783113,815021282,860400524,861687482,584871249,676542561,346129673,766275603,579782990,980836133,461343290,169564539,517235481,911472795,54096741,861375995,679025032,733542862,505796205,417876813,695843405,641311602,951286622,604948489,363266670,366263604,168044071,483981875,961681722,335481797,610724444,310772360,380699882,338568924,730839588,429184708,245641763,544232708,20274450,393495668,841337447,563955060,577941262,286164023,435793297,602069285,552383730,550046860,387930530,760025067,885951502,401178749,851255079,19132477,811438469,584572864,72440788,918098612,204404247,720976283,255229675,333853788,977151551,119288377,650770098,947701400,464060630,315552202,744889435,586537547,456191643,333104526,4390399,292624291,117371703,988378684,984089998,234426668,331300777,566486504,911513273,800612279,582125752,283010644,749562308,858022481,684870615,909030347,68685886,708205284,701025199,995703398,863814074,828484950,932912293,464037975,462924258,411054570,449870191,939830261,425865548,390266531,838670730,531580415,983699513,566538086,708853823,566766129,831192378,206579820,37308012,179888829,174920451,29923813,301188781,741829521,657979351,821511104,590730766,593164676,231588061,800834612,245884933,936704636,770845925,303004806,388137181,135272165,173112946,247687458,676146427,589312043,205628042,272876741,41047791,963120036,232528387,705428274,775817031,266419267,669489805,276979681,471733299,107060302,937835947,631026019,605154426,877328108,7362571,506268060,522147012,347010609,897850418,570335076,6177705,771152172,713858514,178011904,689869762,936268003,193864340,666780762,699888911,676150645,166873118,922700952,666879233,380386949,760826274,443834893,725706872,443657887,735740462,905906528,328979964,72564175,197593783,486514627,226471935,470135404,497601756,382643551,366208505,800048116,954410105,171703479,749544729,934051883,186302178,117565665,28515366,556127188,165302301,517407446,832761782,129452649,393456657,173655801,925142654,39806322,297193538,419427422,320214110,74672160,478922755,198854937,951720077,298024541,871933197,394880724,822553534,390632053,278310054,693543402,821825588,252104595,774273828,870541371,413412181,468705875,153029405,173049798,447426627,112732874,512554988,689071146,385605303,209873720,282897103,232240472,693187928,346011894,928693088,882275125,876497899,958225129,305917724,451486982,630091198,356048018,325679625,67310823,518026008,459335532,895187265,705767517,603655893,128774695,648690264,808258749,134184555,506333429,501958182,375160961,575505950,393573130,88195602,827220611,748694047,68190615,214323896,281445790,156691339,916923649,939065335,276074031,822569548,11597655,326103418,552199946,298152608,439461455,314945688,738026177,694814243,671139951,623015619,752565984,717432981,385460530,711326704,555396846,317971426,726156597,529769387,554596291,898735222,603182133,15019057,640377761,216846033,233536009,338335716,695413992,916128300,582989351,486482314,392473715,157046045,440133909,979645207,171001823,980701383,329609648,362216114,665296408,305452149,443404632,435848803,826373774,467041349,451783592,361204798,470555993,502324157,903147162,308057484,119542277,347833149,457648395,434959642,708454989,106943594,372490496,385510728,388387295,211933849,458819803,592329486,904737188,32004291,829555360,71505438,93458558,78988746,132150611,76680600,241322250,889907850,454565719,577443503,91306733,33396591,54296524,623828097,729012741,489271002,569749913,718586252,686156489,214043693,561649640,521131116,322168493,713476044,745829775,528827131,445043596,115925492,63602402,267362755,302400315,923078390,40685739,570334625,425218947,300566622,154721591,975635122,681055904,560006512,39952100,991716635,548996041,222059821,925368876,912995247,83494668,474854801,477211096,257118263,498240557,945994695,297063515,343363294,922935675,212820659,810862062,276719840,833792655,758360114,772735541,877820275,984614775,461853093,148073889,770537802,186103548,229542528,741797144,308010402,482353858,819735799,687077719,74731896,30003378,63710828,532365990,883977343,930484262,656311650,122275891,879154192,915887245,268372735,173770156,269873549,377742973,51275675,941222802,545484874,748280238,46486013,58593926,677432735,738257061,21881554,605854640,887710995,474842829,674783621,267726409,553978642,891554540,700451655,7073772,95183385,848867625,920632493,400176109,409080008,234032702,100988948,333528883,697644778,97522948,325275913,515496652,235673487,390377694,262800898,45987398,897079383,57638961,790010794,30413416,115403281,517050512,692919799,360642718,461749160,76590405,13198445,567827302,505712943,935404028,567109428,424654706,577595408,946647976,882088760,383892745,658474566,145066889,339045014,288595133,220173083,809196985,488724138,715797300,812500088,390872748,198395437,209809677,251680896,139804320,677703055,663506382,695347814,70091750,292264493,306871020,494320490,766389361,40517433,367534638,25494329,923139353,249490179,12629586,299070408,870843400,211756561,659238894,850635539,504698718,569606286,554227444,952543806,110877109,65118888,558805924,853457929,445252148,571935891,22129538,979023484,188912279,256281795,695965747,893757562,763080960,305074154,65231491,634938288,912911566,311587357,375993408,546541568,69072133,939152092,292698823,790020967,405540822,155093216,553969206,817359797,936036643,192543744,749696762,915495697,381995158,316762863,94140449,963086402,413126101,979485745,37563575,158394770,544711799,311655841,933641832,243010205,963056710,724471925,602491279,371919617,802417742,619165135,334646013,624328585,232957550,214996303,162030595,574791029,886754778,38088885,326425271,333007835,722417626,211906626,484123887,743006309,283059531,377929821,590008446,14252420,558071312,848568426,743946412,409141798,248332941,796671445,832357368,988034679,631542916,162026842,678384283,172276641,405207112,409675070,182634135,829303789,951352281,18063742,368518581,988977552,737310856,960325981,104121967,374544588,1884078,355808744,385892669,638607426,273169986,596868491,312790136,784653222,607304611,525479491,715745570,10606982,133670326,751377777,813926726,521733954,277617484,336265578,35834555,564087599,219065921,343961025,515203686,313632531,150286151,694163251,67384247,269647422,18058363,230943242,547708338,52161288,538224444,656121134,798823564,886184101,944959217,535498408,40763559,912779295,244779964,876020115,523124058,562910912,889316514,971894705,275052166,623016958,495867250,565227944,376005807,204446673,141178261,48767038,457684273,933554548,127826711,742944255,210864657,487318395,951127803,209305987,319788637,659137294,976295813,561525552,183064490,527803521,715390025,54138287,873594068,817557371,821228911,865854329,18862495,430238957,667630300,462554005,324322857,189862383,863799064,638544070,700943861,388911184,109394926,35807478,250187515,850048805,286059202,595613028,498643547,357103141,351853877,636456178,312649497,655494525,245942980,839700535,421290700,676412450,909702106,793598459,285843479,832276048,238607386,208830815,147954033,540440789,726437551,184348260,848435923,480584356,252862701,526417714,397798371,691522880,400731148,101133665,252522639,878164518,985130003,381270337,330583810,386147469,587766057,789544102,625975158,474173552,674313019,418033105,594767143,62163978,790870663,274769381,308013743,509456888,237717712,157045810,226519400,508818359,175635693,281117739,966318684,272047186,281918691,899835088,559379377,412419409,117153405,32567116,955814250,699002119,177896584,712896591,767682626,641598662,503281057,758380660,486826649,808701139,511479298,498997878,806172108,119444874,144672106,221879805,993644796,699534338,338909703,867251263,722145963,549347798,186743862,18536028,319624670,253251894,718791946,632859338,41814114,536832412,448354377,777914764,692260461,245606459,773628426,107128109,973925075,5034412,140617938,455404299,794274468,380138257,327840352,250512392,994876440,598001182,311999258,394484143,57084755,598687849,852238642,581475169,239270658,157807456,72355546,536114498,209498896,277096143,261113192,55917823,68847230,398487191,545023245,40258068,855448818,986549624,83919888,504174407,194807105,528902040,258157503,710487178,679847579,325341339,467945713,772086096,669569604,606089443,884328111,533760024,579210533,656709079,353885019,896332013,829392518,522716276,308491660,680599894,880836012,44551570,364866697,465201045,378473773,737358206,52859469,53140903,405642641,459387570,202713771,365800865,192383808,848556095,301134762,785454372,530316421,950807601,413840829,760334679,399586250,41923036,656290745,726780130,699590035,485457499,690001441,111874163,308669338,566931363,640827004,325669309,975460780,684479442,967269373,546969497,388689701,932126951,721695220,399980339,749602473,472949993,518017122,147559016,549687820,159788463,247686020,470114481,256847336,932446869,159111724,872185857,545826250,662205150,461871193,218592929,13037169,143212400,696437508,191849336,675932866,151889553,896456400,878703498,114186730,314795475,633895291,418918400,255290913,595884163,811539323,639511321,89805971,192443742,825671035,246883213,485041591,168382150,714976582,295898061,696818315,611070862,163789266,140289851,725068512,759880589,701148374,242300526,533042609,506130339,4302336,1294247,410992377,185688203,752958782,353070689,459320446,878306150,697876761,206837612,477909706,754669485,611607455,380493034,662830731,559289160,155312119,114532351,915834079,945274406,79781699,298263705,778838607,335552400,529216101,878094972,952119381,219827639,861214371,152422062,840903973,647310099,552748497,119063763,158552943,367416824,888392797,916525439,748635378,550383403,973366814,75923430,83240752,976001238,828804575,848259019,745478018,114887925,937624887,265623514,462421750,366707320,367924553,846993133,923119693,667227759,174378703,418329548,738133676,562397423,897917455,319069390,40062090,423511585,296804580,81800722,114346841,342324676,566524382,152058535,956276337,520288073,830957214,289941149,221190161,942686845,925752178,654416425,832452686,692205432,420541799,740157471,820977660,267169410,831220038,417005912,875493938,823166072,728454812,869087493,272641764,986020321,249103550,447660975,803704970,941778993,843439912,640250852,126594230,81752448,217214373,8090,815508153,467782330,888470703,192220616,987267463,124315590,174714168,973786025,267901132,889525490,660774027,125472848,951453479,50530621,220169704,437660856,19840397,183261403,652678397,91600158,591116721,308306707,942859297,354880856,540319710,774130469,313241084,31357126,164289049,319954828,850416074,139084582,737388697,781023184,924217172,108168938,917861735,148278528,105376215,675211107,883051929,31018348,760049296,315094878,154159023,305067968,438727956,509624570,607856504,385731226,966925552,51871608,740994024,733905911,672734939,614085592,377057915,215945066,457743498,499872790,124061032,201506295,817586763,992735713,623503799,704564037,138937737,454349886,35212756,559584236,518745177,504223570,218617689,231822660,457207833,125417985,487832784,404169214,276036750,84159058,784503697,206309646,396363623,734558079,731642996,994932386,354883510,436335309,424180850,289803077,364805944,902810120,172325720,433186147,288465914,715164617,657816003,481162304,308380947,148254302,434327440,613474447,884361465,18333316,254468146,558956496,816835037,211183995,12935086,796392703,721146367,884294368,142185445,351491725,640398562,953769884,977697357,346680870,655645460,246888672,834595531,915915979,972255064,535812389,748283012,420850780,91321067,41972562,521902115,230370581,207305412,394878806,853009537,67016984,371104474,633565220,785313954,611448374,48682076,283884744,27542966,766466789,191863723,64748124,151779940,226249422,106855733,268575910,489360447,277752808,212604510,498320579,735304770,361275315,896425714,663194414,788340653,445854390,786336279,805765546,257110521,611105022,758611451,805161272,729706424,36746501,330158910,596485813,468129309,200847921,552903430,961152460,556713989,645091350,981930399,710497961,62345483,217099119,887284732,315177010,503516862,357334986,718835852,913004502,599658875,118059173,487589844,292156157,358814684,907292236,247311789,116097054,863453020,281295633,812972737,643868500,121480868,951402810,328970139,85367035,633629166,362924216,396332115,395955130,818500778,125030221,181113364,499002150,164840186,541557314,853292312,565567804,704926294,820902807,423202591,82342424,339640455,811981711,761699708,734504379,62253260,457345181,373779604,246274415,147864041,680611489,113395585,707383766,592331769,925077350,694680152,770548178,990398656,913846362,245336149,888597030,996402653,699500103,866682684,238167074,543944516,595457177,125581313,600130702,296697449,264897779,112728599,572041452,903837674,799112668,384136177,337833945,752221617,529462989,376051822,480450700,494248455,98214173,90612675,603913380,173972579,332899082,350613655,526540127,408884204,802830021,961731838,590160610,533047427,759026369,346122597,195415572,236344704,110008879,481666406,873393028,131856714,594822806,674279751,145107528,59522583,136504873,669915134,801920753,159154238,44820432,541962510,220094258,645226926,727292827,747002087,777072334,389938970,676886948,713230928,391187840,231205897,972738828,752481486,415537153,65753788,690717789,564830671,474034007,564793640,236626833,600061073,380606083,457790341,205871960,323738297,23963426,621374593,166813684,770230548,723238432,118624235,243941307,287671032,973559504,80453079,816071184,662038180,188118664,398253464,78969719,358919724,561161036,244731384,861375753,676552828,199341171,111010963,404032157,15007469,410891874,293421269,339843420,269766986,752732002,336959605,14244457,377684984,423996017,841787262,331579622,268243673,491000522,182948540,412033053,832405770,462579521,693558577,356801634,546702921,25142337,152513397,691739925,737863144,934346305,596451995,694568954,527495727,652014069,462143646,876006820,491763782,650203872,206068022,878034127,193660195,463004387,19556326,504569410,551134448,416795012,459988396,10441940,919894484,122583813,394649223,922878353,419994315,593398649,604125596,278442527,519738858,929932476,963768176,456894764,721553288,481843872,202651936,882517476,846760390,498683337,976095170,15479729,702523597,772761299,325485607,336863451,309635269,949028249,538720983,884794485,745987221,624335538,128957299,489646786,789322533,659333765,509104842,171997372,922549537,394512677,77936000,386115493,50865043,387304485,923800607,329505251,845328908,20937461,385258895,49018815,277896830,541222054,690959202,872646140,714787224,911100363,614764590,581356488,625646122,574488313,500694157,819184601,369182214,90081456,538177858,587194686,937991501,993580422,375354540,416654030,558823478,401984674,193500140,14261622,639095619,3524514,646925471,540665426,216988792,847764166,413162692,304116919,365786018,963018314,734767599,407132657,229130073,743731625,952322941,211523872,16441988,661637039,144980423,477198733,840849387,421040574,150783281,979536721,805651582,172155857,547294476,696300165,773259009,577403674,649228679,726526329,802820829,617053935,677653860,453067135,131583878,305544461,247670131,176106281,632449155,929095498,593362809,843705280,644504208,239282036,758940975,242888980,30419459,162331951,869616430,959052755,791826050,985463402,962827274,795721179,930624835,122667284,261585206,516321755,852592530,390947948,69222814,237885042,737313828,835951835,389749648,587283246,111276893,452997345,78828708,382938777,638584664,488166208,455856024,651142160,818863012,590612592,137660292,914306639,832413555,939806618,491319468,720784236,420320241,899336396,469676688,386626643,244467770,668695145,496733288,96791353,949582565,26368504,330290904,731332496,295027067,182188737,792857103,442171559,946989153,830308872,744842355,666885724,521344100,105160700,753055262,209908395,670313309,6285377,668715275,293075071,220131604,905683034,87247059,10563023,924835496,299223721,259415897,361668463,971100089,226968298,760740402,512017253,440777209,99649743,519917946,739992246,826265493,58953454,476222250,824386193,97151070,111960112,219436620,687289480,391726954,604890028,633652060,591607843,247747483,678073819,815450593,918048438,242366855,48354316,219270256,498897396,516432938,85284531,56995494,979294232,914659468,386972415,854842065,754079663,642786658,458603790,996212724,838103435,876705126,365887989,817047628,610073831,949716511,289235445,803644094,882832171,444094191,308045603,613338053,698025609,835786784,72480267,711468923,726172731,189972995,322888445,665038087,288851183,675202693,622429752,845794575,11584804,394994592,712810838,206029625,743809429,301029012,757033316,812819242,974559244,674180764,723617861,367711797,733215777,742398359,294876390,113763819,22035421,959486572,858559810,523005355,778259899,609124230,882672374,898089066,800576135,937766095,325993923,671629636,343145762,941601677,535448641,128638019,351097457,947031904,440740274,593907889,858256620,651200723,94266795,417593196,783573565,299272677,715624485,635292517,83086894,673298635,984206523,542843971,504474428,359478109,599533244,134519312,904684853,659955603,881173342,655712590,450046291,735928439,194548795,972774406,173350007,287321583,739105020,376902792,784491092,868198597,394283085,648465952,443703262,690154031,169013813,16422871,458780403,337974759,146999583,585161712,367061625,594319722,854563647,568434953,697502214,618177955,738141043,542099463,248007459,573994984,535084676,299174432,66628616,578943699,285943986,746900711,903903635,742314795,607883363,675831407,229731324,535915879,311480923,738290568,3134056,94704928,106243257,703692941,856066867,965907646,49633724,972242413,883520028,221925665,401920943,976270161,820696588,409911108,274832651,665949756,352639283,631573115,316896483,254970102,236277883,455338890,137768685,955911337,160454905,612745912,609520572,419254833,628030298,162620329,813282113,577741576,234193154,948010625,909727799,892454686,157317951,174446986,853284937,187596630,901222267,700818032,516363789,911998295,975021362,624900982,117598902,556611288,637288257,552836752,927122298,886216966,439575442,871469759,980162121,686321335,352486390,365457908,385975035,845606909,84924870,965740114,459102643,558220791,412374155,927606072,908613773,650237056,93379555,878832641,506664166,768668589,34507081,614249794,220035602,353631992,258388385,192152781,739238802,422199459,165913238,908362104,350255133,255263058,322575358,566073550,813032469,116007867,134035304,595475717,816674343,771449239,728556772,871861964,967916935,864877926,174031496,926829282,563096119,326549798,171259407,218872798,43745938,886925642,863565863,908752311,64716978,703211036,12775780,931947039,874007723,702731056,244643479,853945023,585315061,803597299,789916432,286374238,745768395,629141541,613676466,953559789,625414510,423855595,366145469,880336545,87335825,797531927,333734234,599650552,282280109,724671071,451165139,256297014,370248303,128761001,117377529,255028448,895870714,440724648,58852065,308653660,281552118,455980650,953662571,474075900,795392505,281348468,71916322,255585641,434816091,664197732,185792743,222918487,828285082,364856903,169212958,548447756,911828063,644503498,149123648,718045173,630806417,972393845,862839484,388854780,736227254,832986400,916456297,573433356,314693916,511764402,663678493,515575336,428068270,423183826,567900378,153529304,378440984,70891382,419733481,642060086,706239578,753773333,437238788,888483202,869729486,669908167,664990744,670313061,238933227,564423714,767739357,173199128,922377714,336564048,579196148,344355077,632912142,452390855,757103493,211287250,693195921,435745985,960268965,100189123,564150498,284209379,679960920,773087916,855479832,481827552,433802090,713277676,393934171,51370348,177090598,961178945,694093380,701651719,403061033,612179701,893262054,420881731,524045373,496971759,464400965,709844862,146178979,101615911,831753030,200986212,900026737,220987644,864484781,251718753,269235518,498311664,734686163,387016592,272779384,844520957,130659604,7080469,661917973,683379259,968404926,805217854,203956360,259240348,488844621,155358248,7529639,447193381,381466282,881783783,194512089,252082398,679935071,359944674,659478190,544001661,441485312,502082022,323738429,445719559,755335634,360449440,329588615,750732621,740782647,347511077,206794321,901599231,372193140,546525906,98613054,109218884,303110828,298050489,985524427,443773412,128459410,590893716,86282010,548033568,330887234,812956643,687294533,948511601,333772553,464112846,772333655,721084229,31835478,331916427,533592369,357347436,651001706,871975748,752533273,481515942,816679791,452722766,416273693,730387628,783543268,777115208,642920384,503085651,93829695,235070863,620014456,223341051,538597437,655989476,278056139,815903428,707971922,746721927,930661318,749801573,449409696,699287127,914153187,334885743,833938200,429759848,626291316,876302615,466041862,425565564,278985149,503803540,547723012,428105027,868403596,217613784,411643260,474844534,888238707,392534750,803473052,922186089,22753517,232218076,346631241,760590919,510661570,893678582,769865249,917928671,810358415,539001034,983538502,730641039,967064402,474310493,701394315,995370356,616996159,798322301,76591944,891854924,239300981,231721356,302285242,474417140,102429294,218582540,326973501,921448953,918617007,772169831,501125854,426068899,247200193,626622487,228649440,660946303,722403656,715477049,671794162,198467931,643696492,742756734,963103784,605152029,651545852,462660570,663270261,220884334,396881088,612760233,376483161,364187931,708582028,74340200,753818952,848867837,350431704,72059034,345111886,932474797,791216072,671823672,812319607,462569962,334451149,718995099,633125919,30988619,504541050,531213622,350378112,226166717,523443516,595389696,180591752,683141957,386814657,518422245,255692174,673365636,317446209,237594135,287092115,548832542,827056161,650760543,451479365,892157578,177978881,200411187,651780991,546182474,203041679,269285553,866093357,688684808,119366536,667327485,458663531,80257141,313316312,465211069,35032685,541239751,917768447,256667636,605313606,168706957,182900375,750117193,33032014,728508871,464039832,933488501,696936931,503930295,249619035,269173385,196063152,855789313,218680834,663053607,810979765,637623901,47569040,889679555,900453742,630540173,219548125,811351181,447157254,48293872,252767931,958902297,681449865,296218814,229958401,853870159,452358286,125943352,439152913,62402409,682301831,62801862,177076138,748259163,69570431,151191712,104676054,986063012,224735177,71921532,892227618,124164816,829872466,213177421,960467929,269013494,871688962,978059858,42926916,537087913,635832597,651741378,587610508,969123613,514588945,92440114,20660049,666765961,434279634,513856225,3907296,40501448,197524035,281871512,415497414,175477963,189098770,544177744,12585949,286592050,109328730,643691767,126621521,193241990,645469437,379407277,367253353,584459532,297457955,102052166,205393297,23840954,896624036,217127017,163298189,8264903,44123638,116360014,880054954,873938719,194598855,758373441,502483692,459233410,617583886,196981656,454590544,166464286,492245792,986843080,812441428,80557198,369548829,936650186,962390239,433418091,105552005,20590957,242273101,580971332,840528210,886788488,501678118,497580226,665147020,803575161,762288537,355493809,419413452,88900164,990167611,673447603,179294895,901634007,89866970,492495082,128625385,509849185,575987650,826426395,577256185,348974809,532070310,444568444,616059995,414194257,818744640,394411763,16232745,443012312,43908505,977026668,804019338,461389164,659160562,360211014,750462725,732686070,968896201,229855967,240982196,815178512,324741802,197991923,687413213,541144612,240107673,648599644,640036075,59809521,952962089,856505535,935796702,992905138,398599610,677556704,870177895,345181024,593682394,325666688,224925603,901456741,934223928,900203387,154765991,785527811,581404502,184139999,511100545,159186619,972405939,426214511,226316709,399705618,210830877,945243221,199203725,811858592,714155454,386454418,631101690,34547625,681858171,160235707,84493735,645422849,526859451,248807068,709757129,974220646,268994020,250959694,148576677,19371682,820097297,233191193,846957266,580279368,318300447,2191828,848633697,935092683,506687987,901220987,481459931,539567484,743569393,282424433,26691239,729073424,860597736,475044977,177903321,24188730,551556379,436357857,735589161,792972519,614286794,926316039,743034339,567854358,648437466,516167226,151357011,143068447,64707765,193691951,311273254,808637654,272522795,190701933,336563763,829880625,218058015,909075057,540927150,466246599,368855028,786112034,925898147,522559601,394220873,188514425,850407126,450378479,769707451,899612407,215311924,84202800,392017718,286251537,479544467,668806484,94214098,163976105,565857838,911406244,551435120,30019651,794424877,33218812,323151525,906613099,121701603,681384398,614217983,782493409,807101118,176055335,567454212,853746420,8181284,444528833,865461951,286653714,355689698,54954215,866192723,553631971,838853823,921280696,387622807,426963589,286620803,63876447,949322705,361760886,351755097,984061713,820629354,983685054,889135077,965214778,888573766,419062603,732044144,913768172,995350063,302767023,526402934,70552638,447453679,171297128,977070668,368190929,981731104,225210951,636262729,110954576,647142829,191882124,772081349,562980566,83922475,60634971,579150121,312895656,212904780,51568171,150274796,844462574,548478088,562983131,60949367,465284724,364394020,204715419,727814670,19533020,322226329,183566168,724333004,328063440,510592752,276171166,327928634,52458807,582501116,615419476,977524177,566574988,883205623,344382954,341370469,54122358,959181460,480158153,361934895,912573425,401918906,802684215,207544377,755652024,286207526,40174926,866739461,210824168,668830073,206707897,661720836,568479007,425142330,590246341,384156962,566396021,369414407,593320145,280606414,414163604,706877618,878128430,411742951,761341407,193301813,465989488,548370000,8294322,949836834,749570167,379912287,57885333,442312776,187044007,366933789,688081744,322956817,419699361,851406178,11470970,16574381,396315381,949643886,228086005,600191572,750385636,41785937,849101706,219222295,391667731,436444811,105083968,158009352,656087823,328736286,473646076,53766182,257034880,584902453,30645366,827091129,89255697,808411380,507001848,215162519,692374171,121469295,507231913,113371283,604947226,434264625,348763373,825243013,476935929,236199953,180707885,776822307,953526515,643293926,718439098,762617700,21874873,689689577,444935230,411423177,674797408,362026478,894030634,675610856,803407599,159242971,867608454,829317990,22554175,632441623,617679741,103113383,952628462,185446735,766760224,258447428,18653828,908749844,460774480,263006576,927429592,173685132,199348204,462348776,757681534,210505189,491698560,23370155,73507840,61082578,546791557,131196700,312895519,629521119,681666415,767463094,352900288,142064581,329771568,947466395,188075141,975254295,309980833,618313851,12206799,37792560,941195987,575749846,133527905,659767098,726730059,978464016,51949427,75778666,933746852,218322651,140975223,182431188,446201733,978860867,863081148,784719440,897376809,195234529,59215985,494052526,921785397,207637164,288903997,161179205,87496483,410436352,320837890,574761275,439197472,312114682,963193528,254232494,377078580,259779111,123471668,720364313,898211399,250523733,511621808,104401589,676568476,805430653,463263515,145770512,949841094,921085980,865596423,708180274,882749888,34421466,548465725,28277201,850756943,943124465,353052244,764676482,164147939,44273894,872053396,673013740,857553424,853104621,538664274,631078482,603216371,726262252,655407188,32843680,166861622,645817459,2573502,287526682,746744346,743415395,831928009,446508498,650675936,687752220,772287179,519795821,715948127,674418745,547498225,602427948,430682817,291573802,141075040,544375192,924112080,385334046,122457246,707697400,534072066,385643091,707719861,896026294,654245223,458599137,794973480,143513653,413809004,341001400,915004119,883782693,202936283,506579349,678515194,927303505,869723371,905943705,225376470,322770518,214589039,805963889,134842161,282857686,391933828,344786236,313106351,926403195,481219197,223555385,1629499,262132854,134241631,813415337,870863860,487593718,400034567,994489646,411670648,941947566,519658145,488248149,342071802,255703671,720345751,480273999,265769800,959554435,877283263,165910246,358859939,791715397,263553238,75187258,20591569,254623345,408753255,325742733,579224315,920778509,614310318,468381897,617209068,131146296,335001095,766268949,415812467,954507602,526825098,733227729,334226426,172922144,689116289,535405004,403406769,179969253,64404368,325451103,225526518,418067497,649367294,281500398,411753420,890805692,707787492,119743149,512318142,554603050,323708035,340819315,820453170,288791777,601404861,531223980,603644245,79767669,955559118,776543549,372220074,253896843,860664276,242484726,11998264,559823889,694440076,304161303,536413695,269781682,429452935,512988139,16965043,205340854,289691664,3539578,201516782,116563013,707803527,887949257,424238422,232483446,255336791,576699812,943193558,542202517,170958045,704624663,218525078,642896614,581561783,342882080,984289287,875554190,349751626,242221317,461546440,166393488,46283078,215255086,62719106,656243352,286856802,833841915,379629428,384759575,605918083,127003478,763148293,68866378,816889980,648103769,641544481,807722138,466178261,703351910,254364584,926419773,788080170,328101383,300255531,12272668,764588623,556901372,234501930,570935836,536663662,818239318,150896699,302703328,573048654,362191589,457760886,253151120,597554637,675114778,488712076,682666273,97856807,659315718,960720602,483066395,125217612,918256774,393453192,653799428,400574765,754407717,771557187,181366252,90432862,744965282,428394983,582547026,469528291,833100011,105941911,347140977,472709375,971630730,769640186,250924244,619201192,911615063,455505101,664888038,522277438,806851596,743371401,684492244,295015721,297010667,935209969,641382840,828050164,865849321,746857728,605166278,446540967,347501384,935640947,909557571,74277182,184639537,259740169,437082669,680081455,492480060,157247760,717849831,421012936,539598789,686012810,775930891,47091425,642877651,337904334,294758097,939702814,634761317,289407955,697394913,994282435,499082462,373510154,614689006,817232406,228169720,19536133,482493730,620838535,514470733,230157941,548753627,474022796,118113109,908934043,632727669,593243221,972494096,730606012,262131366,606099055,563850263,321448905,913053716,43517848,198766865,185475971,462639757,969237802,717327818,754075136,687419227,491401112,256738618,466415123,378938294,396799323,49348482,427810475,548266487,650084514,657976136,769842260,157654452,45589178,282635009,864535682,116075727,29550277,364392467,506466886,433009242,597572477,437247124,139292288,407711601,860830935,888075117,706683328,960051373,846540019,33107339,897387201,535478788,484854818,557635493,517661450,294565899,162511342,217062483,205744478,467651311,104852699,619284159,921277985,356522734,812398757,975099999,931348671,850331416,922547157,202133852,911644448,185843982,974445050,213986666,431839017,971838121,565653344,782023267,548304623,709549400,655045473,905162165,520984268,902585392,99643620,976386449,351584221,447646372,565860686,773282878,939655476,765305740,423340934,632684135,290471030,5250326,384359258,929815121,868617133,61134552,433879572,388051796,211234310,346771112,129206504,174671334,961617281,594139590,538485916,929147251,134088395,332481734,804218505,227575277,837008968,715146915,172165484,414513123,160338146,422332597,423389191,203272275,959400038,629800791,353775281,57259927,822018130,194909159,256644252,469563025,628803011,253303129,553500057,58621692,62265336,847264029,911205590,569138008,656402912,835064501,311060327,807745356,325963793,41770045,851685235,972563943,26001836,997216722,960411173,21197005,410848505,696063419,636254864,544071078,264793769,928380405,630020964,739636779,944529132,326416680,493551735,767232757,315266012,232619872,118842991,507865868,346707363,672814693,223884498,84257200,458917832,138671553,249651962,433490648,763248924,683631995,783724274,323097426,806826405,687559609,678021435,863392583,916736917,865666964,150907932,472793431,962204141,326189693,390909379,401832452,207892461,539523756,659638846,196236775,242726978,914688565,288282640,694053656,238224020,766752066,702430135,991301384,26327533,48486564,959173604,578270158,708446364,128348737,973395811,390269102,272450352,242912964,935396087,457085846,992293822,266144751,462441329,937839395,775234193,744816299,689343159,723962524,919211209,22646332,476631694,647844047,938060844,955870985,227655372,177284763,750185149,734597703,623256769,553131371,702429415,575284290,407468436,97510275,554701193,374065901,940057038,52138662,710567700,51855733,169855231,802105912,600825502,422314327,634951777,629007616,684764381,651429746,668090293,583464731,719169602,116171569,616812432,194256847,937385045,564737074,339187908,709896143,691491630,933240841,475119050,580383542,769560352,863914044,614826778,714502830,330903187,287066722,708653625,89312601,40993711,453398410,985909263,301084497,500502656,820235888,863184644,442130280,598410600,883448504,749063595,666937879,341630268,662528510,742839013,239329111,687465785,568093082,477812264,849786046,612759169,275968173,167565536,343568116,547413634,18591377,219622855,180185753,130492893,551027440,419142436,234744613,173657981,690071657,46219460,442202439,774014314,57953956,594749548,457967843,941600951,118999147,87259356,886460769,170661061,158013406,722587713,735915370,968020070,141775306,637073231,879975605,971483785,681248316,811059073,471564060,785513967,482003677,996872768,31109516,447222237,181002475,652981849,326727045,544563167,701248503,403761561,512560867,286769863,246661405,599797734,182386413,817931081,548034568,732454403,577221870,565858314,869105192,632273904,576015405,69656699,840824428,543991636,568602651,637587950,51052704,164564338,756326079,938409154,173511054,6544303,607243022,582059008,932096551,135289050,10958310,639019927,457576033,955084773,150007855,554955500,661745248,366039506,547538118,112487365,943192237,143936312,663284735,886890211,944241793,192526269,150059187,304711582,421779097,978912218,897983911,71717720,367619635,35934197,601096360,961628039,707365961,348991447,868093321,17532161,240232720,554915517,17028594,593450905,243203844,627280533,473830455,150029906,816617255,22691591,710239542,306093006,484500944,166787731,395829959,70255649,266006850,100549095,366830033,741557556,261743865,239580600,363963677,365610561,34907454,228474833,480542196,960130817,154977923,140260596,776408079,501529947,992387594,35596410,870341658,304180483,735069330,749448411,492517985,654256447,63607040,481760312,597887170,855437455,905730134,953297493,302709049,19997707,796751284,864674001,758058902,784924146,670109418,426832104,983588375,395529997,256962216,823017060,988402373,362087694,156010331,563804127,699526705,569026004,92568710,825833840,893106215,627152463,607701910,242958210,539880795,782699783,900917749,649774792,568342979,234683685,235886641,802308798,348641178,907910635,52626619,48255822,900552967,987893927,104361415,751843490,143935578,659229224,692200743,274397653,116909119,128019192,956811939,342718238,368411962,62806842,517517337,855038826,930711874,279150975,574857555,164854598,403636264,819869053,505965820,353417551,870735150,626316896,555340806,476520498,40061330,968603057,602650849,865021171,859223681,822203768,645007223,112455506,920327142,934433124,681051568,48663714,132654087,386398410,51991269,490913702,82627507,254146120,355967270,36134523,9322961,934786222,404719250,839561982,45758872,766631257,881129645,769619757,442215012,170653709,124794668,198591086,927360884,732614296,543042671,37844313,51855,333073045,237673023,391716915,163524507,684629909,362492290,842392605,116266913,729108319,671156429,98647530,623235494,736921347,490867505,743583659,22588584,206033114,993777102,47035168,746673419,659938697,639817999,978979098,682765157,975967666,441342640,649650998,382710072,53842115,261162900,560212561,650559057,806117495,817965276,757172910,361846034,548742063,677001598,757179922,698000394,586082536,862833967,591385514,339238384,602488502,801059179,917006691,774884612,909741023,362108083,297362352,329261613,112712901,150530547,559466893,561106230,668645110,175260501,158444563,2490351,540161396,224709594,107191713,140949492,675208713,347237043,660669524,508680213,993302799,65480284,74681400,218107369,738190542,551621442,573728725,320792950,37239095,342218055,137578883,664362197,865784575,178265160,526252940,475122706,677110174,632343006,854989312,777898568,443869843,856310131,403893323,204297308,367028173,605400098,555135257,41725719,357463998,576780728,689361523,919298440,670553151,446079298,410683143,769596520,704489618,274782189,269198543,935632811,801661499,357745722,608706956,516540313,536047622,474900284,144772303,278617548,524252054,221839489,586624857,571648819,221630511,121548948,299878187,349960501,770454472,938724912,541215360,156144194,134084537,503400792,881102456,436417672,549737824,650564083,29286834,235687447,100476545,117313580,877097974,528576053,444374536,716853074,514265102,379857427,127513126,558473021,373626340,68250185,887890124,641663342,601085617,79662192,727897980,159436401,713611864,440382648,106866216,265495921,133274277,494370766,397669108,150597819,441437965,986182139,262846984,790903732,684960847,415384560,729720334,888898363,138283489,140425007,346272300,568925901,506473247,651552450,967750442,167299594,459461496,717448863,305614829,364454432,272034045,499309445,632617040,265918139,627817019,876808621,493171177,93489779,120578663,890450820,788481986,460958750,750837047,209333992,744344879,675956768,380694152,738411144,400483531,443372770,272841854,168836226,80856091,895638820,9030973,33857526,840160881,429075627,898884542,446132539,594952891,141116880,887244234,408240304,747979126,772878514,225064950,132205308,848643865,242709633,210312104,109618190,426428476,114138558,671453933,452787741,842341383,281150531,661930289,974999575,557481044,85305729,459545390,466207377,338060455,559633156,759273275,971242416,526610238,644745859,220396827,97369807,146278719,667016107,977004959,75935354,669317759,79434494,234710504,557695235,199039337,766247510,297742086,239322577,986724034,224854739,829017039,815949583,801121834,855863254,576852688,550323884,197588605,176881479,312628197,723971571,261274540,416291211,691727676,170064248,982549733,918239352,869405324,103247629,847203458,686285715,29606025,144283037,913767172,861570108,911217059,870793828,173133127,377895863,100787304,882571148,293683814,253151884,276559944,503705146,760676118,378510746,227072228,641299773,435227659,912657076,367270918,147905845,4717993,544520679,507400049,481292028,123229359,633569521,217967270,473079883,813097823,7917922,869804624,60712726,1323886,798448487,429188954,775379985,143686780,421616469,230791733,928875954,503119497,279595365,768951532,899305835,669777197,927685505,439490384,529253919,504040630,160697694,777376052,172172822,882012844,162510533,975676318,733746295,313004905,958599538,479367951,168229155,3109593,732766199,296607974,275282274,180559952,603605790,257216715,250289370,806951470,251465520,532835032,236012568,335115381,462774647,749373624,144010412,913680176,25991992,56473153,988226999,720597117,994632301,789484878,184659008,12520664,470274726,328659970,918411588,905122161,282082004,603407505,827917393,393634553,664034750,200078516,189670650,685227047,29125900,109726629,140350889,956226452,35081131,499149637,59372704,406210712,748338482,815436688,29875950,325795100,368790861,499612338,922684200,110114569,486860143,210317316,929448376,107727990,395851051,843736533,34935797,272689992,713102241,654354262,924723613,495983082,958586082,408035547,510375478,880348000,921793692,931246800,645137675,212376682,801252478,294483047,590790899,235492719,582972953,616515290,362638524,59888024,977410427,270627822,776142608,792517877,542517498,500843278,233136855,284803450,632013708,245830139,734808241,275882738,583439582,330987636,977079279,805263257,934715482,274826676,200050192,318804570,206267171,52173830,6018349,261005717,727851802,448877017,278662368,377403437,585365260,503843697,494012498,789721035,244041569,177608217,248568082,71452646,206791960,527081707,24546255,881104891,39510823,942709850,544763288,947296371,422973562,647019022,645108650,708818585,20884194,739760068,421365014,191538961,354033051,830793308,522905943,247822034,851482456,904309832,959374639,432682187,881249020,125921431,589922898,94383709,69636250,962304054,353253741,673933870,279216826,540176481,122270842,142912291,682858433,474799091,705134856,549371805,79290685,945260111,702459321,4452732,967321971,386350590,899893421,91003219,700999068,9710951,421519808,515264973,97159599,227425765,725376973,252615615,911685911,55821831,21017897,97573992,804582047,9527148,352213091,148392333,505666382,851224347,239480646,562169673,926298379,599653049,27383361,524126897,239363217,833334137,7294272,852509887,48259065,400220130,901025063,26157762,584522336,578214879,220208835,885262212,598860599,855195121,118677219,144113925,18357870,521665998,589726961,786127243,464216717,699031255,475392745,669207238,869205770,524407684,220506673,689613149,675392702,923276513,269788265,326174225,979952097,647276845,937928886,498910857,893833404,199925060,277715119,802186160,661843515,634236890,521918578,589512887,12198440,727930564,909016338,186815700,844625140,638784295,571395090,810913393,468095035,212948578,34200904,31789240,495176721,260737477,19072020,758925811,767802285,51631665,768213688,178469309,185027790,812961070,373512090,579829591,336972956,80918046,852661846,635154227,155121988,939076879,120604699,749790553,467731703,217093422,892345735,610456697,7073976,99462722,265184771,800766132,573601211,593440479,333275954,81856271,565443008,208296321,827361616,779029568,177771146,190664812,49743354,974903132,559021925,827297426,151983506,653691911,153563523,208004838,285447960,959051187,490750754,401229578,897457477,256850511,637864251,674335312,436100884,76803592,3853000,140445031,887877110,599605496,426307178,588827936,232303657,875880304,810743443,871724533,877517411,910589926,308360096,469087458,421030271,431450710,536627530,414636410,351190937,196243872,78467030,979791243,886100267,45548202,290562055,819800516,647310799,8525751,147027819,621277355,965427816,857902646,636257427,822428251,110136096,271351399,412208982,558338775,880137836,665110057,620379712,35029149,500159951,520181428,507846755,676364255,532907954,696213291,437764076,958819736,598356365,607863542,97268896,81366014,190076128,235994905,509225188,364983542,984763249,988186568,815263708,671775072,937928436,462276586,15617735,575979814,716074408,641582714,43223386,484133503,788277011,216264505,586211304,118053291,804978770,396173607,285503342,345265657,350830865,448295531,781466241,717726069,994704486,594948276,66092643,337582598,782005000,443549763,1857575,170060686,80107212,578592712,207259440,253794778,870452389,790970771,969044093,302122082,351825488,364379250,735140939,172068509,166055224,798556379,630159689,5834778,611847780,623250998,363278779,316706342,456011036,802146866,239642551,779809871,947566216,243633104,823414817,476337075,184010266,354401895,724291290,215439868,283167364,322291721,548555495,518326875,523302092,211328914,899535612,73429101,228142667,702023379,68064804,18681956,180424314,649237321,535709399,950202136,284881122,657295852,496081589,71341341,187552679,263662830,878395784,386677355,950091752,18938709,240670526,764937268,474964853,565563914,646784245,305928504,22898235,632046454,740557827,598764068,32053393,733885460,105673208,673802032,538505481,135290915,279789068,261132766,299063509,610424991,800849725,667912494,603099643,86000108,864445053,269828780,41911324,810733871,261890809,390248689,814884557,339995562,102502161,702046356,278395191,956401237,828666830,378996395,802342572,686098470,79280183,576919627,206967135,184879749,935957187,478670683,657591941,573876820,626210364,868529577,674323032,118527211,526346788,133301926,329970687,293643564,530177004,191006198,739430903,804930040,389937453,421510690,141700633,753855318,84992079,822607020,805399558,47001928,155674715,474569269,499740540,611562716,998035629,243527772,810762228,395484213,206168289,531717493,182069742,573258936,962288073,647891059,702204245,579446652,756464212,765204592,985020200,138021221,64331023,155080225,342833436,717490096,342481697,710006812,286966169,391316764,641927336,163813173,740462510,283614605,899622638,80616080,175517384,370909756,19283401,687298872,157064143,960901741,385907919,24257676,209256830,754870233,353984926,636108396,871831819,119030022,831447308,418707377,553133511,612689791,894289734,348390639,300032176,849678837,846988741,538695155,661674325,545346747,632299295,617120754,217413506,799227111,461818634,95589232,971716517,717332626,283301377,908635732,215519117,979541482,609569702,334115506,768506247,880030358,297910784,936363929,430482926,54140494,158892941,991087897,6259065,187967995,178449755,94381621,783825907,967476181,542594390,775344700,351129885,214821357,403186186,37058828,479331293,794857307,689498189,996154431,515827111,667478516,129122497,405026419,545986228,787570970,835349499,631179322,946731704,969525034,914970365,34325677,367169218,609346370,776933649,886352257,264819293,522247532,707669156,188935494,374100193,144228432,508395411,457703127,993523725,674441346,670552581,49449063,957341187,312852149,149613423,943222257,217620728,980735523,871670064,348890847,395217883,392047058,649367684,452728181,61135796,364301153,614947888,791011898,637177559,822514219,734641141,106407822,82098966,213660206,186657803,662340002,962319210,234729712,93288159,789399703,740142578,857115611,105002711,934255640,932265522,219067891,317534229,130614285,494713237,162497346,422802484,793227159,291032164,383800090,732355595,859336562,496923860,193188049,308576104,304967011,740333780,758659608,363211260,345749320,452975523,962333047,20506237,58108651,214310174,686459451,93745902,67085097,100756444,47718874,500250082,486479404,182655360,954947696,221025605,278311425,884626024,972423996,346032213,849634242,301583949,363566630,669552680,863300806,109264234,643066127,533787471,118363506,36876722,632826195,305283648,71266483,531030730,622610957,338004522,463351805,886386745,520622939,289232396,578389263,188890371,107689716,120744822,667938985,693473107,287288499,526449301,558420898,734886266,956720795,379625426,204692655,257512433,395881057,589328566,380998177,841567207,634380967,417188702,825197119,637619258,806721716,596976612,183092975,814214118,365901116,683165786,752224001,887586469,242045474,450694993,414738490,648533733,83334648,847357562,248289434,885439552,393617876,797819763,748730069,800880477,467700392,760302574,100176902,601113034,243707311,542351412,466611651,781587414,233814369,489612075,294205596,732075333,841864935,254466725,810746281,728806094,627013238,371674670,465280416,550239544,806669488,766317851,18247584,111700697,0,0,0,0,0,0,0,0,0 }; void make_factorial() { ll max = 1e9; ofstream outputfile("out.txt"); outputfile << "{1"; ll now = 1; rep2(i, 2, max + 1) { now *= i; now %= mod; if (i % 200000 == 0) { outputfile << "," << now; } } outputfile << "}"; } ll fast_factorial(ll A) { ll now = 1; ll left = A; if (A >= 100000) { now = f[A / 100000]; left = A - (A / 100000); } for (ll i = A - left + 1;i <= A;i++) { now *= i; now %= mod; } return now; } //int main() { // make_factorial(); // return 0; //} int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll N, K; cin >> N >> K; K = min(K, N - K); if (N - K >= mod) { ll ans = 1; rep2(i, N - K + 1, N + 1) { ans *= i; ans %= mod; } ll div = fast_factorial(K); ans = modDiv(ans, div, mod); cout << ans << endl; } else if (N >= mod && N - K <= mod) { cout << 0 << endl; } else { ll ans = fast_factorial(N); ans = modDiv(ans, fast_factorial(K), mod); ans = modDiv(ans, fast_factorial(N - K), mod); cout << ans << endl; } return 0; } //int main() { // ios::sync_with_stdio(false); // cin.tie(nullptr); // return 0; //}