結果

問題 No.3004 ヤング図形
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-01-05 16:28:13
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 88 ms / 4,000 ms
コード長 52,265 bytes
コンパイル時間 632 ms
コンパイル使用メモリ 90,684 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-05 21:14:55
合計ジャッジ時間 2,493 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import std.algorithm, std.typecons;
alias F = FiniteField!998244353;
alias Pair = Tuple!(ulong, ulong);
F factorial(ulong N) {
    immutable b = 2 * 10^^4;
    immutable q = N/b;
    auto f = F(factorials[q]);
    foreach (i; b*q+1 .. N+1) {
        f *= i;
    }
    return f;
}
ulong solve(Pair[] lms) {
    auto N = lms.map!(lm => lm[0] * lm[1]).reduce!"a + b";
    
    auto result = factorial(N);
    foreach (lm; lms) {
        result /= ((factorial(lm[0]) ^^ lm[1]) * factorial(lm[1]));
    }
    return result.n;
}
void main() {
    import std.array, std.conv, std.stdio;
    auto K = readln[0 .. $-1].to!uint;
    Pair[] lms;
    foreach (i; 0 .. K) {
        auto tmp = readln.split.to!(uint[]);
        lms ~= Pair(tmp[0], tmp[1]);
    }
    
    lms.solve.writeln;
}
// the struct of finite fields with p elements
// p must be a prime number
struct FiniteField(long p)
    if (p > 1)
{
    ulong n;
    
    this(long n) {
        if (n < 0) this.n = n%p + p;
        else this.n = n%p;
    }
    
    FiniteField!p opUnary(string op: "+")() {
        return this;
    }
    
    FiniteField!p opUnary(string op: "-")() {
        return FiniteField!p(-n);
    }
    
    FiniteField!p opBinary(string op)(long rhs) {
        static if (op == "^^") {
            if (rhs < 0) { return this.inv() ^^ rhs; }
            
            auto result = FiniteField!p(1);
            auto i = 0, pow_2_i = this; // pow_2_i = n^{2^i}
            rhs %= (p-1);
            while (rhs > 0) {
                 if (rhs % 2 == 1) {
                     result = result * pow_2_i;
                 }
                 rhs >>= 1;
                 i++;
                 pow_2_i = pow_2_i * pow_2_i;
            }
            return result;
        }
        else {
            return this.opBinary!op(FiniteField!p(rhs));
        }
    }
    
    FiniteField!p opBinary(string op)(FiniteField!p rhs) {
        auto result = this;
        
        static if (op == "+") {
            result.n = (result.n + rhs.n) % p;
        }
        else if (op == "-") {
            result.n = (result.n - rhs.n + p) % p;
        }
        else if (op == "*") {
            result.n = (result.n * rhs.n) % p;
        }
        else if (op == "/") {
            assert (rhs.n != 0);
            result.n = (result.n * rhs.inv().n) % p;
        }
        else assert(0);
        
        return result;
    }
    
    FiniteField!p opOpAssign(string op)(long rhs) {
        return this = this.opBinary!op(rhs);
    }
    FiniteField!p opOpAssign(string op)(FiniteField!p rhs) {
        return this = this.opBinary!op(rhs);
    }
    
    FiniteField!p inv() {
        assert (this.n != 0);
        return this ^^ (p-2);
    }
    
    string toString() {
        import std.conv: to;
        return n.to!string;
    }
}
immutable factorials = [1,766786010,705983787,244148993,210582481,215582594,129246395,86672976,21874704,850657009,638474417,786368753,103549395
    ,264078536,625262204,185226044,902168850,218641259,640480499,683003246,876712294,408525348,547233394,300634900,371584155,832944090,893651744
    ,326512726,843656716,359802705,949283602,755038370,398849114,157125107,971617941,951610819,481304016,680950950,575366956,816984038,187142323
    ,722805387,318238233,968982693,578248523,271818664,500499768,849466163,268604730,211074478,373341033,262864254,903574757,570163026,136310560
    ,492373922,218256882,184219001,348551228,302307407,70007868,797190974,180557608,483244331,933027896,890154909,605185517,835769462,689354486
    ,96687561,501927483,593944616,23528366,357335185,398516968,797725335,184061655,303152497,98078622,996728981,796024455,915829452,97457057
    ,829937743,907175897,748640136,42590154,768160042,39326209,72020724,542991096,577428803,233510797,544780457,137823240,97062836,578565389
    ,122688768,148890003,278232786,45596018,
387102481,515773886,604845763,384403210,849317807,210722610,869634880,32144134,642008315,283287674,422410040,288798151,497583578,355648573,561110485
    ,580834681,112220015,33475427,317772333,596316874,335429501,900627351,733198052,844834750,400767242,98032360,292816061,983912094,549942096
    ,417528165,895122295,297548894,752797429,496689395,78939987,406390137,257680118,129807060,553661506,191166323,213045873,758339094,309004018
    ,128589948,212513874,62004037,649329767,926280101,354244239,834980587,948751335,299685362,267600853,173796099,167633838,455355228,914452079
    ,29283142,482874240,914550501,550966054,259320783,226806694,300654217,844638237,422327106,489451003,980318491,645638169,688948565,153383062
    ,536430068,923432110,49382817,248173708,833306540,986694950,197628535,285934271,104964765,674229619,147476083,791673374,710735456,815197913
    ,92412037,843863210,70227310,40367869,393032085,302180761,900779821,130815209,445232011,752109934,309849396,497647689,459852401,671454973
    ,623627864,
892602210,871438080,28185349,44275710,712246343,383078382,209588582,640672435,371907015,982424362,454748600,226512910,418711160,372627958,242570019
    ,983737359,940263818,182269085,615426027,446366139,710197880,532876159,707881939,809441202,45768177,897943079,339739889,808452545,987511783
    ,407729297,680043468,938707127,222949807,810935357,154762272,486805848,992754474,21949307,413553058,330880448,108607930,784896483,153641122
    ,846914883,232588079,984600471,263308959,265889797,209305986,428937595,184451191,49525425,437151206,325973945,398204190,595487166,918795881
    ,380683932,634697067,897706118,281839888,25120123,174552294,641839971,655937896,76069349,277055316,115365802,262466036,536236563,278768863
    ,90522759,63204044,931888706,938010479,209053425,761781696,591582400,348639450,860856448,435334482,343673774,901613695,920381845,566172771
    ,783990843,33617073,611136185,90817591,945501487,74284790,522692857,549727729,545075287,90265520,178236658,59569691,488131279,954672905,442819817
    ,
887478702,939144003,485961375,162118962,174913840,650727215,984640166,243009290,535790194,57092875,933222015,288003384,835225795,243155841,671154973
    ,265924126,994247829,532312977,576069340,14554181,393621207,554820476,540585991,420527242,79339328,906937168,950663746,93383124,96868329
    ,511596111,404369049,925142075,695178051,769870823,37319493,942160874,159647979,339174706,749230429,142128101,932249458,848166191,690816329
    ,256408885,939641949,25469448,275884954,901736665,897787042,499710224,636546695,220288536,522130486,173590818,463296900,585289222,530772554
    ,27834666,108265239,406984354,267599206,925571632,455835455,582383970,902263780,684207567,213169731,281195933,417452790,372247494,229684453
    ,557539657,396403031,559048195,280520923,618589023,507362338,536827111,161184916,788080221,970234708,911557655,75693974,293425406,841929891
    ,131340979,96506146,954715348,267285258,634098066,291172701,287824262,321615349,407060168,40000658,910618969,548235654,238062370,147732413
    ,833655840,
283787677,533215075,995321109,527440767,237670639,544700093,542342152,946800898,401371823,62174429,553295948,564154450,991069498,824132912,123644879
    ,618623956,58529238,71490068,333263606,217507999,724472787,817920986,559153778,215291535,488985182,935050600,757869745,792449869,235112752
    ,826634010,176734098,785552216,208080760,360532390,398762201,497218769,976622995,982778284,395349740,531854347,678229473,95826270,458437396
    ,205161868,223515902,310282069,602291763,593463923,636498474,83857087,941456377,898657754,938900018,519619493,265835960,239826028,739353209
    ,135132726,232832650,391931702,469195547,897215155,373585170,952125022,868405413,677030475,454752913,754968001,14566430,60435539,947940003
    ,402349796,951901408,740021117,541638394,74405887,776016487,881994814,26360681,346814021,11819857,716353332,56457542,371036503,390868579,33882493
    ,580753084,601390003,492401516,201876905,264348632,138310,107364155,139014676,556369147,671144270,73314446,428534311,262608571,295201906,
646603270,442028998,888863348,482698870,167342317,156284559,956966779,687638063,226973654,841028503,742226110,562003651,530387335,849256396,473741210
    ,628871962,249660218,474928271,465343968,595254166,819951346,666882823,33815572,630367831,590816585,238475183,932643931,295968411,892959254
    ,288961565,929507751,953980996,801541562,300613803,718862176,667361194,789824950,949610977,726957851,372617820,161815033,631010537,779373181
    ,902406969,738226588,488984571,817127135,886157785,843201845,788488293,540160650,922594605,387246581,189066224,154761619,820956171,983286131
    ,972222807,10444968,214785669,351752972,232499980,991370393,810149116,550114861,260225083,819565147,730385534,236733792,586941976,317828186
    ,215461415,46149138,254190204,920148457,361029415,956026213,467415314,19605667,798836079,562245645,324830658,189114329,815996246,69644461
    ,879334647,845997900,843341988,984039926,121559584,260414298,918422660,477793528,718065705,725886624,884828858,777582868,216466111,193602522
    ,671639287,
670737198,257389707,177391431,487030403,781875023,980639309,950330469,789624676,566735230,905745233,70585887,949046606,820858398,506122531,875679929
    ,827316681,920815981,890431581,790278065,598047083,461151725,19054350,359241742,141704105,376932643,721167189,461514284,599510684,177954383
    ,524126609,249763882,495119176,317197015,449744390,543141116,858535288,552386260,975563958,395902274,332670261,14749185,945835373,166484052
    ,388922150,974327716,688607498,37203851,411146339,262885506,849315549,713528023,704972138,904163602,627000768,8736716,608597979,833334656
    ,329761385,119588647,108180821,746331286,725824072,796155217,634031649,422497229,405203603,64877662,269136008,540798032,330441070,747491247
    ,457070326,378980361,657329141,816974015,119943815,97380732,916229823,592827307,822163165,955815918,812135120,299864530,333882425,430943865
    ,987691209,813268432,364180579,492610257,644097424,674417830,911772899,297212142,272286799,379247043,388794275,333406252,40430343,780514133
    ,597398273,
187097818,914515192,252542566,694440683,166341402,134979338,968083279,841804407,934163586,433824922,105828549,72137415,145749280,130053462,393637267
    ,194012585,110555958,732405689,477036739,821516475,418101064,581171297,147203960,513443160,124154585,894025670,412506838,710805836,7843764
    ,558211762,24390703,596606181,769152549,218724291,653258419,97728763,629495314,931953587,450107439,643537971,4859457,807829986,39024983,281199385
    ,256864002,842263311,457966599,485060957,833022718,813259672,353345124,395098973,670874088,15233432,807859051,924528101,397522032,20005467
    ,305099953,980160849,190522866,439720225,261078205,913999481,439675861,358058699,43532231,163942117,816890321,572408921,659283529,60448769
    ,566297495,286519494,217747323,471016879,543756381,33833202,919354802,491147937,187069745,456278107,888235793,708498804,933700742,183702408
    ,966798936,740807542,939320629,662387095,509789156,430581985,344260441,143717214,48859617,757169067,544109153,862655812,355473026,732727656,
577528176,432677872,403630116,410077367,761843085,95957088,622472526,507680500,573400564,426783046,676450399,852443360,908846057,881257945,512938664
    ,165949587,236968319,434343964,234678849,336239771,209064756,650425800,932943252,130640756,218643760,120430504,686179550,233084794,931094705
    ,915978376,536226247,420794365,393161258,209854875,799485112,770682403,917465029,304471609,427883506,384818512,618878367,986159350,796831075
    ,82158123,458381264,642835585,207688255,278625101,186493809,244038325,144563199,437816439,385729717,45462818,851452138,773540700,372879067
    ,477122243,984862444,482374615,254825647,73502308,582523264,83788152,237782183,562274981,770135992,62845975,464249939,763456553,814310529
    ,638612521,468960229,565140988,63319660,815848680,765298865,519998610,934990041,670866031,473678881,946480424,643145719,542924466,227744943
    ,315570925,622391759,985699573,900753112,970700529,157641681,408617827,950289592,669871795,611806079,530363943,486927964,955594394,881911928
    ,122642896,
952035981,184682527,302567594,607721495,895550751,324580663,283572332,588529870,622498037,307259936,353778597,649557923,877016685,79544999,437010626
    ,429343808,8313277,23624463,796354705,552245646,189822510,6217071,780819387,350545609,971171783,390693656,848602210,534176116,916679793,334904481
    ,322055224,17284447,669610604,275977346,883755903,311887337,160940817,995672558,79413637,700983666,833660014,958155785,698641716,835600164
    ,90009866,841351512,647947486,627444052,336191025,310517972,527120703,277745432,599811219,663027401,122724889,919049165,601071605,69928807
    ,813916687,122041708,861387942,886541189,138503262,116191060,606051890,629040458,128124370,800485576,842726057,158837842,711490696,404012203
    ,534790377,633097164,926200354,277988369,919408886,126634348,851179635,526576992,342474332,947986203,837341238,36264839,827343775,969640363
    ,934205604,892552159,455029799,154265204,457315028,891900183,677485897,550632331,551576768,381151605,893009865,85918646,9397558,160030060,
307989122,101584848,62333550,370220627,448172263,89635271,163607402,713361309,722071763,545120840,271278855,642850399,408896866,879447933,636154562
    ,177469369,179855271,522937313,986634145,594484528,454640252,553883982,731146466,770442976,925196798,960599024,119712991,394022979,440647876
    ,125533240,95976683,168998965,728377567,668664457,372731212,350496901,236111142,423352565,395754819,932427947,980650315,18466008,940240963
    ,784679235,879767419,143954086,407880474,573749794,884537822,483239722,108478334,131058006,401655427,949869116,591424897,642785834,843958692
    ,374520026,318085956,888547621,38485126,980272667,34612578,597330370,203383969,706748726,712902515,524817905,520173816,159892150,600961421
    ,140816402,686313457,371936783,414439169,826802631,965725413,618295147,579021788,204604906,449155039,294591503,601865329,63102261,37300490
    ,882028471,343633125,399828955,451379215,953194755,701817395,178823139,185405787,515635045,408482757,149146792,656846059,331490273,297018012
    ,683879839,
472072178,501408621,628328103,703460176,926712023,711977544,208671218,126108861,308301883,710198568,136257141,282353058,523194601,238658718,834825111
    ,30428643,311644596,913946404,670977108,40172755,276548165,593888314,94956876,344117321,532570327,960711181,47104208,817070832,326985973
    ,230420112,755440030,89331583,280609308,165417928,877948466,558962963,254483476,328210593,203410497,590157392,292313919,865817468,696041757
    ,561706739,892164160,226598309,826054861,113852838,424184889,712910418,361102728,649352739,202988250,743048798,987922072,11219632,660838332
    ,803536293,383400291,853172441,362103132,77111153,464382972,167661835,504527907,558370843,890426684,721884103,80042256,199660950,21445019
    ,84079403,256136616,900984165,388145942,935070427,514706473,284624010,743115622,89366316,25931846,462554802,543144748,824380627,867466114
    ,917690924,875830816,836343763,753849862,958564551,938598695,73368393,225909730,565268404,718486591,520658233,732952252,44445214,644430578
    ,384710263,
903447941,96439371,748455476,515209414,989891253,771063839,914482362,979947976,641090995,193777777,309419803,729656425,535902184,348827877,502970226
    ,434924748,890096480,70469798,950454573,252902665,259144174,38432037,465965317,187389683,581661214,695901800,135861144,354062878,722082409
    ,629222215,316980779,208037150,81274183,303989163,487893739,917131679,573046747,622494867,12436144,513947030,515138589,899440697,501141606
    ,732083845,128283081,599849895,586379684,462822402,649620136,433880730,62243734,611337099,971120359,740154031,701090324,899177033,947801891
    ,223910795,78194219,305993854,486816378,385102351,401403201,697308205,749399197,264811043,540709334,997688825,134209031,844300169,582681771
    ,29183394,669374511,490480019,173571241,40179693,100901842,347305901,858267083,150494228,184852443,306182924,786646265,568960062,692051744
    ,978843088,427039804,64862443,559541677,12034969,702446365,281871897,659105178,459366524,38195909,567917384,583870517,448249925,709561009
    ,844360005,
146322107,859339253,482669892,795247599,572628826,713376879,811634796,851291940,877575114,736620499,930668140,475980181,684292981,682580460,985191809
    ,617280700,854266588,449213778,566744604,880392466,177159640,835440559,775169090,376773706,403113505,12064115,165425502,148411163,174941250
    ,621197845,500462335,958531999,469495042,719913658,603012013,775394131,993429337,787513946,11092922,316234919,403643351,533078779,302224653
    ,846683474,420587112,131659649,359581793,187380745,187954277,513089677,955123258,815397030,974827129,472337709,28857036,671921712,30494545
    ,892477017,813678728,600187555,664944343,33545856,973848063,970676593,305755531,721164180,485399324,337514608,304949011,162637844,919042490
    ,261368927,788771570,301893912,783433753,256122003,624999283,391724837,726137322,695714167,427084831,7413059,872596545,887054805,587618300
    ,944719408,234605982,47942183,872222960,580355949,290466390,115997360,581505177,417127207,36875792,553826235,43322503,467161360,339960296
    ,101492974,
307492626,707099175,977550055,882961662,52412404,472756330,472251161,164639606,539017787,190978288,481566499,105535162,877413879,755676104,394628997
    ,915516382,30584151,579845648,721133087,622545330,144317599,963462859,808099004,693669709,80769679,943449358,621989391,436617565,781697123
    ,630593004,417659633,676221631,881354313,15956326,679555362,229586736,365950970,37205843,447259302,159596479,706489969,826054681,893443418
    ,453452300,794421490,116039205,226159081,252307986,321472200,959253371,841953601,796333117,577165151,557246334,209853980,189544229,14225834
    ,190607435,261112143,446760507,846963451,963394511,605095311,918878289,154511181,730774116,600622808,207224477,467096432,188808028,529078763
    ,184515412,783526514,358107957,118894170,559158329,874958720,943363555,85133632,19289865,427555179,330306157,310053930,933292721,920371982
    ,910312945,754207958,342915988,193459494,438270265,349102792,27642535,289621902,327315301,894464050,971724849,871643046,683474469,361654522
    ,957629942,
234071392,672361598,911939667,724375022,148169463,334251803,354381023,229820325,441816078,411489774,861003317,14296015,54858751,834619802,455633058
    ,633815809,258831478,907940091,897287738,833415116,565411742,931716385,595103102,521742282,447354505,566262439,856156862,95061906,329675437
    ,639147854,254997521,507389991,517614706,906928728,777941051,737508935,109251905,143255747,511717122,1858960,745321836,710644205,767460907
    ,546264894,307565456,907180523,262594531,91426959,186005035,678615452,439196615,795610381,492144170,819179541,80304539,892292504,222557795
    ,844863361,72765647,368475610,260425150,788329956,166817794,870879937,410262774,253156771,529889763,794189662,524032553,97606564,416211417
    ,824869091,917652650,266987590,736977921,710311386,573232873,793777721,890758402,682682315,233476026,69796838,180407408,410433984,720528381
    ,56036803,444348708,614228668,810783810,412424033,181084034,734087629,670140403,406468058,913144158,198357187,174612505,735290162,571113112
    ,34035221,
120437666,538121343,237273373,830277900,244892303,985645897,60344979,976606139,444984154,37308241,27354467,314080811,618362889,833090578,541003270
    ,211935252,313966867,805418630,868889543,510346646,132127750,665723391,63492932,550560056,649701456,155715152,133944358,690630667,755238489
    ,745591849,647169320,10811109,458525456,644097609,560315527,767292723,589732740,58587459,700242366,319020540,492428338,504340123,872981348
    ,43010822,399534933,499049559,422598902,516987391,621135023,56734233,307794890,270455933,394757535,203095847,189142610,392199672,273169135
    ,151696210,369521657,74617988,494959593,35015739,150673711,312528319,496621188,439848775,715580563,219189176,354905701,329751033,794709348
    ,53132848,578911895,292571856,159132239,690972561,788521998,307227537,466711321,819215905,122599766,520402283,30605655,202057554,127712220
    ,462235000,374650731,656998427,202440278,147266093,628005221,105265489,835589262,25410545,3607793,236064606,50512657,531438147,223329549
    ,524027922,
150247116,455418433,498908315,373308383,558309067,727295809,213730047,654339704,895302783,36811456,752036783,640060285,983376114,110734897,328324496
    ,659584748,352701417,165144065,834995297,183951017,574239208,167247531,643397500,640153089,468138917,797582804,235364754,613761310,581833813
    ,90677883,811937880,220790091,395930908,662684517,686325612,381197334,103271318,311809675,972726020,584237732,566827544,716134566,518016453
    ,227898980,549508124,690544982,170419606,710487535,4006697,31729117,831345647,25638186,541153650,787989652,579803190,551256784,559771934
    ,403844250,490999005,528753617,151719500,142435487,468669452,232084103,572307448,915789218,650834292,132271016,251618043,356071602,961152647
    ,343122595,596669754,494764413,592853902,131041087,370312518,410012874,850750646,259079578,634813462,94742057,235403451,182594066,404191826
    ,787346655,46685454,762130293,317916610,313473995,803008425,37681112,868767086,612424484,198685173,835307686,590569074,495705474,225015537
    ,102311167,
216471633,156738824,820302279,874084950,822094872,105777266,729615179,303378962,809430080,365600946,137971887,82946561,820172012,889369249,259013470
    ,472922686,743750992,35645333,606179315,493073744,588692064,738228570,132582179,664066840,636387003,54083893,585067145,133536888,352108727
    ,775455687,150604839,332341299,792988738,326157545,543560543,73916964,598365419,91993077,408438365,826897016,715439634,154895858,124707425
    ,809879604,293984001,717561226,115387638,799600744,580543881,330331487,777018685,977462838,634389539,346932105,89309784,223393408,285363803
    ,961200120,945805615,882716777,788078902,361140872,225391881,897916028,282304449,997231102,837660353,744244883,853451857,345961537,616377215
    ,886676908,300870123,307216697,994936544,284215365,15654753,870911824,992181068,393771832,556716976,460586178,950364168,272683975,606579310
    ,965257311,760875943,399991213,734314498,816774574,534060287,107505479,131823680,755240919,928460687,581665052,315942538,781901987,386133651
    ,8332991,
124850654,507676958,444007972,785890447,805952085,893867373,262289941,132248396,754016244,908086460,237259693,136910840,798125681,66057683,188742861
    ,929757323,548734144,112453620,405670605,824079438,85243157,408754746,787278224,954324718,64516363,300191968,203213353,331298030,396816806
    ,223282259,767200472,69255257,237537415,212392006,517709055,496326253,64696364,764763266,210182103,736669190,638937389,821569602,974747778
    ,292499084,797726781,817531936,979228113,44162808,91123930,832392662,176786135,828635314,548023409,452218741,522316285,551896362,665008395
    ,829519307,225901920,649905009,540099347,212117421,597511294,726691399,937060420,518152285,829316590,800746083,501092958,546421210,80199308
    ,444479638,367888280,791675322,549792287,444320272,732154485,423972234,690727385,220312447,219784390,354994838,252439618,286490817,559707160
    ,589516980,941768080,680758434,354853256,872186518,843135570,307739716,987313890,81372777,131052356,388349618,30074791,453858838,571158763
    ,545208507,
141376680,139998477,977143552,641802768,838198931,45142842,513619186,524017093,247011050,526440874,462182513,160122554,772190093,594024048,600068175
    ,885285489,675669186,742847638,69030818,564560841,239850738,207187077,321038329,29884779,583955648,578661430,608991034,928227394,792010120
    ,901016661,738292619,931910885,988401019,565255353,720914574,824574746,905510576,986490582,161864410,820215494,982727841,995659410,690009102
    ,805232674,933777955,529383249,978612425,374809294,947201243,594075875,806560399,343716600,961556798,140572983,278299266,839007533,349987487
    ,560872276,321240865,630254812,454740589,365026102,335909910,539569376,145201372,689645139,663230613,744814609,384836880,497843223,109873920
    ,829156195,663554280,431731938,282838202,875890262,751953015,423965223,678868981,451653192,656279065,897812832,583291780,327115816,728674118
    ,726688870,136427883,37042116,37024226,281875122,113274818,333583043,266729609,299702832,461368598,344232029,175800827,980032282,95104565
    ,318497156,
314826601,729029109,667241409,878611162,142593818,950564748,777010740,129475302,879065830,281077520,605419099,667061811,844289343,572470835,537068606
    ,416873482,36367084,538006810,328762373,391564011,394491344,57552318,837424529,915774723,246960789,700195315,191184665,786172469,294991741
    ,985402237,806344182,582248532,518467198,310959074,344804347,460729703,824781277,454993323,445269743,281589650,208883566,844292707,489548655
    ,39012216,3551978,458545417,160539977,570127200,851910554,859275605,608663283,753675679,689707367,745065626,711891339,421824449,962094903
    ,651031713,442429257,350331071,516641209,14381697,892612641,360356892,761851684,31901933,678371377,492703959,706332063,110566178,722578094
    ,824719791,908918003,629352205,961059853,814080198,671519911,873489261,670257837,929486824,593569365,92710697,155745663,334778133,442060807
    ,501910222,806153800,967141443,695093294,82719024,202509891,7175164,279019333,670204158,535687224,111964750,859901328,956253724,150782241
    ,300738984,
42762998,805350752,171761508,428479071,401448187,237382246,316265967,40397790,465804761,340522732,89261221,471992296,594246463,458027580,274888611
    ,433788332,842927554,966994666,255895270,805325367,80114537,494441528,537911129,584827901,973949196,789728300,578558797,13418629,469918670
    ,223689578,742110071,172259956,711844521,32093228,299763301,303588186,19098765,17399183,996065232,40359077,71488718,455118501,961754730,479440480
    ,253362678,946846708,708341609,359630504,722394991,767818091,176556306,408544207,374112867,542544741,367463943,534319456,804224762,965981258
    ,717256908,906934019,166275300,26640611,375503396,49627824,552150000,297231542,699359244,489361984,568232963,216541952,722051667,646297605
    ,463289521,129967340,94103993,938418715,242459834,666921633,369673102,658294019,676271254,558878265,772361194,320472881,613917136,889460032
    ,549166166,805593987,359873274,303213536,896502964,856093514,956763902,117689712,469034644,859519724,626171814,335631850,105993008,864118508,
365605272,505298715,471050005,94585240,590955305,238667137,9580513,313803623,517429587,997822898,711952747,311403013,467107038,28174436,871755427
    ,920010820,555917661,927236510,920360811,348600216,389895747,848967167,645692007,880873424,344751572,412138213,115552740,285473813,948593828
    ,835484573,433273846,591135275,802720121,186969504,159830953,604540996,847880961,572805238,87946281,573706739,64037013,619705873,322831845
    ,908917247,615550957,695944538,135519551,121206904,424522836,878131539,312838690,57033460,20991802,626079095,203848382,366055250,625119902
    ,896383075,244467632,195969604,614229402,866725528,738477175,331189477,366641705,403270866,52478851,314963384,445586444,73732226,162649405
    ,367680248,532407673,869483306,139166895,596384391,126616929,340926359,784626480,756919022,359053028,695389090,77534535,287903465,964431231
    ,969469629,401604144,23945787,48505981,619535652,962144152,805904455,228264858,191975689,739410636,408396606,361642345,935739709,377925506
    ,316588744,
594944969,157104524,947690748,312207310,906160178,124556729,392834385,963307004,81553347,178145620,287559335,142358000,875451376,726182510,704881626
    ,53320325,490367285,506488396,834322400,401222720,234139049,550036036,602317320,481866619,952658900,419159518,618275957,50676080,551264767
    ,940074300,196425631,884827730,90390396,710600868,618981916,638970397,252679901,600561088,84437370,885534177,758958101,969727913,838853234
    ,714354715,496695688,426478205,357803205,686956100,30580948,812496962,867063945,654181605,873247982,733428548,636083719,241573287,225901431
    ,980636969,242745534,722316264,251511688,490908024,556531634,31121237,181609694,451988374,770928117,96231873,929556198,348438629,457127190
    ,223038709,48990235,749974605,3809256,810602098,731748983,124020724,916734965,575985717,694363833,579780433,583443120,659191708,115617183
    ,308118683,657709052,342520119,892817001,599834990,830538887,406821140,725321301,40862720,735848231,225603008,73220895,985844567,205104591
    ,213689172,
755044721,142163189,964769580,385512587,943167861,79628431,493057819,878450643,186890803,103783113,498641343,379387065,531890818,155284383,803576766
    ,272760247,666072249,966819751,677689315,815021282,30977021,812762325,736809331,44606670,621625417,162182234,924310635,277581406,614787939
    ,860400524,598260418,584859211,817090309,775988476,216466894,233433580,162270908,262785007,208827687,861687482,427439174,356080117,714046188
    ,792666345,665549925,35332274,868085142,343528688,921837248,584871249,176306348,744216593,724560764,672167712,686619578,891726147,833660822
    ,841063973,435045670,676542561,701798898,617104375,379320642,343268122,354397564,522594696,715890645,462261143,689507270,346129673,121630156
    ,253538456,969315541,561854672,47871012,17322705,383962176,377394187,147861478,766275603,14216953,713551899,579527460,678272062,714784049
    ,403955521,489134192,348444304,873487758,579782990,791424168,295010460,626646620,595481297,356302207,90216606,358894582,71762540,593230112
    ,980836133,
789990042,476498122,144070556,874181050,465930686,109228462,149217689,739150120,72840667,461343290,800273573,286411135,931323317,412490605,660797316
    ,362273955,234420530,407066657,340851485,169564539,224005854,611101271,595655446,418866250,934524094,535606618,31209615,598396994,525517753
    ,517235481,107747952,75451305,740161220,833825767,193453277,399004762,902071104,911351719,314374590,911472795,46020014,868049125,333314940
    ,340507580,201728848,138901063,135225755,617242159,56329093,54096741,223411382,632878865,93469785,694806127,177127283,734587411,123985104
    ,301363721,618769094,861375995,810674067,283421005,468255569,357104983,278966502,225560274,138026795,546319631,897521530,679025032,503121845
    ,421570031,922623846,271530953,247171495,702658288,726703894,320072678,709235133,733542862,309840711,525064046,561731366,533713598,222828057
    ,101707202,351841101,112821148,373071874,505796205,607565929,195083434,386324705,531307987,835085648,446863793,171791789,584449969,988215361
    ,417876813,
492726426,187781393,160337274,313068808,741721827,227626245,833998834,221384747,459787,695843405,377302183,621412396,276740056,525763903,529848897
    ,310216837,317649191,138675848,77501257,641311602,496692065,623349148,239415787,92360780,913810874,102306155,688411166,48864530,638649274
    ,951286622,164437922,94332306,975594206,577297664,619329017,192562468,972048376,529916492,653068858,604948489,966379803,491670197,335675624
    ,984570167,342429855,533116570,733960336,869360042,901921662,363266670,520497116,715577960,950242225,73268638,918792965,553097265,937063862
    ,945606593,681140489,366263604,627663214,52080297,754510750,453222356,851555446,842988482,922608515,575639935,157608850,168044071,729750850
    ,614524217,482671405,305142368,331007466,895632912,565429478,981828716,257447031,483981875,720661979,429224810,848205056,323188695,210820069
    ,883466972,460158780,747540971,237351689,961681722,973155907,194839617,304678191,521179563,251896624,362951559,355296618,655623734,698006687
    ,335481797,
447814102,963575704,323212512,227660778,877172698,866864690,324052428,17397958,481349807,610724444,515059389,149661908,106109785,90006127,300902496
    ,211493354,10402789,537548679,697026012,310772360,683734789,751831824,935963987,627267760,733430406,349218860,550137358,637200751,528789573
    ,380699882,113408198,168641127,5196608,379576553,599834256,967942845,997387339,389389261,76709098,338568924,241695622,548892166,15961531
    ,102709957,326948342,55849434,382338391,763658096,675432687,730839588,147707353,179522423,892985251,967107409,411160722,594752475,947298128
    ,144303205,808400997,429184708,638742748,587017826,110883347,458290048,422855699,8504018,538344152,220664430,754409726,245641763,584212670
    ,937130722,379218630,120561060,972352458,406193274,113724749,10409852,985878468,544232708,129566,990930052,38071089,174544731,856505385,798165020
    ,969858414,830725934,680952690,20274450,656213038,107849218,725209458,85334842,645222068,170663849,561784709,729785367,465990075,393495668,
695501833,664307080,759975272,429871971,752621075,238026400,250205525,17697613,428422282,841337447,250505227,348028161,753720717,174345953,752764687
    ,944331814,755322746,606802006,811274453,563955060,204400485,323034423,81717845,614987712,571071750,924380904,298785758,552810714,457130786
    ,577941262,930197877,273390577,580504411,441107884,115479596,18587146,13343734,786905261,545430842,286164023,355792416,535742488,542803132
    ,135707980,955707879,887428561,892703349,952665108,816570189,435793297,295659250,680027755,264866249,740567219,178901259,379110481,721457787
    ,20795259,341592495,602069285,88895221,31079530,867529147,967882600,839165893,373127806,173521653,911558620,538855210,552383730,793772707
    ,670307735,239190492,498036476,397078549,445270493,746957402,980270611,107919333,550046860,674668755,629833758,49656879,927358274,483197590
    ,787026399,66359849,139977,150801723,387930530,885605554,921188899,3271144,168116357,949650894,181732715,463278248,778842727,884534149,760025067,
878256819,282508221,476548983,207888415,688209691,798273219,423029295,166334525,614795030,885951502,790126124,391586489,778304179,627954274,391593537
    ,389461221,927691430,794451110,933600148,401178749,606920186,353409056,886361742,214603334,683769540,12600258,74952538,873126389,558896543
    ,851255079,668662515,398446501,696438125,186572970,593149713,710217774,243053371,276565362,24898948,19132477,217284368,42405253,380068701
    ,876598408,233136968,468342663,210966269,379351299,717112779,811438469,692968550,280414800,281176004,951358231,328429094,757122622,572774273
    ,265427477,816490152,584572864,115715215,784209243,486469954,328007660,574041503,774006740,311875378,295778081,163160752,72440788,189338081
    ,9350785,580935967,914154051,311992864,461659701,672021812,881678588,841782715,918098612,982269475,67680534,709674921,453973409,157023191
    ,417465967,469562922,70186451,660349206,204404247,937088268,260277193,503990250,989959824,378332342,123410728,274911422,76013270,570865122
    ,720976283,
565497208,316961592,64176281,907420097,458724455,316898415,707305461,422401080,716306998,255229675,933914702,624084033,201026809,523732467,340586847
    ,797836090,755851110,360526664,718577288,333853788,716857994,439316914,737916876,786495949,959687845,775953302,906696783,324640502,176442426
    ,977151551,815041686,698937907,601925589,819574831,96701658,436032631,479912635,296714748,688918534,119288377,263311240,45790814,998189601
    ,682827973,264920634,472740710,914268031,838445332,918254536,650770098,50764123,574881446,48567346,440221695,507279942,464885869,508908174
    ,76555865,101360926,947701400,338095442,847655179,873638922,214565463,387466105,742684928,155972573,469900567,822464325,464060630,332424359
    ,897343925,616898523,342209208,254292706,124426850,963328675,560884299,129866604,315552202,125542272,588315792,4533212,880844665,92104292
    ,361474826,374758578,583153343,350402044,744889435,546575355,934494915,426395742,725542730,482021979,90100458,161524371,214852530,798166167
    ,586537547,
937833266,643194873,245916533,725609179,340500626,455237713,148585642,184346814,337883825,456191643,817619778,38695739,6953241,564437957,165186797
    ,276213128,728434869,218056970,256177319,333104526,404297355,429904069,911501677,541061900,592547811,675723405,396746596,152369624,16978035
    ,4390399,719409709,722308058,916391456,401929040,599635511,16192946,227389833,270981574,181616444,292624291,519615878,918434420,132689002
    ,825524733,245299743,461983112,957089128,712675746,836359858,117371703,927868662,890610514,537517986,594185504,660756513,73965208,347221158
    ,384504912,870354004,988378684,303188833,748439007,658114120,853001682,812922650,830927778,834729608,464881143,750160356,984089998,653675813
    ,863916472,353140491,943555123,111424627,858034620,490281316,370103484,367088338,234426668,815351696,787120951,525063361,916299096,9413600
    ,255176549,385221943,880162735,55506241,331300777,957891194,674121671,220312497,815104273,85583581,165926549,263963822,98859581,394332918
    ,566486504,
135568328,459521035,373573472,966321447,1114189,479476769,420202766,152632011,558704674,911513273,55619550,908006168,861366373,605275776,108940567
    ,923167181,545306348,579166643,77822229,800612279,403486800,750770597,561279498,142146953,269593491,613380379,273966767,193594591,142817107
    ,582125752,199532411,961804361,258106322,998110155,767334964,484374525,592250370,24572824,673582913,283010644,568573577,190566219,137332945
    ,318142829,124397236,833050553,599444984,575632388,655700152,749562308,291861106,874008749,816936030,892364548,395222536,795795320,328049114
    ,640818392,628195766,858022481,976738351,422569438,968537208,276445093,796395177,343973070,838213000,429046939,760577352,684870615,150863897
    ,140474325,560996492,722038071,183549717,818334266,622859836,612059290,149195859,909030347,353684500,657078406,703568931,751117420,114435050
    ,673758485,553592406,348225350,320563174,68685886,381059554,354890322,929772698,818422717,242596814,271274397,85354228,253800129,344600879
    ,708205284,
72297738,639565151,58871345,955295577,121396961,193538289,383720808,33432381,940918548,701025199,812069099,811542837,210319882,752828343,774779307
    ,383244497,834644234,595462988,236315580,995703398,402685766,273070615,96732718,857625674,173702524,701549465,504037161,482804755,108117781
    ,863814074,932060605,235975975,781158550,681095327,270783826,390249909,828963405,459201971,498001269,828484950,854571078,420869522,292848850
    ,652477883,576259070,726234358,692935197,798595917,524485402,932912293,626897055,869079482,214745553,454386909,678835379,686107119,78125519
    ,449000969,764138349,464037975,269616040,354329033,356826889,867313676,225867,403412226,537007842,689459827,831757033,462924258,622569744
    ,595779283,804557083,595933958,3112027,784906172,26513397,487274035,692247770,411054570,737798111,550098453,282540637,615204296,104586888
    ,796034880,790671548,843412941,208619481,449870191,469925525,456522465,49810017,359415396,697285138,68215933,590407310,126837322,13271723
    ,939830261,
982002309,981175865,908589309,675226561,683734700,310076852,53603549,65962098,726645980,425865548,632220988,495072281,306200399,19560689,3157171
    ,537304899,249526750,56772030,796444924,390266531,133113318,926423532,565499211,158544067,205136297,630102742,925571523,133632681,570768135
    ,838670730,490379063,416928904,995969715,295635014,897009169,730986921,984871902,965662407,710140734,531580415,838740496,330914613,237664251
    ,514762978,415620745,349214023,399563787,506305130,328802501,983699513,708173309,947241700,373838627,428315648,951003395,537621050,15309989
    ,966782575,788985115,566538086,929081485,20824446,444204306,267604234,141550538,714999550,484723139,142228692,775417280,708853823,48028794
    ,761295354,176807478,968471877,128206525,131987684,792995149,179870724,992926691,566766129,998124604,396878718,391185900,830229223,573813781
    ,825912567,5890072,710390707,907146235,831192378,740861386,94989643,104192320,507706990,788464052,939563008,53651837,384059432,369891125
    ,206579820,
928207340,410190951,318570926,483514152,768353686,439407019,25257929,967665089,478818014,37308012,844110056,484882950,791817814,447943412,639049117
    ,438637722,313514553,693906613,539092187,179888829,456189951,768495415,278120439,923458311,819019072,821138064,207680291,106694231,83161558
    ,174920451,741505463,364751053,249255748,390628207,672379215,593207490,822712225,744901132,124674725,29923813,321150073,929931032,497552873
    ,236357905,207169515,495184108,846035629,614013638,980819743,301188781,163560818,484596815,736818464,361552545,1421725,293035282,389444506
    ,599483965,22946914,741829521,593584156,654000617,519461139,229405977,758896288,458879461,745376958,818496048,168814149,657979351,59001514
    ,982399982,483918349,645041025,32831957,172070041,792549922,795927322,881998488,821511104,81647239,276660149,310010563,375456581,586030044
    ,843199636,302345875,862705388,972504868,590730766,85551914,607832734,657849055,535906368,383792414,18326444,501216682,768552065,723279859
    ,593164676,
450634405,76547658,524604341,533416623,539916611,17597508,934334467,620219850,270202988,231588061,351802549,722647709,454176750,335880490,53167033
    ,130441823,595797827,187797509,188439159,800834612,424835272,869368515,500448396,393103273,553027839,554550181,52544644,814972209,529072901
    ,245884933,297015383,908346458,370358101,990290060,700414743,164060837,369746054,687120765,27398378,936704636,417311156,970942713,443992990
    ,318363607,644511025,965005979,407975042,205802897,29968380,770845925,472082731,560317652,307192803,905161514,833643400,166440380,365645069
    ,250611490,134572619,303004806,261449034,234943096,376684936,239434279,712670243,847860261,679741401,797215910,284256897,388137181,124768877
    ,765068381,761681965,55170385,500160984,267024118,885742300,837751321,568151042,135272165,51571203,134941190,761464058,593531621,150853255
    ,361510471,151017889,748514604,50930324,173112946,956932293,335591553,808950108,908017654,394050834,868514247,436301922,646260945,173249076
    ,247687458,
976398180,333430920,612825621,163337916,790889456,441303225,575406465,26691577,543997311,676146427,431834632,750217579,707849279,442434238,443754000
    ,790173696,709097919,195293587,384087850,589312043,403473194,620372919,894311584,784353552,281996439,274627022,122114453,58402725,556332281
    ,205628042,377854655,834594642,981536920,996825666,902876729,76883486,53957542,978554583,943615869,272876741,939842213,790714385,238406326
    ,765509754,845739988,269280281,267560924,187797500,533479928,41047791,526320164,479909265,414665773,363797180,431084962,770823667,800268321
    ,182369922,482601959,963120036,202230963,802652370,979125891,577313734,975062099,640539513,665930527,954404383,641437939,232528387,592737378
    ,760352567,449613576,181990966,824079688,582458422,329585709,469947223,767748918,705428274,975090856,890807687,202497963,691958712,286669969
    ,4953293,534857124,239450264,845007664,775817031,706080205,141674628,600303499,181023477,718759381,266522893,240838167,669726915,266005348
    ,266419267,
459213031,641644259,729626758,259189283,931488488,118098770,590931490,362959889,368225270,669489805,142918197,496700903,207982109,481166862,291113331
    ,532078134,326418990,463906532,861367490,276979681,200261531,351361324,592133675,568889075,592015961,465656941,483986439,585803672,77604925
    ,471733299,625099512,24966222,166475717,277218581,771629079,62351112,811336737,546004836,318636793,107060302,797286013,545668934,945774830
    ,847949430,934801196,615638837,188464563,148080521,459072053,937835947,298122266,725975864,902465478,702430361,806938034,511651770,925916000
    ,313679156,66869361,631026019,433615319,603668794,308097278,866882067,718011627,226742645,291545419,279073695,742154052,605154426,961033745
    ,588882279,806718317,706841781,566508289,414397677,152996481,592640168,924604644,877328108,210125812,162780401,151113992,480818099,548831440
    ,338438956,296298335,199363036,801976115,7362571,740723478,878004335,164696933,881692960,680822024,736562183,815277541,418919965,786123852
    ,506268060,
424398817,93748375,861667353,129258790,348370646,303401411,762432895,899740001,808330763,522147012,804958667,406498487,967152993,499780163,139589356
    ,343511758,675337756,734240883,841537548,347010609,288447096,725205087,830733192,503746650,417547027,313958096,558411045,296940091,349018292
    ,897850418,70915014,360601604,685425236,245544261,575568130,731414475,688035454,439420592,750769603,570335076,886222210,125227623,373262035
    ,242077566,503174324,274137609,417373857,299975776,377146207,6177705,107923168,878563288,410922311,301876943,375961195,461948053,911007180
    ,211999866,562982443,771152172,335793370,161840762,333337820,466593908,10434394,21424772,778862074,858294060,785254938,713858514,807180198
    ,365747733,662845859,502372361,752298111,557330675,94318562,88171858,641799614,178011904,145943196,71122724,289196650,962831712,997543040
    ,905581827,86506263,164886933,447062895,689869762,133792079,199762393,306338141,906131637,159615066,650783654,694273917,925412244,471672734
    ,936268003,
595535145,193795026,31214333,539994540,300691433,805766984,434441258,204768802,198636647,193864340,340989376,968160680,7837968,440634146,757605904
    ,418182471,12800342,744306550,514426032,666780762,968900381,564909229,690325460,179186097,911071683,488964196,560739627,351347817,573282831
    ,699888911,939994030,536193764,255677235,876440551,385070476,625220709,566088612,380135953,391617554,676150645,26503774,914378771,818033782
    ,903309071,135790667,530425257,990808763,624009106,400448506,166873118,767808660,500232681,712960784,273841550,253047365,89416292,532654069
    ,184079203,290655636,922700952,668279156,780950830,223910322,90506336,282915796,257943157,825340979,903604115,361558035,666879233,10644418
    ,419053844,639171711,538471077,86881583,122984643,433670513,175810445,564600865,380386949,63991992,201287391,813394960,299305754,360398324
    ,630919775,693880097,387891781,683144949,760826274,756369727,40625805,284594407,142731608,565307130,359646428,36315760,609313394,355955449
    ,443834893,
453659040,91788917,682069262,44423673,171577870,831280026,495903257,967329081,309671468,725706872,119278464,665840607,781404806,903208389,736763310
    ,159635664,808580224,498627646,379379165,443657887,955114081,700384329,953102257,614012967,732910917,902341463,665247016,744274839,930613617
    ,735740462,413201606,337834120,51154457,479830629,684069574,724177609,444840056,240941684,240615817,905906528,817352929,531562868,239163284
    ,692453948,456929390,971425124,332242785,613312188,386324190,328979964,394347289,600570310,937254814,665865046,187888455,833814625,381507467
    ,212353387,473233228,72564175,475288855,226634919,508212378,917102296,243585604,930023114,180816902,212171947,84360303,197593783,785833577
    ,356933887,309112338,288284426,907574085,589126594,584237732,270488718,847579137,486514627,529029675,198543581,974184931,665437663,400071227
    ,523601625,79378159,679969070,966225931,226471935,931883419,279406117,686003074,120680418,280554490,138135913,215908326,170886488,618295204
    ,470135404,
586202276,536982797,25282104,286711108,881266060,877232784,978074123,724281833,17678265,497601756,219195669,568765634,666390476,78220657,530956884
    ,100624949,195977750,327488352,914789958,382643551,955986852,209980463,72788539,324379917,781258799,22022215,935421823,968583827,470232491
    ,366208505,710902895,376756668,720574865,747454715,562778366,335399824,563267682,442170186,369759560,800048116,810746442,909684231,601305301
    ,733342071,255190604,862946333,634641169,887101973,578641822,954410105,924086748,90737563,692451218,382860057,506415842,386379908,232839787
    ,645389547,324108127,171703479,273287246,713314520,694832007,801001034,721608845,799627337,364325101,949952952,424667939,749544729,895571665
    ,163945242,772330023,69942695,629364895,199926343,19460562,984603151,948246415,934051883,511638603,807950894,510332573,697255610,431219724
    ,337943573,16318341,300681298,542957543,186302178,139486456,856072518,683578798,358636011,789737871,896244722,469047681,124013030,277430096
    ,117565665,
460528287,694603160,262766158,481900114,952917534,487255312,904905793,829268166,921330831,28515366,440372280,901530950,967507064,421561695,149584797
    ,608712518,900112403,332777934,544722256,556127188,264430771,79124583,320071427,123826462,777954612,840340344,578388289,727229171,702646529
    ,165302301,108956821,317331649,546562946,978350484,850020363,494769707,287169920,876501634,554096687,517407446,767285424,959676227,908442833
    ,637668224,94969001,61416679,448046149,206440222,635726202,832761782,248101424,852488357,746419504,704728827,387510685,268732886,482924442
    ,493945041,569832609,129452649,944829127,504578232,886705883,707959417,657796783,462067944,997849064,806049212,912457212,393456657,787279888
    ,69871170,477868849,559177147,910359169,802528151,100231495,951782397,750356758,173655801,364015132,149818511,80001334,871481179,29969970
    ,202204692,706283953,172497061,234094314,925142654,15383595,742538589,502489673,178436998,240590297,664507308,134158351,321532315,68570935
    ,39806322,
957956276,569478770,80085810,361537016,880490691,546990890,914226232,30909707,720653175,297193538,251624725,721528572,405412795,252173582,396688048
    ,22736249,643568447,647476815,739528081,419427422,748776331,900136908,689324471,772066091,886530187,870363804,56118892,322246905,286344752
    ,320214110,128075046,991620070,825213820,334344449,75331535,552112930,861232094,58003583,355847124,74672160,277103607,749067083,392276414
    ,259659490,573656602,723465303,492588537,641298870,555894218,478922755,144989416,141064386,868762812,70440207,743176939,92266417,681701213
    ,1224407,450530678,198854937,50127862,529534422,408629372,588679918,709824457,303670088,91591360,225417497,322671193,951720077,186779173
    ,931460106,116249505,875328953,778232855,10326409,153860894,892170898,193948177,298024541,552129176,544692193,738446833,575706915,795088878
    ,382498857,91524335,949677105,148283515,871933197,287010501,722787094,698614171,904754731,425995100,199192153,414223721,551372304,767561356
    ,394880724,
65716158,100019680,663640838,777236055,312385373,825997680,803024049,643559630,839690900,822553534,730479115,487712862,790437528,58494765,130557374
    ,86578352,76626781,401975191,694615646,390632053,131986859,587946922,821353153,199980785,970951247,635632643,223192996,606837346,783847209
    ,278310054,712310137,169970201,451196535,892688288,434955776,217251583,114605218,495503243,747212906,693543402,448583505,867841567,395764541
    ,590268231,225042652,84332972,992264780,694348292,676150109,821825588,861079322,633262822,844881622,735067013,106661706,883563110,343241103
    ,524932557,633024371,252104595,185255060,84695977,516085814,876101800,97022827,214215510,995147119,214177025,501837862,774273828,231757042
    ,390645304,171546468,747306424,811613185,375393148,735524598,35331284,648448047,870541371,88539249,289917521,528188440,978393319,777045621
    ,117522727,621684196,718196189,353723277,413412181,835079559,477148557,344894823,805731199,990339685,279458673,357737430,35569899,930185379
    ,468705875,
806203962,856377309,68431597,91464768,592289708,236859210,526030031,800036535,460140597,153029405,686683732,247128688,936930560,155329809,940758320
    ,502398771,168581904,802146317,606629174,173049798,332268202,632703885,216110196,130479615,310117544,254229562,148772877,751193683,870830441
    ,447426627,915138369,214944347,50152581,674087556,195353513,165713479,495611926,512010426,377564447,112732874,691953286,417967963,977406619
    ,317135744,105359232,722628811,353553308,258478857,614085334,512554988,139047001,538016062,612648478,167430399,817332555,612965199,987020961
    ,588981677,510620416,689071146,823933538,147486025,80166306,590912785,351169682,428841155,531319084,892201641,973169397,385605303,841129034
    ,248476932,882647877,384866980,820096045,965002596,306104514,815688698,79483193,209873720,272298271,915340747,787896421,845176984,260535674
    ,166850946,523086492,480021924,299260463,282897103,124856573,215874429,136169986,330245180,331384161,128204476,793640344,205241452,743753950
    ,232240472,
287308791,517317777,799660342,360881120,517327078,524887975,137621092,122213487,124318857,693187928,5836845,25129822,150621786,79008934,862914941
    ,192567501,639701371,495769005,357497096,346011894,683708594,80281195,425936338,934752268,194317833,902542107,474586912,722463121,529433598
    ,928693088,985214088,395876871,65817012,650451000,760471241,275790579,840665766,840673688,18096548,882275125,53584756,330590696,451329593
    ,732071300,553763614,306681250,941285512,560346882,416062765,876497899,424972092,864741815,96376709,193425618,445541104,199518487,877869164
    ,190038443,914648400,958225129,303649659,929840251,9005664,6938495,761553634,905260248,433616394,629882537,257965105,305917724,982185689,28432457
    ,281337279,514955803,782503434,121192998,464310834,65318465,747546224,451486982,621196325,830583879,103401026,17535517,549781481,140835182
    ,472063177,11668639,393609946,630091198,276420895,243245497,719192669,180174702,579080515,822665080,792984240,311154715,908964773,356048018,
504699845,237978929,292702554,687237323,202300173,975036833,55687501,92656428,298092466,325679625,860099745,877854829,50755898,821389941,674120223
    ,225485784,940039279,70583068,289950142,67310823,775906453,895821177,881531503,660823196,249529935,765213171,805804655,546196175,527345521
    ,518026008,20200730,327531075,466414706,628548785,415380550,161868771,345447982,922264748,651759216,459335532,529246641,532063021,669642046
    ,347630965,300648871,588871577,114652813,893444323,778383169,895187265,403593426,364287218,854269069,814580039,918949349,304643511,996018687
    ,896091363,698369010,705767517,281421759,854570458,468164217,399069334,603271420,35652140,412337,344052576,688073612,603655893,104328078
    ,169219823,573403745,325994113,376434083,305776215,940738877,319067025,507974058,128774695,114384492,526586732,552598049,595559841,175950202
    ,920687743,855889888,113826577,798920277,648690264,717994198,588760083,565037740,396252552,914702985,132506924,114739636,186508247,247586308
    ,808258749,411377786,];
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0