#649676 (C++17) No.1561 connect x connect

• 問題: No.1561 connect x connect
• ユーザー: shinchan
• 提出日時: 2021-04-19 16:15:50
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 631 ms / 2,000 ms
• コード長: 39,008 bytes
• コンパイル時間: 4,816 ms
• コンパイル使用メモリ: 273,612 KB
• 実行使用メモリ: 8,960 KB
• 最終ジャッジ日時: 2024-06-25 08:00:17
• 合計ジャッジ時間: 9,210 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	2 ms; 6,940 KB
testcase_02	AC	2 ms; 6,940 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	2 ms; 6,940 KB
testcase_05	AC	2 ms; 6,940 KB
testcase_06	AC	2 ms; 6,940 KB
testcase_07	AC	2 ms; 6,940 KB
testcase_08	AC	2 ms; 6,940 KB
testcase_09	AC	2 ms; 6,944 KB
testcase_10	AC	2 ms; 6,944 KB
testcase_11	AC	2 ms; 6,940 KB
testcase_12	AC	2 ms; 6,944 KB
testcase_13	AC	2 ms; 6,940 KB
testcase_14	AC	3 ms; 6,940 KB
testcase_15	AC	3 ms; 6,944 KB
testcase_16	AC	14 ms; 6,940 KB
testcase_17	AC	3 ms; 6,940 KB
testcase_18	AC	2 ms; 6,940 KB
testcase_19	AC	75 ms; 6,940 KB
testcase_20	AC	4 ms; 6,944 KB
testcase_21	AC	2 ms; 6,940 KB
testcase_22	AC	4 ms; 6,940 KB
testcase_23	AC	2 ms; 6,940 KB
testcase_24	AC	73 ms; 6,940 KB
testcase_25	AC	2 ms; 6,944 KB
testcase_26	AC	476 ms; 8,704 KB
testcase_27	AC	509 ms; 8,960 KB
testcase_28	AC	481 ms; 8,704 KB
testcase_29	AC	415 ms; 8,704 KB
testcase_30	AC	439 ms; 8,832 KB
testcase_31	AC	2 ms; 6,944 KB
testcase_32	AC	2 ms; 6,940 KB
testcase_33	AC	3 ms; 6,940 KB
testcase_34	AC	84 ms; 6,940 KB
testcase_35	AC	6 ms; 8,704 KB
testcase_36	AC	6 ms; 8,704 KB
testcase_37	AC	631 ms; 8,704 KB

ソースコード

// https://yukicoder.me/submissions/647398 に制約checkを付けただけです。
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint1000000007;

vector<mint> cx(ll x, vector<vector<mint>> &rec, int m){
    if (0 <= x && x <= m) return rec[x];
    vector<mint> half = cx(x/2LL,rec,m);
    vector<mint> c2x(2*m-1);
    rep(k,2*m-1){
        repp(i,min(k+1,m),max(0,k-m+1)){
            int j = k - i;
            c2x[k] += half[i] * half[j];
        }
    }
    for (int i = 2*m-2; i >= m; --i){
        rep(j,m) c2x[i-m+j] += rec[m][j] * c2x[i];
        c2x.pop_back();
    }
    if (x % 2LL == 0LL) return c2x;
    vector<mint> ans(2*m-1);
    rep(k,2*m-1){
        repp(i,min(k+1,m),max(0,k-m+1)){
            int j = k - i;
            ans[k] += c2x[i] * rec[1][j];
        }
    }
    for (int i = 2*m-2; i >= m; --i){
        rep(j,m) ans[i-m+j] += rec[m][j] * ans[i];
        ans.pop_back();
    }
    return ans;
}

mint ax(ll x, vector<vector<mint>> &rec, vector<mint> &ini, int m){
    vector<mint> cij = cx(x,rec,m);
    mint ans = 0LL;
    rep(i,m) ans += ini[i] * cij[i];
    return ans;
}

vector<vector<ll>> bm = {
    {1,3,6}
,{3,13,40,108}
,{6,40,218,1126,5726,28992,146642,741556}
,{10,108,1126,11506,116166,1168586,11749134,118127408,187692415,941503421,64334502,171422003,349404639,414370691}
,{15,275,5726,116166,2301877,45280509,889477656,470102989,131617800,543346538,672693081,528691884,433100319,259856352,631703746,121492784,65000963,67868821,431503520,556143263,898859209,822402657,746831347,942022314,42461886,245383965,159194955,442319965,719053964,735342087,986228635,385914410,746460380}
,{21,681,28992,1168586,45280509,732082734,37461992,885687205,403247903,630794366,96311199,188560385,132214957,81864959,656832813,129969437,337127917,885747691,994734031,901081506,113735510,330166803,692897482,221245902,823578678,149151767,513212823,565413378,343413792,552163984,401017125,775469314,768705741,822998669,524634565,141276343,644398112,617812249,791340223,983870515,203398182,625614815,683890375,368195928,142285464,986226417,160965035,405204827,206471233,652493150,587867820,808610901,707659600,22802536,445444835,187616183,160982744,457176050,436730256,169883893,240716120,405440669,340484060,656210817,36771327,96126498,306426249,814430155,444930212,988328253,540530995}
,{28,1664,146642,11749134,889477656,37461992,949940562,34890374,408395779,465431123,169444072,476095424,659247954,873440607,926228358,615656154,946323264,52968124,753942504,466886220,131497623,574943442,651491966,558045773,251030380,281770571,626734327,538734009,338782739,544266404,882070771,638524752,866251039,377115307,677270990,923683803,407681394,135644897,799433050,734586418,252356851,562319011,202766611,459305661,237631148,937873188,999735041,471421437,196454674,548587822,155433694,513218158,425727801,201766011,618282733,853358524,794224019,317787454,420202005,208101995,561508157,165138107,680690785,440574802,642204069,1519935,740668820,993620892,358321040,609591537,544950607,452208170,885834624,821590676,398458087,516061104,713420418,988022777,345184826,285034175,821685364,13669476,704448103,129864472,272789356,791468167,22642555,191074948,725893030,621310461,91319075,716141215,100651620,124026881,366140815,685675711,544588613,31892809,733368799,814661720,416829950,25354705,920576064,404858750,224503153,408647840,32879424,449601451,954308700,384324116,674296838,792515237,188224955,323348585,972509240,558237931,478379644,769454589,5532215,665030504,378063244,50177022,152536855,592606999,936002695,561844587,98320627,393845743,234288387,975460550,94761064,230083310,437478027,493404365,809166706,952865395,30537948,269093029,454344596,528546169,743583991,647074729,593751773,863574928,753557944,354148307,464934709,275033859,450276861,375178856,24286587,880771043,120621725,710396662,135056587,742687865,845401042,8181486,277891374,585736419,570298110,955283694,601817563,141857657,613931527,134904117,127307580,914760872,56527073,515151064,85256390,867641311,644658123,516456196,546485053,695768127,950249035,737354235,328196921,664437558}
,{36,4040,741556,118127408,470102989,885687205,34890374,247777016,233426110,328755371,705627253,787442872,382905968,14599213,54410761,601006292,612557411,15449456,990194963,286282085,699722725,781620769,840139026,489073872,334785849,435236311,109774734,741619354,198733961,979223831,316303898,39151097,758722723,846456337,302710767,751509519,910422866,269441528,739223079,47041872,144990978,835832181,94144832,432122371,718847361,143249505,202420879,524474077,175432350,259981775,949834434,650788361,314338901,308488393,925015945,735629952,55340122,870087004,914406437,652461932,824517283,13384791,734924498,195917202,347913012,345009223,72962601,728865665,529666843,443583543,797807890,499559112,582526183,750449603,794171249,339435367,795879914,610395113,651525515,665256279,771083632,124044838,103256298,555278857,168723782,37135886,926137424,193565944,44104251,848927128,311714530,740363205,103826476,426742610,675142274,731839743,444416323,663478468,724122696,351972777,394976529,438819547,910482232,104665901,409225876,167205682,514913255,760105145,29299318,710711305,114816263,854763814,393789740,110116602,971095517,965304627,656067527,345333181,54369787,393350947,645767328,278297447,584309442,643959646,760481447,306899117,556007296,90782544,501999191,487093902,851119019,214855164,290938704,483935411,931413698,87706720,543982301,557974404,993894344,617966931,450284946,530064541,635450110,955879320,855098870,534537883,745899211,102957101,662330955,760521286,880202513,410332359,896841550,21942388,327590993,607470931,510274101,755158989,271684724,681115728,979634385,116288824,441075062,869557219,498624604,668265455,563569496,411144207,372553915,26571455,299681786,483501145,332251237,514296631,262088005,767350800,242709545,312245270,625558060,630739736,166453361,987400268,534085288,177342293,635886216,360697926,830064107,142999667,796390630,541632626,524331979,832128250,56784302,599770934,420185002,36118708,960687380,886180310,494123322,256629996,167297430,422622751,387880447,805197257,990906673,197392117,409215677,751867399,114891717,20016317,539423303,506437722,420323843,17970683,326175155,607163024,810675077,843118080,586603097,332437402,683685949,604167445,591515392,281318475,78155302,77262870,295568742,84378564,642943804,12418388,229594263,734305604,17384828,186823879,593406287,961690928,25278271,599757507,378599083,885999372,931931154,847818732,310703306,179718037,657210250,145528035,460498835,941558183,335135033,141616629,159440568,260876848,890714211,188331960,684788951,962770200,647749365,692000110,84789890,537064226,34450693,41361159,550194872,245249510,900342927,708273455,11582750,128969774,512056024,55621840,349004103,637116327,221258619,579454604,113893155,576214565,70474670,23918406,481813326,650352628,246808992,284149773,322921320,932867440,994253316,940618752,728504628,428989277,122474883,119546567,24132989,106306057,431011676,611024275,216092722,58878209,120907053,721629563,912245906,362994491,77928369,598179975,862251408,302060801,740845851,459478020,470575531,272055896,271404799,997912850,546477555,102801686,821058456,253389281,766070116,630671870,387593406,363890599,503970373,198459011,993364983,210948547,542855600,819226189,105570790,913838629,104902492,762607730,954174415,72362182,262189042,660554698,644882931,306650491,22189921,453123535,325669077,343206525,974951457,351413353,739439727,691749300,370158155,944047087,188614448,382554560,385741341,62378861,740868823,256532720,721260792,546722312,476298563,606762613,98776597,898445055,605244416,333859175,433695415,401161555,572855900,243667256,85343275,675159111,922771403,996753883,954048792,469148681,19943310,296231983,99393046,204271242,312577414,956614050,159362747,723539464,111719269,894138283,588450712,602782641,981925081,900433722,180543976,267328359,522848269,4196876,67000221,107779275,321728788,528597009,269434052,964941752,949825535,975030569,458728260,549511657,418171228,245570031,648210002,972434486,581872841,635344873,319802131,678265430,806155028,954458488,526854316,847377932,635338258,992797405,996032138,354562941,45336905,183006406,369367986,247817599,491651791,494803388,962480389,263666033,589248787,333002562,984917436,533517314,834849849,760791455,813814450,264438765,491534108,918145304,179243081,160538845,82373668,881806227,278695929,385349193}
,{45,9779,3749816,187692415,131617800,403247903,408395779,233426110,197302784,177620321,206888828,835061252,770003207,167817536,517820843,580617827,469175694,251779825,370582103,72645164,713328911,277616510,902795788,659852725,220506451,987735057,337008278,326694483,929531709,623473947,796684890,777051644,795130911,868689620,888962474,15266105,133906102,896971307,432781360,609904712,139195228,582320632,810000435,144947710,694533822,353828777,974567746,545012102,655590198,684583110,709008352,516538184,177659042,730381723,46966182,70580724,546296538,649380101,839329069,521579662,795443379,918648017,416884199,467381920,180180330,922394205,388926319,338398209,519862997,15436054,832899909,25205988,638023458,397967187,958525485,625245409,761065828,308642848,984865575,166574801,351074508,483949359,826042702,587151802,332893090,23588721,198575871,217064634,935342647,875830166,870762060,431430866,714037905,451514552,118685251,876908840,648215587,848279668,60298648,631459253,423970402,946540283,520092027,98956341,792001638,336970096,931916670,592163792,698538791,255778677,599081543,736931826,498542055,487642144,167722474,425497074,479036070,196741185,39983686,490171826,41410688,950392180,499418290,916512858,995578975,364239372,287759310,305160181,776807436,795631950,394372202,993536736,574952319,609892554,374430406,859025147,436507546,532241817,70196027,667557733,86629981,53437441,215255354,775586987,386301783,329730035,202594580,163573385,90440286,830055244,592282175,146234819,713607860,431108208,391672172,89707230,227887893,635772628,670074546,823064293,429723599,720075550,708101376,728992627,35839866,649628048,777233024,769395244,273231976,452388241,103609465,50984607,571111271,37433616,645071594,241717405,852257157,792730997,762093846,260970344,710690387,581362111,325183396,887018246,894572200,248056865,450822007,28780679,485097554,610718927,844021940,806875641,356112859,159635847,788536148,115844061,32006334,343606685,949709181,501111333,368083991,85114366,231716730,758617505,42613424,792424028,406591750,7556235,372313392,875852936,303229657,493990389,413068577,970321428,914931582,883280547,348694252,48829705,693879473,956820845,494398843,524838672,55642290,291803820,838072276,937627886,352806075,872719356,645619108,203657091,833772501,188791198,15808272,336497713,294256664,801099446,152749995,41154832,192492036,312034558,714016971,939095632,362217612,344871905,183574935,889188174,138994256,960429161,296389559,883734447,484177868,83759713,357767259,405799384,404997964,179592455,903922102,309177362,762328559,846181321,186860329,535482051,303516149,218656364,107450950,239712834,878534309,957325925,369018716,743188094,890784475,179418699,403243176,82350077,760467414,628649939,536068242,546840675,460160401,131727617,556807821,103868149,100658424,320228785,310512098,723638547,644759206,54096166,438468025,280923557,715718353,545633130,123399383,171267284,991718619,983352761,402614189,319762846,922715169,183148106,404824713,482568353,237420087,669034731,275370689,906758281,912995718,736734514,669078916,551700747,844999682,490707946,397056376,72201274,440950741,308110319,99342341,252577468,439457763,862615164,97430404,650977533,227567872,732837766,486412310,424158571,314727501,706889056,657623511,936876993,355562470,9669720,793140369,959968300,899351234,219020216,880286167,595856391,493610283,799709671,824990610,720595839,329639104,976749337,936889221,809494863,315709609,237042146,110330913,567862810,101728268,746956576,529866255,586725298,648040801,779748452,153236583,914584631,749408847,513718701,14088744,993137657,564190068,564615128,218058108,134675641,474742395,687879968,690548088,277156362,833518401,580665444,577772528,19376544,299323127,895099027,299338547,839803398,687138570,578794727,71021961,41918341,510329763,609712540,451003507,709704951,186996194,578245109,487769767,658075788,864769755,506366568,233278984,86797707,695583509,153704084,307322932,831266923,199868472,103620682,993020713,659107946,396528525,448813397,73914984,907386095,831778457,594736347,150616395,988883526,366215643,167086401,868932945,313717943,593312471,235565012,521329248,311252446,123949902,964499849,144982401,326364967,391588166,501164095,279706676,683502822,592927881,202357005,297878695,111559939,437962853,837545570,371947446,187758155,101943565,305769633,
487510260,916387514,682044268,61059324,657929288,460684128,163896142,161536407,538311886,723564214,36418739,327436336,989827281,124248645,832708688,882308790,710452531,77716353,875129876,836074411,531835865,56875321,833407105,423331035,393581722,167353704,46338145,795984501,429448793,921170554,895713357,399606530,448677100,376663936,565811400,301582936,103096130,89229646,456280484,935984940,257863967,62176804,520077003,989724020,230216016,198426323,232816551,723398169,947598119,145563483,543560195,769283254,687695853,412141785,458246892,322562821,870174788,792046447,992281653,261650102,321433331,28258915,361339155,916537223,304030644,26483722,311683688,962388783,635976431,109322303,111089464,562711339,932659823,884184806,961770497,482763443,787907009,283606372,844167426,96801505,102993913,616787769,332259272,90020691,33473958,108789187,901500422,168357636,853210301,871337077,376008840,609311701,33409148,458480523,530786778,390698056,481382022,680007463,849208790,270019810,368593263,287960378,683678741,840373286,472091096,256821798,909688373,636672904,857109891,992260814,638259714,682582093,715207690,600484323,181860536,177868141,849248564,743213709,255749170,601589780,577202203,715681221,735331176,522995960,337047396,380280967,562020808,449068543,963757501,321956499,151307217,161277903,285233282,762020021,339297753,69679348,52568303,535629098,658030018,319086680,600634301,532594728,293331051,603165887,881090116,441710021,197876329,311209998,65489057,438038471,846586492,841740111,900892505,272268279,272662986,89882804,789135775,548746487,93712454,214835785,687205843,809953436,716639879,931867150,5763196,404820388,529438877,222826259,393767310,372063277,755012934,553961581,34305285,137826363,970617902,758748623,22630688,297099624,233382191,919549105,715661682,204181124,621028315,733111353,820512193,577134999,902996456,829943695,846032894,905693877,542196551,252622955,523732069,530997965,533006837,460888302,533952669,844001205,812367056,483211338,158530789,288773918,681553155,968699783,254686618,449601998,599196037,225007854,290070160,539848030,608861062,188322344,747926660,538066172,847178687,798739308,292443380,645523492,583709863,519984309,947227788,785996221,849492107,217296632,379082083,328454321,948218307,458921548,733036260,335345610,773876458,744463437,69765238,106787889,312188870,578318834,7590839,644251670,957688430,335704885,472634567,890314526,887231598,869685716,675313178,908538033,362098899,320019526,244292819,322269049,505039770,483852205,866472202,694039567,823738103,892325140,758360001,346368562,815348254,412182503,471602176,990001493,666290216,161636116,879511684,412410210,446019037,337121630,658855385,784637957,536675583,404218240,960104489,897138435,48992282,548012990,560174715,792156454,160189169,705905872,573054279,928960434,598430005,723118328,3133966,709956394,400173006,843883821,846982537,379029168,361068204,661888589,887835679,493479920,976133608,354917572,765784969,49078976,364396665,502948009,205972104,807960031,802286021,744327814,245246294,420470862,538828146,696329703,411129575,588274570,6230560,547505555,473360733,576825268,869928171,485124875,32250130,382711654,49947367,690021132,761491956,113839876,634613886,973389949,360297061,350465803,385111971,501526753,394165342,117902532,47188185,669058037,586179392,803534253,9867730,117081149,270343570,869732012,535560128,74135321,913166862,745264069,367865464,623137053,135895289,799585395,704614475,888437551,472048245,210649737,887519734,367380507,467654308,310951744,120246371,1570185,489874614,177001364,639465634,752300677,618186089,125694494,282846280,736316609,953882934,653497932,841032400,979929908,640731760,744566282,956866912,308789171,978715397,648405630,702106874,252210450,37223998,173800106,569247455,870763443,145425498,15568087,948078131,543632996,464071584,555186162,273468192,844935944,319095366,541561522,462755462,976898547,38432185,745007341,431518992,996017081,641720868,979768983,850953140,572191500,305562385,828023713,101969831,319513329,411569368,498489858,687104004,861506575,386766011,47630047,485950686,906252626,435904945,523398217,237981274,184197706,269135307,723734629,996762583,961708129,184077468,987996423,232884778,412092659,38185479,920544354,863648751,226193943,388570440,67028234,139276129,987378193,100903448,903580344,405505214,
867338867,333622878,921218665,511487222,463201346,414182967,124574190,125984615,331268678,712901251,926814813,792501262,571854656,980486453,67546855,150063837,986275190,522883996,773384884,81195741,381162217,512867735,787522767,774407258,380624609,500979859,425339121,963880441,911568272,792258594,350130673,602869571,264295247,559699881,354311181,316717483,974583423,385148768,775793636,276045306,192338240,677282938,975826894,376504882,438875821,650005503,18308145,573861618,505201938,646594656,659950897,130894025,249286645,298317355,654311532,836465450,865286055,895177950,246676014,195480007,816931196,479506395,881134448,708030910,402627578,94318479,239737460,50326524,124781860,692461839,182412976,588599601,905280444,671991486,149716817,47905658,64714287,716724851,557647216,28241812,713896117,846376494,206401418,428739231,942397989,324941900,306688147,258918808,206428157,459115203,714606128,901629112,466484868,310408763,294905148,749311051,394101771,403806550,498739596,248404900,190125924,522025988,356210447,962389205,814535861,3980315,250331408,790031419,402340345,314834487,602818980,373056826,513025448,514106359,330630795,280415656,110664532,260357566,438075255,589257527,858090853,422891205,620257075,790506377,952563016,765975974,960893637,543352842,365161673,624020379,800469365,251809505,622790780,765922253,402911760,997555042,559439272,29544238,878217449,228591540,899811201,871109199,546784719,253989180,599758115,684560325,694533607,280703340,236096123,66961640,589317182,148043719,775804319,268637104,330635805,56702421,125110763,721113904,467948371,559561215,304843404,297100892,617590242,296473496,369817637,718004636,526124218,325406214,131642557,869709758,216629105,687991036,573256824,311737341,758758392,234589476,806451920,213768729,631008009,285161193,822185858,233315562,217016673,677480896,804760339,303459984,221413383,399022533,365958714,40799195,381705662,789465567,637528335,343565435,451970239,746068672,166867880,819274545,76504657,397541090,634573222,532288800,461447953,593079116,206340568,73124197,802335966,905865702,467513529,84938694,290540136,695515463,3667894,705686513,717484972,407798786,866250512,73759857,988625790,225509686,921183249,230949763,381533094,278804584,32480390,574582357,123789423,768169179,487732014,297765428,731832401,432860256,598148966,289492130,97013575,442023507,762069525,931825284,458140597,189544522,921471521,275855481,956391146,193634695,84677511,113885808,830941679,431684736,119795183,940323412,300483044,11521577,885580158,695593645,494983307,139383566,821276667,477452984,683243183,361935517,273621685,4025495,476432519,678629225,920228510,134283532,278793091,224178916,869681152,174441945,438098978,983179206}
};

vector<vector<ll>> recs = {
    {1,1000000004,3}
,{1,0,1000000003,4}
,{1,999999998,16,1000000004,999999985,35,999999981,9}
,{1,11,999999911,162,999999809,255,65,999999375,623,999999932,999999735,230,999999917,17}
,{1000000006,51,999999809,999995793,43282,999810824,402417,223797,996644365,5478389,2595314,986300473,9768918,963869,993847324,16003845,978012096,6980821,8542237,992845888,2622787,997448417,1514014,906816,998379872,800268,999942070,999864370,83965,999973375,5212,999999381,41}
,{1000000006,999999900,1472,57842,555056,999423842,970651995,788104398,778759299,323926634,658083892,324684919,79015122,761957547,595366047,441316887,12688266,201612744,847477522,858041020,451868870,223643742,306695658,77027412,173708838,474147171,793731894,264630700,154797729,871832255,115243176,389288711,223307320,881424398,979848061,936686122,945798937,62008594,810844222,523480614,505535302,983769096,982949299,941916815,776018349,223667986,704805532,228407485,821502095,486024197,720816875,979485868,986504724,922413135,515408927,189284953,275891884,961520636,294959301,670341682,948280892,942059966,549856378,20132019,93346877,968004573,6041799,999257343,60466,999996897,89}
,{1000000006,368,999981690,998922178,128702022,622171930,731677741,106140317,806848365,453924327,836855049,142949576,356971908,814732925,717825556,82972688,288503168,120122643,783939986,761261839,454492864,151480839,707484059,187778239,273758032,418269063,800082505,619069795,76178749,957681166,422561190,738918870,868324775,192285044,790478625,300278697,907983776,336543495,672491101,882414802,406838412,716911716,812021656,479173601,121377445,929977582,842638307,519092571,670937179,172224260,242913036,434770011,81772232,97058866,742622147,887421946,943784930,434994403,535882597,485531550,619565648,837313372,968658812,649591907,706383980,176997673,341889953,628738192,825278395,608672151,320688075,906198878,317067145,809564593,878742507,67173776,657673978,851043661,340084998,881179515,232253314,774737263,247463473,562691692,667156054,890629929,723950318,469838013,807785140,842937545,780020976,388085824,692100536,178612041,384920506,637412043,275031861,65727321,694762825,426116702,90858378,74519735,604011435,653207784,854209867,861488538,56370837,955488408,670965860,178494008,754971238,162264859,876592518,739879036,393937587,733541559,728294606,898584731,967224422,477920513,692790848,73969011,920747536,524709217,445485824,529489817,249104930,616150786,282273016,871078999,899999622,293201017,435241358,462351050,18433516,964904564,67047170,364288897,366586232,378352488,676358445,658876396,421940793,915747648,173877261,495743686,650176206,980414754,933240728,190218477,225769134,538216708,923631714,932091627,109931487,799086382,179972353,905430460,29154215,667161026,882157610,547589032,888811106,844270261,986376596,322699082,709615713,883399554,598871713,188714740,767594257,788348805,53766434,850171195,453154095,482639899,948734189,1292003,999977874,226}
,{1000000006,999999157,999961164,22691715,775147581,410175215,644656057,433867918,942780260,694126350,671278496,910277885,39627068,222159471,196903145,564566673,941751864,923053036,147723557,560425597,390658098,269999304,478209884,171351303,559568908,555958330,578529189,270567479,334046812,664084148,426141415,96693084,880004794,17943766,676144060,47682286,886235137,511505185,690272250,49592688,342788330,281389488,630052818,741527500,147162504,786489218,526080233,844683719,849360143,619409338,956474219,825297899,986361128,329483773,139819119,580748761,200535180,128966905,198638619,115964034,783781320,11302535,818145231,362031149,95306287,873292889,472403755,591992744,155624823,403015989,52369871,612067600,384010750,222103616,396297608,47575767,906775198,836323438,91975976,452204899,142236637,409527286,305068306,438587013,313061425,149815841,176463779,579007269,778594288,368560209,74891220,309307880,602519050,210318962,354371490,105171277,250427019,355580248,190319116,115692310,457939375,112841642,434280888,326239270,454086133,915188806,17980197,400073015,358452800,245408923,569938836,232125716,103712934,205173735,883612510,439686521,194095888,846959060,945111425,20003916,419336070,216226312,113595187,964766818,642525591,291756152,147039258,914303810,759539501,457304600,561456689,422156772,659902622,537726509,439944526,437792409,468918100,336414753,622809363,369761224,299791403,731949674,37727766,406896931,262654525,699531783,610657511,456922572,216496387,470173802,409763779,504753339,580555824,796293298,909091973,657940637,815300275,646852987,453485355,562438375,706429510,635132037,553586981,499649183,760812141,511948790,993907029,513039162,31720885,92110671,941835283,397116491,553937218,916554452,644836050,345369871,478546407,266964991,55705259,705666698,442839157,477454241,450600498,97498485,981508374,261633959,97309351,646004005,930569505,855279913,420763648,490136004,721997180,997543168,779631621,506769646,772955503,846397660,728106337,524341112,594481902,339700826,770828149,837823022,787805746,214220488,473371241,895746100,927355474,519878977,173362357,104688499,697584375,185968856,981552276,773183236,387510340,863722737,621285833,237323356,302437097,920548969,660838797,807197643,562669569,422543464,468001520,530195388,992250337,665724116,54578338,513178221,171247934,293744771,888956411,579173543,141592637,835142620,419319168,650565558,650909420,416192789,136898561,653379891,769443194,205628385,992906817,437508295,565166813,169893621,347807126,396291528,748503128,287931377,310615140,287209355,350162057,4315306,676099505,376573383,599594107,924150639,754137626,719280422,853577354,672613114,244257288,958537399,148612508,316169148,267165275,482266210,686545141,980432356,725358733,347604857,926015159,300427234,487182149,918737053,85486157,157808383,602121197,630435844,150339838,633160256,620789750,240730013,29717803,55580523,679161941,788585661,65514307,77500997,798399024,615612655,491098680,73797450,849842816,775561800,665002514,807977643,844974377,161412416,11353469,200369247,469673910,886570237,643100335,503005008,607898327,328714110,936349601,691444028,37872862,18216137,932544081,829923261,333508237,191920692,637675248,696274267,180557278,225913591,347690554,998781460,372734637,865576740,332888483,740444824,560416809,66651664,21968021,487248816,667752393,763417404,792794552,443161549,716270904,93941602,196969246,659554150,116360042,614468673,810414085,88530163,813557138,138511124,276210057,241295347,471498993,547802684,357882085,793694988,31836043,582295502,709527794,266700105,958596321,624742631,331287367,973526783,215293422,945599102,887795039,697018383,135467700,637066917,812387920,477713927,81703211,99583804,3895313,310415048,734017600,163896570,974599336,759702994,493515955,362201400,696217027,382787019,25195250,347804990,58770255,336807315,652135305,464250,612199562,703014308,3642639,142226513,254806040,860119414,335109643,316728669,931770997,768602119,530329205,831284225,631033789,357011056,52803150,453658842,650235010,639525339,53801475,70609024,289563782,511499519,55498233,763845687,958714294,497951360,474923844,879333867,715984295,101354107,532249251,295080098,756726770,369952284,919433882,157923496,258708087,274525434,761196060,570014743,992795005,946272379,825170939,12221018,271941042,17390127,999878386,520}
,{1,999997177,1797781,921557810,555833992,325540387,293250090,138504910,307600795,705495750,265236905,750131445,288638932,895703772,630547320,874752618,771851381,314922165,789447370,99324530,655759625,358273345,174808640,732380182,25243987,139856322,533136942,423471922,230063565,294486527,16104936,522856316,497381086,669209225,761158998,692272234,170512886,924408316,819161060,160651563,664129160,924634280,697441880,360080558,708794080,577100270,26388002,157273456,190495543,697838160,117033078,882691364,159920602,199736,565592991,49932710,744195645,57478078,606092764,162084187,339951019,422090894,340573521,562905962,800689697,199173386,127022932,443709799,352248491,75678195,606831498,31419980,248640051,757373993,621020108,738791536,756374648,698010320,990662712,97955240,389520987,843937275,347438399,28919847,904312475,961453572,647420253,88630856,870272864,34459798,820317869,179686656,67557227,81189131,815852772,454657297,484205598,639099914,591767698,843626425,404554374,437567050,416975856,314171138,676727798,610416698,332377433,749740314,530764338,917338140,600620970,370669572,676014155,175792609,725220998,663457539,479571223,952886192,110833422,421134812,523751029,605708447,659183865,430338950,183654243,432141852,362643820,409524531,611658107,30851994,389598903,554679759,727596733,697764385,596270311,768513153,360410206,279972335,680044442,5804359,676683256,519318359,83291903,23521573,483058896,180186341,62430827,746076536,365041943,899538216,136519547,212599524,289307289,937046663,727010238,949542175,702845272,422448055,156289439,975023823,103647365,366389466,423625417,323389980,625707008,655328128,862918862,94225970,801592783,44920089,808157757,136277824,879777357,284913651,361146428,122017790,601059933,597898077,986616293,572358928,732529224,237764615,828892011,650387677,833726991,370571040,806966131,999397014,231661754,512420251,274352225,277058476,199893332,736876138,731579972,16831320,889366627,602467230,965513330,754208824,211509859,875911264,581545407,949482295,810592891,694782320,183749922,357288085,794098127,247716921,203029320,91860103,499713962,698899680,654720117,697147603,499720195,281348799,416983817,606866261,491035478,509319856,9790715,644487726,797343280,217437132,480348996,647825034,162410542,148208771,120975884,722106969,318367556,92715379,645159736,675923988,485987409,71158983,304895322,382846772,491849556,850895593,269172633,667279007,260606497,544785396,725042799,899800379,762065800,722731070,223211479,611239147,497986292,393755252,334896996,111064201,259607723,774660870,566840147,970383684,544091444,311376611,144527920,581529950,823966662,194332482,938572456,151148053,367672652,537516518,216591282,984283929,619174586,943231071,935482642,994035764,422419861,363864686,958218838,984806586,18581826,477182337,452538849,253766837,70108855,206109073,950721076,270401083,572194436,965845652,650220053,704049478,202117348,615604429,117070520,176520163,279670656,432984694,454726215,653659352,957761070,900963708,881372959,135168347,393756072,762375659,201750536,857019874,10368090,184548947,964649823,497135348,82363799,181790898,914854913,976128342,11027019,635199808,710035264,929224143,945937316,488915081,869041371,538239896,543307666,592517616,938165613,277005797,113918492,360866289,392625446,891296982,537746049,494036034,407608456,988475552,982617730,678041497,961910789,138064107,421578802,899183233,47151665,248303960,276680120,32687305,148360251,909092340,923236042,437553668,493915455,523832772,125722720,605688733,67633679,910873137,514016563,851232594,294314094,509519077,506070511,562059091,72760622,277733303,203407493,187831537,258280312,279097948,841840577,661342217,135342762,247252247,238993858,261567873,238285653,312436959,978814371,555094671,81613114,634998871,610525411,205927141,743132541,665003299,984388748,916395278,171941283,700105368,338516851,355130395,451051960,950159077,671421865,851576786,31706760,317596899,906100119,13382701,809615945,112200355,198264631,255927745,592139593,986080842,258853931,339935752,277564511,37122329,485159331,101282065,506995194,352021924,668043505,373609036,926763555,835177890,350606536,39411297,746452480,123335994,821684206,572188769,265352410,394001600,336929400,387816709,470780779,449734141,897145276,932636171,302472546,257766520,6479853,892118077,242114808,340276970,
546563709,600844968,637316176,471334551,876053188,175968852,699159958,478036928,821644724,607690834,426153875,643718324,919515640,180433797,29926729,134392006,50355775,113563060,190339452,980794966,862335426,436610238,651905378,170318880,655351049,581173512,896182432,812215696,731228204,76355146,478474246,405134890,398869819,476187236,941924656,718924217,503237577,690157179,864547605,137283191,247978623,907933309,129524904,820815612,768316279,877547174,937350889,43939543,301562506,351697842,755512431,705218987,36254487,310852344,109033451,283766253,211384514,165690377,673399191,111310514,867831644,85083402,822443456,563265485,938053557,475093194,169725521,902805791,514567288,583603822,464579053,121254150,215888490,12910271,576419988,663314897,436703536,179032373,454984571,41898550,906787208,823095534,550426804,765668705,504331298,503550606,139673980,839917237,958480479,739719249,407782364,240564673,682932199,136783298,520511517,111889310,551735476,473774359,574400193,671538507,691306227,670529433,112858367,891300698,898311896,901148362,862914412,165786504,890756318,999485174,293041334,402753580,340551058,488821659,888464349,112388546,612259526,177718552,477249779,8127403,229671017,538782523,761908778,444357405,549990319,568208239,364279278,536457050,556273817,717326867,660891568,753560918,757996822,55895763,516683338,133055685,999161335,824315188,694079756,856098692,989793273,355256562,844577350,114350550,206706839,237815553,92372467,399354733,146105825,198681981,760904660,579167612,162234408,190363391,91220959,854365026,836582369,726688593,900706043,218488486,83644047,836352924,551298946,778131759,291876780,537285748,699322020,678826539,185075432,832428797,523034982,123537496,806502174,661974300,7236424,335717950,494961151,789305794,664032120,218566106,100566464,278919716,446699127,78931861,402732726,629151854,436958738,324833347,747110908,860373968,467123152,486149604,207848678,392258996,86445195,556781080,672724819,771928655,286992979,428587248,41446360,140571557,484088747,325080890,757463617,422768891,922721728,36918332,59004595,338622350,334125156,555665252,253129041,49235085,418427027,231178115,277317320,374622157,998920667,926943299,602483974,477162541,715250736,863890303,270523697,76271004,14980331,397692982,833999598,322158747,421511852,360509094,488715013,31216065,139052731,320613543,296849851,726368697,822174349,344642305,975543492,908067535,664749651,620647886,473697228,426203964,879943567,459833081,525445091,904264073,310807881,35402879,894842210,213257451,664163117,259336875,708613696,765139327,960374761,380603441,870445064,111438697,367050828,968833137,991413125,582230354,475831968,283650879,451754997,972523792,498084897,268176601,943592978,759190463,109182833,375589662,86926035,685624410,205233673,772529225,374272871,757182008,711673916,186831158,129859986,118171172,512877992,169865211,574628019,76438381,306195372,187216549,357859148,415185334,821208531,814013063,689545240,481490178,608027733,825256622,638141694,399511751,279115721,613093731,449491845,777484375,491920069,107484882,472905020,346004116,946241343,450562135,428234655,727333779,208418860,146865713,575872263,304587474,975509411,963224553,410366532,369141919,451246043,205634967,409018854,988967741,567125738,146395920,953041599,683401520,713466529,484254062,591340728,121689809,926777682,876611554,695554090,388909435,753143429,145389011,241919085,812002048,864286440,327224873,103317270,322673544,564144702,878777455,930088996,150088545,614882653,878950902,936566040,131154703,611886089,201042497,267661435,904247742,318344195,110720700,456717468,33050782,881067230,689806378,595695080,87808947,569983954,323120420,359391562,742226851,909619496,255724358,625164445,996420415,4954198,365511419,283185542,163039996,861096878,500438933,743978423,65070839,521349341,11833150,32261280,306312372,770894605,552193376,254952187,286487315,879701971,361689635,537481426,645434223,640370096,320857997,831922281,480270454,801365067,24695651,79715447,434961208,490624769,329720970,78075009,911606091,607876533,478539595,752694299,774578808,499014682,172866047,778277464,88751557,785710365,114826667,131223874,691961899,244841317,491517534,755298928,535675944,536259551,76634144,326276720,429166682,420442433,938985793,457594191,735280570,543575273,613111714,740176904,660696318,393734840,
816977675,335773832,747035484,77165130,668447955,552828043,230328535,954242433,941778559,762570557,115941481,456499233,861367478,39955309,20105688,979143511,763514288,353491162,66140233,303874151,779291719,883036223,888008896,249226065,208127144,63891186,673937246,683837046,882433049,257424620,747996214,691664929,516666830,23495604,494772807,32948255,251376838,434978177,636003704,811568333,863258340,779038626,911017492,363428578,388567789,219082955,998114655,795415888,785726393,982214178,229685576,706124787,882666383,691403900,43680825,628790771,441590606,522686064,671804528,501693025,220867908,261642303,616148791,625807710,232674776,170635157,375805622,181191483,417537036,791513698,712991148,855297710,566214306,304184895,835376151,903926437,350745175,640741374,867289978,444545025,291756877,972380579,157252748,428585123,844205537,882850647,415013,986032901,251054122,908181133,899345361,601673943,506181324,211449547,462466013,890108823,782709985,315720449,779159922,940401847,905322254,844313540,760321486,921325876,619414856,308684140,629814994,231676684,164783176,195437554,339089395,984685739,411536968,190080722,602894226,546131633,842434642,819400531,139659150,688547380,574954812,469747230,36766679,253706620,510699943,478594784,951385954,364925247,697945319,130117806,810436081,513863961,535158361,336883041,933438992,606114438,986621843,874037138,588383320,862777044,819232075,278060295,220263905,387361422,26429844,22417025,375006758,87223496,676132013,866616280,371946935,849973669,857990387,689153253,500378564,879858195,233500497,692235234,864373942,974589567,844186449,465089046,985342618,417440614,957542649,392065416,718446013,969726186,79756239,980705971,146311060,89372209,468434741,921396800,858336552,127948073,75580028,397856606,6181897,265622117,43501006,508633965,378292155,639314360,298481966,527040895,182872810,212615396,35566838,185836566,194315162,100786457,571843157,606343844,885287590,843460439,206407963,3743037,406528255,686808904,894728427,192283832,773527080,681019654,168280429,172640051,937350474,479849773,685881258,782078189,46730087,292363503,260787714,669307579,435917752,815547726,982762964,990928860,851653435,838243257,118461776,691160446,247969785,44728247,795230510,200705515,351734304,361904102,467214041,67425251,250955109,421239709,393727716,703239176,729277841,916483745,163950453,966861803,924576857,846561018,912090722,960986363,553393619,919203262,75799334,581723000,681001833,229205123,24442386,4965734,92495648,472362569,824112264,609058435,612032950,7132279,616610190,36408031,909279400,625583652,528295550,626827671,534082066,573970133,336657236,276396212,736811294,474461697,487044577,363234030,999112539,1373}
};

int main(){
    int n; cin >> n;
    int m = recs[n-1].size();
    vector<vector<mint>> rec(m+1,vector<mint>(m));
    rep(i,m+1){
        if (i < m){
            rec[i][i] = 1;
        }
        else {
            rep(j,m){
                rec[i][j] = recs[n-1][j];
            }
        }
    }
    vector<mint> ini(m);
    rep(i,m){
        ini[i] = bm[n-1][i];
    }
    ll x; cin >> x;

    /// shinchan ****

    ll linf = 1'000'000'000'000'000'000LL;
    assert(1 <= n && n <= 9);
    assert(1LL <= x && x <= linf);

    /// *****
    x--;
    cout << ax(x,rec,ini,m).val() << endl;
}