#1083423 (C++17) No.1685 One by One

提出ソース
結果

問題	No.1685 One by One
ユーザー	ecottea
提出日時	2025-05-13 18:39:54
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	1,048 ms / 3,000 ms
コード長	63,375 bytes
コンパイル時間	5,016 ms
コンパイル使用メモリ	290,544 KB
実行使用メモリ	97,408 KB
最終ジャッジ日時	2025-05-13 18:40:17
合計ジャッジ時間	21,106 ms
ジャッジサーバーID （参考情報）	judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 4
other	AC * 46
権限があれば一括ダウンロードができます
ソースコード

raw source code
// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS

// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;

// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）

// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;

// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了

#include <atcoder/all>
using namespace atcoder;

using mint = static_modint<(int)1e9 + 7>;

using vm = vector<mint>; using vvm = vector<vm>; 

#define dump(...)
#define dumpel(v)

vvm ume = { {1000000004,999999972,999999678,999997124,999975378,999791162,998228784,984930612,871265298,895697861,490966251,839941496,996957652,592847946,481262275,58897454,787621433,91835827,919111701,950331560,61357947,894529451,982000726,437575626,23977988,471637136,657944468,719613763,774106299,777216337,184451615,436870027,278388928,319718151,572355165,2172490,51668267,934427665,930499483,877282654,501376151,362834395,293720711,292394955,183939795,639000011,157446273,241969336,414851690,916854402,735752796,584926856,311566001,368505348,157662415,656808985,944528966,208226528,658798917,899203404,524067376,940662919,482818712,980099561,141086057,872852815,429038283,937920548,742073578,339544117,315363117,90102951,708679949,568661373,671064743,471966863,613976618,814279852,832034185,457453864,674936720,639052622,582034330,980497720,909418541,583870262,589780631,942428154,875503080,428962016,424147901,132523556,291303158,392335647,240469956,274310408,374837281,985769944,438621460,755228758,371772935,722973828,117169864,197471372,792943873,252483312,865170182,874642608,583011879,51254152,334343590,815042979,230975998,141868175,323575453,677470528,448321072,331584072,548824664,317811174,734788693,834927057,70643215,212050655,553221796,616851013,861053082,373963717,786448656,143718037,3017077,658771077,291393788,277582790,256993779,737516101,348749489,644873561,90873270,932708442,207333140,799608599,773591959,309150491,828477165,465716115,747748227,166204020,662129065,160328008,281320398,940620478,660542616,817411609,679865753,409984478,10225448,982161180,520300910,483625685,905022945,956443859,664013485,85059314,699841059,594040020,466017906,363463994,356532006,763379724,315944650,273566731,154827127,92319444,18253452,326756926,355531846,537752238,920660084,553946295,737050552,91850408,290693753,846425090,166559538,411998617,588194832,226235143,504637272,820288159,799207423,526536142,568503317,968122331,418295867,340716708,199672982,269046906,476320640,130243009,675860019,3107667,254140513,602050896,363149232,184636062,558837226,52422094,54697841,262395108,951966031,699621598,533028931,575456411,206397173,380070295,705318007,108406971,142181155,469738828,684199352,39288553,957700135,850074294,249024768,937178099,213442433,694366913,919238706,199368773,89992202,847765610,703525591,766882085,469000992,20648368,47296802,743555642,569319918,463141716,40717478,553241654,811392156,401389585,144556456,234322662,329132965,981547503,516931775,489941564,130404672,455415449,223039213,626229722,25476463,622993793,447222003,119875440,317888443,820752589,119016248,862367365,791659898,407191399,17479940,942419356,281951818,157488816,715555947,58297611,996480308,52800715,168279999,496639563,793814911,675885613,372250055,15365905,574740571,589158313,152734981,584397846,969373243,296234027,781410439,797186075,392764976,263667687,443726812,966848555,894150756,266072158,785851636,643986729,613819860,422362484,821160003,402670472,979923863,814833079,548166244,726620583,840155675,78326825,240699229,328982313,407922907,628678147,246809353,8765302,955039932,159628941,128847568,102334698,881946270,317327163,682389885,308848937,940909504,449716165,565822438,865203298,3598467,381846,430820597,105374501,329770350,393705346,385160140,273302979,362974352,971957262,578523080,196923772,602597066,783422499,803968223,115612090,416287111,156213339,100196702,8044333,444371025,440465118,998130277,420476503,823104735,516709090,6201871,135144376,916360596,984250483,610039896,194616105,13571614,460981670,935622038,358429615,343923587,971375157,401225141,161794507,531118965,851376611,245790476,764202389,572608363,385468906,583421121,862291675,98218055,195803350,681702460,382490519,309285626,269108458,853215672,702367375,491009704,891744056,757977178,754749211,648089158,184052869,665743911,953953461,591819809,703121914,347681229,507436441,635875723,590481706,3289257,663612276,882236526,582531265,434679684,421758450,808918480,642684496,666510300,976185350,128542969,386877513,456586879,208713948,343957388,35479508,794394252,805751979,972243500,208822010,125576890,6653925,831623548,861568288,897877602,830886381,185495338,743602127,660556774,293059053,316079415,726363432,764765684,616076449,940805910,900064680,726282686,438228819,374081868,706762511,944624270,693645110,865394470,500280642,240714427,543221489,687277887,853042788,149374581,296345245,36535092,363610737,590167687,2832752,563677123,811013787,861299959,440635542,357680826,648568941,559953191,267017807,66635698,46036958,222786594,332589715,995280838,328963329,885978696,94210356,14527516,189264930,690707316,453575160,424147423,84503674,578285190,421396531,938465933,128319602,799761438,723770777,446860387,936574397,388552344,641819017,438517819,893394426,802078515,654717886,55133387,249375620,472298269,117045665,986898558,97816433,538854387,901717263,418254062,788869340,108555545,295873630,213992865,476872049,518253674,72518632,842255380,677863911,801786694,143634832,206375904,139577359,360817331,114799383,201929797,699236045,782515188,700542096,794547755,914143675,235969829,331109574,264406733,377105846,959823079,930939393,61881008,740872565,161464917,675075642,138406306,243617203,729950963,374849370,938481179,922632816,387598875,289698947,266662722,776717212,569865889,707185014,121654644,76637067,297266198,595495160,963647722,161943327,60194473,395451658,851985725,3133589,653093025,728891059,432887303,391016626,538617588,555012066,548941089,152228655,849087092,611447017,435661462,723743020,646313429,571262499,50182506,396227660,995452431,128316611,135920623,155048413,462133277,334147052,516028861,466794996,858154014,795413822,264722668,906624518,736069126,452394687,608313066,281585713,287423561,551464455,832415684,785140654,707601535,141137480,871529311,862009979,175237227,912931799,404636265,608620678,810711928,351260077,624145175,56011977,12596454,516638782,581406406,908930382,925550070,862060272,440025819,652622752,363913636,537296559,678377818,641755162,230085533,788141881,577896772,858001562,49327697,883245809,933425360,52934470,333921647,508292622,349771365,773903833,475933115,355532596,174183194,163061909,955767704,730396918,375905825,711427804,552329037,633882307,177029367,639252730,499869987,910701967,892747133,418727189,912595051,426042106,773577907,106411304,504708184,723393643,170092444,458316596,473063686,708850359,859108259,846830127,555742076,994919030,748142935,467350585,815809662,708045762,375909939,933776574,454071929,186659869,56925006,348675985,467007881,915060759,557098775,900699648,922283141,830146178,958316545,526353637,271309036,223858284,802117176,159486560,780645615,417462465,764416579,585360628,284545039,347288784,610856778,112150908,934981323,746727620,35534005,39543225,533339346,708501134,664796389,360024755,344098049,967978872,958804575,974147091,513530697,553203638,879993858,679838569,823586928,107132571,152347382,681406188,338046929,853798492,690024824,88897630,21468929,498003236,706104338,411655998,41691128,528076384,823486362,173858940,114759262,708453535,461310011,696996712,989464123,363018517,585300278,189602237,996077713,108900556,262302008,587626986,109112185,841602276,81047880,116523423,6990854,304345105,58162959,889995580,37926424,744489096,82191822,500169514,691298415,38560166,611738940,311701263,751232553,641947948,713744073,933110266,312832754,748457812,699738101,778762560,458753013,378740565,932944677,994841648,584165393,74225302,492332894,346537695,333475196,113897340,160769840,563092333,563804983,98436699,345864052,521229449,803571782,848845393,958201420,941257278,476739764,102389636,613994038,852398483,501946433,472560473,239787579,182840208,605914686,451669279,22109142,62091506,230065323,699890012,469047231,576424630,311979028,264223555,866056719,666059165,516233532,946942358,194792936,295394273,815385120,736572758,545663809,236300833,715815080,775265095,402102127,201364607,998768189,962961120,179942188,326189501,725297239,912047770,850843309,434410225,569649727,74881473,520761374,146279373,258306792,330909787,474576660,554172287,480483505,975556605,381129784,291673120,227743399,626293371,669016985,527977492,176348128,788684335,932998065,395021433,160250490,457227954,591150533,538912994,264982533,640751676,85923990,844429899,622920241,244505079,123560864,751352328,782393233,436887249,722558285,524767195,369743378,933992802,362525882,612742362,765182077,343792128,127454563,285719546,722521456,212755112,162384819,154382933,203666045,923819787,527469641,978234786,186306023,81674811,266565419,599287974,81028424,889412739,494315545,773640191,110964518,224566005,541207243,702310390,436202319,625140951,551869123,723689,288033550,608275361,224024637,557710009,631759515,223625,172190358,51105020,213662967,216903984,380902339,608092894,968407822,306564272,530334498,690924040,430028379,788942794,39373603,233602519,723744726,823424732,306513321,736822914,403641236,319063051,962675076,548715488,58936751,239483998,606010758,922091850,932506433,96429012,849014879,542116715,161978208,179286730,166289012,874556522,182449320,185792463,283619284,682539455,560994632,467003034,567125763,726892573,710213626,613023783,357212733,932961143,734431866,222391727,438025865,835556870,476895289,541532427,724963073,154459805,65859491,203368299,110359496,71035786,736576626,300438906,80381082,303956377,918051070,456256192,354375671,935877113,696105162,901893000,517045642,348696906,362742809,186955542,849047099,793048871,991673380,199970834,447463290,878384653,138607220,880487604,107970116,27091620,321524894,479795336,771465450,402733857,817284421,786182202,446594964,889814709,268300925,440964063,338200882,430771923,461937238,425209884,698653255,19293711,938065011,87812463,495222645,362941647,174597888,859689059,151262530,259975573,508874978,485635628,89001878,497431991,931518683,624947130,763693552,337864475,405239552,794029106,849201133,451992458,955941077,770620119,818512546,860512095,880076635,50018997,444207199,354111422,341655651,369538929,290411258,105077119,273134180,657832722,902079029,819915650,510073628,450387990,494164474,30209675,268511990,95017031,477262934,226420879,132887624,795551541,121100371,420154370,236733891,616665579,825830849,838539711,657273174,168724201,484147422,969881660,306632738,950312274,976767164,826881995,21198839,697706962,859259653,945834779,178423109,752412720,759824558,751865986,982414110,552951137,559033708,190287491,308536653,894666422,823776217,533255748,200347479,288339621,874633647,696494015,235983415,873248546,348221342,242831411,209292223,956344765,703640889,645529541,582318811,911822972,956738598,502313916,138259096,247915961,484483409,596620159,752477359,842529230,942506436,631973089,286431791,155718094,755708739,460351961,14262394,517127013,593888624,609862498,597984688,134782558,60195703,525288698,826290508,118430474,747409789,592352721,131207228,758407934,772027229,239074218,142724416,824142310,303896129,489091921,663968030,105295257,722777624,74906743,259326656,848335244,6636536,123154242,103852204,66042210,333632351,988897834,506208594,338504353,487192373,318881932,981169671,917236429,662650208,755855277,155739297,942356020,888180284,286934842,346391682,640733689,315055613,904644716,311697138,459714154,51266507,146716399,317797165,79422350,213399673,657401794,682536289,508420761,627302516,266651880,785101833,207630318,194278942,377910126,844114504,18551168,231251205,508734209,575986667,16018505,501803294,589312310,893507149,771918718,51820164,547285270,616280618,913312292,54809444,302092587,483546588,303422436,594826799,860804789,599117724,798505953,234050560,423756685,446037088,547056422,517938534,341674028,418343133,218851470,11045516,282449359,78976411,519365834,921907830,26213934,728315805,803195214,610167702,713450515,535313391,183803390,953286011,438135626,475570157,547012447,38495874,574565249,350898586,514515974,589314354,295528714,41026265,326407232,394487192,483112132,637729121,666579207,258320269,198233948,603029266,539562362,623025048,425906204,530920028,354209027,652835774,70857440,501859238,705279168,27817461,173031634,785999294,616234174,582772198,833077659,503184702,886154565,60804908,131005980,5832892,485917102,744593411,878684217,664682932,589324580,961720830,792917888,807068642,820769155,740515571,73092168,550034022,826825820,90121719,246104866,18198917,339261902,348718360,802028685,102832964,205156774,908698028,34633959,314154721,7622893,364879972,64785891,821934709,370452416,129851499,618073075,10747663,818532798,731851908,469341371,150846089,549331031,955280001,154489103,361655378,638856943,185256807,107047654,919396548,106073477,685627531,504935926,6074100,757331656,562832295,568693302,548232723,209862196,447381550,803831694,193086706,886890187,236789370,643660583,551249761,250326919,186593816,497639155,475192681,883794846,606903185,639474350,434091570,955034799,472926401,385869000,429394413,627012369,889810898,164975806,113583323,881923839,155956892,805107355,390378725,703000646,976723419,961699035,23382628,19345702,722963736,587826660,400561288,983664539,969085359,258361015,348222514,142226487,471163462,297557393,76845182,748383625,602698534,19199469,210646046,8194564,908022208,977991674,173551734,709751830,920421966,188809660,4642062,301766803,742960696,180775853,524383898,447240730,180247884,102994609,751340849,315029673,681951282,782319219,662472920,517424422,937156422,669148920,422315973,322030031,197420769,508991497,479811368,715915749,587816777,397585834,155358690,139161186,532249025,690493476,607575592,493398004,755031985,785664889,649470892,163921172,675848320,643204018,251595330,325366527,707859028,866934140,587345237,559664720,838099180,922519643,4133096,761672893,778217976,617444976,643912433,659419469,679429532,432950414,502364404,40433462,757608038,155283721,523034435,174601272,486414336,947598538,393642589,825426954,278522577,782615750,86765790,800374724,587611615,769962329,907984298,481325584,242306313,548345833,338748133,673967729,851746608,664714161,434255942,538855831,40544378,508393890,196884412,616729884,45832989,637968253,178811714,693536300,266312222,159274521,806406327,646392158,763774196,99830334,185391595,956475254,113593002,830815351,696952078,874002157,450683133,903509684,301421558,797409387,763632424,146403565,666529287,767533254,534964313,585277325,305407028,949980458,182577794,482512995,838369755,373326009,970327019,855838011,77610190,707246744,489919548,890508322,780828763,124637333,76451794,358191887,856588426,946341691,326878203,208458957,615277022,462370479,216607180,238508680,223414542,825396298,816926733,866381223,220536553,782832267,698050393,194092996,610209494,757338474,44817560,321522124,445111746,63638204,202007562,345605767,467312039,112612817,496045118,129979109,394117367,750430243,851517359,898424046,44457636,867953567,459103209,918628889,328854244,758394701,211724006,5170014,86004620,136154833,504040797,455030878,117509270,317599815,694588572,560951558,133842474,10317173,492496701,611689010,780771386,354420874,895750508,557769372,317412848,811435875,105969028,670366739,883841087,376387785,235965812,598776882,38733860,44393355,115913515,137083617,783458018,9273974,781211989,586491218,127757396,114867074,904718640,229085212,548880783,254291226,261752015,950630763,132186040,586008798,328965426,168698134,865814985,986002932,391939721,633238864,507764679,485313941,760827607,112933707,185533348,725929162,633678705,135803879,813784170,17925524,876900337,969904156,448860671,627622541,266803811,332947903,287827910,949264675,785341478,379098313,505214038,549562157,163442880,548075508,192889271,938809354,269935308,247221270,106409609,261369687,497475449,308891259,444217366,981641355,616186454,845598796,6986880,691671275,671645555,467258724,45141350,253169823,738341205,876770147,320407007,882050841,704054941,712675020,53729595,207379895,620522810,688067340,450891681,574395248,153483888,796145134,823808531,232600184,897148264,337296253,227866261,116768922,736306776,736897252,263249791,185773883,346617124,141939753,265282321,246996451,130307707,869966890,283390091,800612417,582648160,773987620,424388017,140101865,501215315,302794270,970587165,119115106,148774448,274924127,638360222,578441074,937555731,924486091,324964936,266408443,815420625,341214447,476396555,555556845,889532815,338358471,267213277,386830316,221727315,605816463,654938822,873674598,124198303,208955165,325581829,265584223,535146126,494216430,961819982,760636458,202972809,798060836,81102726,181020486,678149279,422400324,721136668,311519999,839825120,253970371,433839716,774634289,526490996,822660556,836144720,921646354,617050483,130594373,460975019,97446634,766870323,103812767,716966235,524746356,977280999,376981488,111633375,66530378,589429079,667806132,455601626,879200571,29001053,476656302,609231124,576506300,116476035,106863559,860720092,200912905,925570914,136984819,864438146,670587324,188465740,968231409,972675992,666139935,895856298,960192429,440490999,143274746,485908582,30869515,909685996,467435006,584205850,904369544,594775590,664870073,903426251,711968528,362531492,182010041,21868291,355552195,814949898,959801657,458220579,248471733,243217510,924610793,12788332,292219102,289540581,223052039,557098524,918963003,67616486,119701311,641062810,736325178,257535945,262684575,851411705,576182406,289062432,701386794,67573042,493126281,276086825,380138893,996027911,599479351,710554689,184404232,401567565,141010616,934369859,698930011,895735397,904700783,932183171,836378554,802197095,59771578,468885240,462506015,930970409,916128560,356331103,866438161,732330117,518839479,335045418,150104095,562821450,999722149,515790870,12603510,913959815,991506197,393183010,157403230,943912150,383153776,308359261,639240465,196003397,337770608,425540979,874356231,152472100,106064726,382765863,800480158,962070388,336689532,592137728,976511205,806151206,225402084,335604479,149130889,286259541,126827204,103068902,155055859,39716991,384331962,605284406,233338633,268107484,297393567,643327462,116177778,371844278,115800502,328856813,568507317,580369651,699301015,715561101,542957565,101131802,910568432,556925044,641196818,417935699,476560098,881057635,331019056,629626501,243023701,509597438,280934292,193953165,696451366,967308569,42856334,901042881,111059091,764716107,806430075,885763188,105386322,739874883,484127502,76655905,326896160,179647543,985797525,131090708,84373800,761412475,686529243,820528507,892150440,8697885,468340145,758747497,495094273,494527475,349070550,789758700,931818928,175226445,245030650,996167150,857571294,207430109,634363259,963746677,140297473,187455723,394870949,88111244,79638774,868533242,778441139,433174498,542781155,546719933,586037844,755477391,9086819,392342566,276206047,920580182,217619726,686820689,371704896,574182613,373377195,448504023,881458972,492250644,851012146,182772104,904784572,406153134,956677107,485882607,949719677,487599075,867898223,143434628,816376692,517356262,99911766,983039118,411150687,154664366,753378773,795005801,446435787,754438307,192517229,511171203,206592423,454178064,509138183,787209526,927182447,951562620,455718308,334559834,965730774,265569884,328778281,597915402,80260150,513455090,890631258,570599609,2850916,79272868,683042090,360000488,690231052,489132787,770586368,728946716,445852033,520158239,676813671,53080285,74062201,262275821,840759874,366688860,485073650,487486207,833872622,949989589,47509088,995913801,736182156,970093642,618488470,616960565,20650479,44397226,590441594,225535476,429837680,428575294,865115197,319983623,586946762,261330586,956046197,34349937,797616741,140080690,984868447,842186119,125583210,811569579,977031838,541499542,76857991,643566330,852288190,502640668,234042179,525226012,51920329,943166425,870895093,478852006,813316602,495650245,490026863,271176771,849981180,947550541,115496050,546618017,477574414,225550394,232901516,21159664,321811445,509521127},{1,21,337,4405,51371,560067,5850769,59390317,590782999,790230492,115202775,88793118,853981243,888221156,970077888,926134651,7545417,935186403,898895229,508155071,25359719,542531669,222936781,862446127,901726230,359204302,537678143,196083745,991629746,423305346,930321739,366867926,175922213,214391318,113426778,968761816,779684104,556695767,468057438,633415606,327246125,541052003,577080763,183628345,805860697,518394471,910053642,208666429,280803088,993548291,540599976,385101739,360724391,827401160,404807489,533964038,565180565,522063780,862647469,363920660,546759831,199250691,815913934,864927274,803250155,168507600,413950249,666269962,152692515,272810214,642984007,165490240,969212381,823034015,570213052,514238144,144912487,772316872,783721735,656700270,769153064,417593493,346715406,756399020,989899401,391932056,313543533,401466565,535704638,521079061,637523171,973580737,564301520,853652630,797198280,989215533,180646233,125426685,758320118,720640987,327563636,515711396,508189732,822582549,839184445,515055683,994646344,437079809,438098477,408336177,145315315,773677143,755830572,333008748,736078580,145242279,632098505,636434434,328447056,958686948,744727069,546515357,482130327,659192850,796739941,142826216,435779061,547576577,153145824,524361874,591520774,690608943,946385840,544268764,567191384,355485935,991411515,639844422,881175719,123697465,64484440,437039091,946259199,983567292,705755383,257328307,953543107,582249045,446287721,285943272,542285660,435020896,899331833,723251840,619758022,369030916,192946875,516060093,651547913,153412367,109298840,912641072,517197922,753608214,664414127,959748319,611490643,608885215,461942549,568311509,575161665,280323851,262493134,633960183,525718554,590420214,712999039,775529066,865272686,14374671,655240437,504961577,991310410,118953045,75277799,921391074,647576240,472301224,6760388,446820186,117582709,290053470,485904680,182880472,213521782,803823913,300651829,346867145,861753023,589792418,790591699,274433988,346696782,525028587,930323494,659855304,39047643,980478603,767266822,569865424,989746652,695088298,886098648,736742665,21252644,445612628,216577767,427134519,462824243,480104772,401849564,838536121,402725426,862499600,909276358,771457061,767082809,418065045,834888937,220237584,810834724,687980306,245399484,401663136,788580903,192347226,869383661,244026060,328943714,605058512,597245093,990209312,106514531,222736797,53665207,75640119,502592688,311661832,130635574,270226507,631696037,646443402,510240677,919264648,584868821,25451674,946449231,183232594,809897750,352324649,986465326,228259924,340236475,725906802,639113790,695631866,223586265,783359946,481753167,642385313,653986918,897157410,380338925,649219680,472240650,464633276,925563732,114070068,732337392,180973547,867474847,756473018,730789171,78767530,946139528,225340641,203114996,441481930,994684755,566813072,938893700,447257635,298582030,763951816,75229676,322163136,673844150,722618506,70291919,848093981,338074651,40158909,170463077,304842161,529294414,65157809,322578443,178736309,345535636,441224771,735620366,943056579,469046756,95457569,443684632,348208615,526891635,628837539,201188952,580256096,445634173,528946767,305723990,689515420,20174005,347703539,191835036,901466005,620671298,895275647,614254703,974237287,722058954,579049752,481060845,298354083,233756697,210898455,395465336,296158754,26711262,29320586,948965413,711828984,861680926,582697127,700441756,729348610,12668443,167093746,36017060,435031112,206714907,471218778,713731048,219817569,982778435,42902591,670898252,585230168,29623811,368140096,84803403,711472141,239231604,279658910,163653713,583300745,163299312,479539056,117496279,753846477,321072019,949926811,453545277,964392053,743033345,893767911,86052183,869803205,328932623,788159611,449773333,789279823,860815749,559219624,650450633,414760149,83572056,281814682,8593556,919621405,811601175,535460512,339488450,106337012,354952201,957825700,61444494,967321146,719327957,389606896,708028403,56817903,49415283,284602099,555736011,262629128,274922065,583642412,895265463,347109526,164665880,420007125,450833597,953788041,922539917,97909279,847551172,580467187,143321323,786266100,96718351,104791955,984200591,928165440,713822169,772570098,366284507,457775053,283908679,318648717,484297622,984485326,860336449,804393498,43857254,18418186,860041343,962229775,175809240,732729131,228179693,938232691,325853085,823660956,667213053,669518384,206296078,223118819,411125342,610329754,82049550,913186224,894337422,919536017,856005427,219497883,248326842,972115157,552524575,658051218,193024498,258442088,351431653,87114329,731191256,443926206,984448007,971949327,262768759,472616209,694406419,620295706,534652793,30220210,873888294,633294702,113146831,961225277,487602641,321793586,189786393,85185552,130786643,821579797,668820693,467979274,170935175,45394982,884737851,275726560,762068557,229936379,873003197,936662310,961850113,404200856,45957896,550233495,684314531,35426,444398438,638812220,808055447,449438927,916514762,715118702,760321732,471723426,685627238,427200832,680639317,163151910,353395940,511996032,184069027,910606933,679302112,888779836,508103815,701601960,321491462,215036328,344599401,386366545,685665889,102676438,587462002,595950996,872564565,439927476,583403315,409797245,427301734,395771559,700662505,922235873,593598454,374998218,235918028,158492342,555644137,601987173,147606163,680581393,986875570,857824299,645790212,633605198,737207796,13328024,288465693,574221142,721512417,654289628,246099470,897776993,648666899,233861045,463459012,348620557,805301193,946797508,151389813,414127951,7560795,527736641,997059768,25847093,108014769,611456864,787207017,336252063,701402721,230255068,510479,422926505,814481886,731232716,390789351,409817338,488016975,870002903,839823148,128471929,665561776,441555108,368972632,734316236,884340655,494520705,164643706,79889015,9228089,733545493,901431073,55522307,278680792,895326201,354138750,372348160,232654930,953159045,325205214,533357281,381748875,942813287,131922673,720281169,271650092,672451487,167363381,594919642,473977885,835397746,780458703,534405878,193403793,110114913,514617136,356232005,500142156,858962875,224990436,103460418,619164711,255502783,930897362,819523486,370002650,34673774,457406382,859911996,722545882,511575886,288930247,811240327,478353339,67090565,404132445,406742935,119037284,589938271,418400338,242230652,5408769,610204880,498516862,229937454,45106365,170137381,419917648,220485164,618742040,43386662,158637887,732335867,44294443,488099449,499347786,262270693,526892200,430121167,738061960,116131076,594582950,487124209,80299767,315494017,88705989,289495994,173978320,510635873,70353267,994348825,825132358,775061537,723707591,336361325,936736542,385649327,381415686,802633362,97604211,231467642,928476530,667876833,649667006,164689211,164324391,798779069,517551709,168700012,195968990,63025173,109079631,199340074,815031380,209154398,136629795,900646202,729964107,684074056,88576895,888928395,25528464,541736212,495363820,674789864,449653960,34344130,119048711,828244678,585302885,6136541,222942092,335034137,742620908,870479398,838530300,870522900,926976500,774619023,756217309,318692076,484012513,570176981,198823607,274291833,193135501,216424565,810312486,741350428,279687138,233383005,279608917,516611812,644986013,118433259,24879363,267836789,53405007,829181797,282798817,880073630,452166036,546659449,603830925,256499746,261364252,773595182,218813887,512014787,996509253,403622002,179872153,266438763,822790196,880268844,973478679,310234987,240276197,187214352,70620811,389726251,89300012,178659403,849206978,661378834,469294778,873474110,885814601,705749205,808591096,839486171,862870702,7397748,452146228,64784701,293958694,84908795,672490323,536555192,660157169,137880999,758884673,564306026,589344685,106176411,931588475,53109109,625458155,377370421,774498947,804188085,896447340,448996529,781377716,828914866,958272913,83620044,282099711,685077437,512376598,321548391,902027751,670541025,53442611,815389287,713011508,499689838,420808548,229792625,513907104,760092695,866382261,737438201,49497978,535384508,370322352,842655284,624564918,503264511,791782498,878846913,185977543,681073767,484785957,547843293,967997885,224129859,523358197,549021675,545011678,700255949,501308455,639459799,78960518,812999949,535615609,889189848,102824955,299753701,372204951,666132420,84364253,966523048,478142733,384758330,572903599,91969837,273187019,533506936,705253678,44095385,648112846,645081222,200672445,965087150,415000776,825487392,639272824,985822625,603722037,639501284,985333589,70347844,185990828,987728924,778711632,802949297,730679677,226139036,295349110,498002395,118709025,357702333,19220381,63025737,754029685,264540138,473167751,42808292,19253590,907769593,857010328,319141135,518312022,707839500,543559303,747520592,607222189,357429509,136575320,288949529,147505141,362344849,72508382,961305957,580217166,345520304,758207310,943593584,2728765,665987130,20538743,635093806,197432217,140806232,508471228,559466202,404077222,138399961,577691382,753596177,811782630,91486899,377690259,602354562,806037229,523561742,494158394,88057309,522792640,652935225,52350267,846026162,647745484,522175221,981991631,95277927,501552146,793036400,534235997,245151408,899678305,649419501,247311486,27982854,22939978,67796989,507886294,922954354,988599357,73898362,963116633,212424347,919396972,424856341,920388575,298202099,896014847,200834379,289069751,828500399,375690090,827541024,572878070,478680394,256018006,704439425,689111019,97859500,1768283,711192344,276635520,57902190,539363292,892572022,811082073,852552314,222089108,540179036,442876169,247556155,702313817,950111266,161207670,343660876,99651866,477530866,173902058,294380250,555307294,324623240,926202700,543689909,118321513,173105535,219111686,149977464,348544813,595725186,167827595,607035255,533264135,942458748,600200190,511320175,58279539,990757011,998368131,636422796,511575433,7589321,190312715,562674235,281750300,609154911,328372122,225081327,323846781,887701982,688605841,593378500,652704087,464630168,369015215,517534680,197822130,510003672,77260955,136681696,458649959,585053728,321075759,957202823,734261956,821505060,2059069,129433306,906848106,356536201,965336506,577152802,854481797,473684733,136006215,464728018,824559481,932606575,858006406,730004990,312371052,209051343,391400809,452102878,57045503,655503072,164284230,358067887,413271365,718238218,724734061,261185553,103214042,720834066,145027868,127732702,542124125,272683798,261092030,532524784,3880579,495779082,701143769,784029946,125849711,148363810,270860855,26117244,97789163,416827966,651178538,97465073,697602584,242968536,412289618,921288803,388734823,832649456,817504662,476491475,396385850,56480888,95641634,581470604,887596918,257294933,208994489,952771442,438050380,550818293,872703054,967951196,726524157,572107696,562612942,191861307,640660799,564998231,159888560,216694443,737383233,766794896,887065273,201979693,819633225,60193999,642834263,463844208,12096989,206190077,897652041,915034577,974935392,808282032,677984338,494036245,545680377,90619607,885846984,682862314,821181382,195268356,140472062,715693095,98205690,107836424,788085351,144312599,637586743,718855505,162202453,895913086,119451397,914861521,917545968,447902125,655710797,652791097,354548346,487820102,692645911,818721940,753034334,26365883,410760834,674342387,916868166,646613351,844226027,117765098,101811100,283261750,674371811,352874794,16116542,65744493,987776973,792222145,522765871,790457307,741051264,568653034,496900111,363181245,476225676,851814744,167642775,43176654,874830317,968498943,684345751,344279895,832184014,435169331,580061531,963530169,813688449,354814559,406452830,669394625,887311114,594921675,877457913,217314952,269011262,147007957,829785575,678395292,644442731,391137784,746108493,158112675,47508446,307493103,337902018,669699760,216495344,90160216,437247689,545735156,946854830,97151231,652614477,316488300,814503551,129976830,168654862,641431429,437820815,912197166,874490360,554379373,888468281,729960656,307606765,613451237,164467809,174381552,617493331,680905306,34535927,673983838,995844055,604088655,903474896,69031381,703951185,445022836,21750731,977024216,999563059,581603583,835655995,686659921,182773783,333827824,498916141,115722174,515955458,708608658,953764705,89444711,847978212,603384975,23928859,972984863,763703240,609151475,282927488,783058669,18934804,823272653,968606558,769595860,360952508,139854139,78495474,425608286,302253717,640420603,46920789,160486591,367067375,246864453,151064018,286763919,325770488,624635698,12520054,610411997,422582689,279568980,145542634,148660543,42946995,458339557,989152287,495201147,233976932,672065648,551078910,111059976,701959009,758862231,6357971,216802167,52334840,656293828,892817836,303003364,228012943,785153002,116517725,748075919,815345970,401294787,707864448,724650311,260356824,706541798,713062131,173373334,254525332,813068604,361982830,300512144,615894746,160515249,780179180,30605544,535348085,854137765,317688702,350831283,217757492,182188779,344937259,201261400,117973806,733463328,125266127,990847953,237205056,460213919,981026534,937637074,80178202,895866162,177547372,692994183,327202264,339452861,664995501,541968331,193013982,93660353,612188976,125805652,21124608,855440656,843500476,953054208,259747712,422617362,196476553,569442069,337756600,283148665,414256823,573479787,941976544,263330827,811464974,391976084,801738331,603140156,546897513,453497934,233988900,108571495,498885898,933396421,646692645,176694378,941375857,947681023,403829174,162298734,168742624,300603057,584140098,700283994,228820956,346795109,795172927,745469762,481377495,836011054,896148809,976055210,534158589,45798534,226173159,617205258,807720714,687755538,283688874,880728052,233069062,315211872,719722092,612172192,616069855,395232635,193606291,706215178,365781838,818986249,119225215,380484866,350025861,191806170,549259548,409309255,158521382,434632653,226772012,574715164,391072959,237481317,61116331,868631029,138524862,93478980,194969129,970562065,226781415,943911997,463148664,936929641,102888829,350415722,255397906,94470467,425415035,159566945,518070112,18867915,86473154,626429502,694747974,324150046,662815677,818791186,214193275,248307124,78818748,622145585,136271393,47505236,113136747,964109200,410097775,2106002,165098304,795777223,844035638,869419402,11863735,70223837,982405095,873633443,979623712,237368842,362221022,777717911,562060380,189691630,851919256,635128124,719460568,589120103,494665554,957969736,218325154,883166544,76832842,326930612,65920278,606100562,419247454,458124210,574559104,293109887,933575768,721493306,153640937,857311701,632044783,896692249,277573616,714547425,274591628,95932989,681499555,760263034,38600365,824809180,728334547,112338194,534203836,29396637,569307184,249588417,363716116,871120385,799086426,906477745,318314269,846046959,212045766,373358573,103454230,934448999,629190316,403815324,579441160,997872086,129964775,755027243,948957877,990058216,344402826,480978880,301749406,726563721,11589203,711451184,498336089,133431606,247690604,274857666,952393191,70054482,526408781,869712249,949965219,753675110,604484914,525197642,912420054,50428127,487826132,745502175,228289616,847860421,907165371,816624358,788422990,269284477,414561044,629792811,919643770,719749581,530887092,942781379,87310512,202693562,838774984,856738955,571484369,546017464,510953594,74659766,562869848,914427437,216850704,784366563,656377082,852316912,604452371,910117028,623884819,351253237,481196551,313267953,341431850,14842859,74139472,658322800,601576506,631340110,449212214,27727056,223296855,197084608,810496465,432798206,30860992,341026455,756709481,414983913,380094422,177089118,11209569,420385438,537532297,692591619,363116025,250871930,413806751,222771513,899278599,541858885,492978092,898072968,832837170,430299273,176528863,124724901,291920481,686251006,881750396,385167782,495514761,134001935,484006893,505132758,62658723,124470997,922346898,30128447,629430078,889416884,937520736,441999602,912221055,577559180,950533395,747813633,478104667,747518954,880850722,16901402,846903245,953114434,112683026,527062545,104115861,129729855,545892902,489515020,26826485,173282420,466164411,880673992,432148965,303838536,252295296,741815021,866240358,842618066,390470148,558027759,748532857,238397149,811562268,642698986,946316243,679757158,174250624,284918169,806974663,532892515,939018503,670689857,624912685,343818519,886361516,717828114,885901264,954206820,688550524,324366202,113432220,802526478,599225482,123076537,80371246,663031862,576347083,367656249,247052038,940838609,98764955,44445565,596821166,437729670,285421128,57569674,84498462,498502654,973824490,421726180,34032467,446009595,61390261,505988229,391004762,243945454,76971673,220421991,840151913,286127116,814556337,730712521,760964980,158684110,190230085,900585118,228267487,48017906,289215544,49232070,205164168,331008190,521484062,586547487,404252488,8551063,154988361,303667474,242397002,363648552,305603932,829687229,74400349,256885171,805821285,824739069,463611008,155296668,805945360,389161017,345343517,374693490,259814998,21527476,625833510,691653016,770643527,407556119,868244620,678283734,385539572,437400522,858336844,625696575,570364418,720652536,694196237,134022915,564313417,743811139,781220088,370672284,838273554,262962627,55553625,747174802,545223773,974402747,554908244,812410977,223040365,492566782,299546443,754328470,945567454,840909898,377639547,226892601,452776904,507885785,363514553,726327824,575958111,521322604,172219356,926020730,818256048,456936685,722056880,495505492,107262711,716572350,890381735,198613456,671773095,690872534,405776955,264199823,874437446,601305070,211515691,15872904,99618772,850325048,599055574,340548085,290718475,907885189,6248067,853071015,24776968,698108936,793071613,352075043,821304268,123928765,301529570,673482280,317786102,729414177,289271824,348539730,699953637,898793804,537433648,584167944,71361847,193640861,768596062,362921133,420687683,619794567,514471455,270393466,380170697,203563296,260896302,176200964,474644578,87448155,373108475,727755004,276660414,424870800,451388856,626790328,10074732,923776373,204045719,487531340,845107703,331437423,364392859,621626061,898115622,632630515,630466622,849562002,924232370,396311984,90357467,966478088,553321089,741713568,679578381,945700598,315456088,539603329,321526133,733115586,631048071,832938797,312097577,424049911,442682082,233555935,196918901,905945921,233319567,979355761,214786504,345631344,357843808,314064171,6329026,437115486,974331063,588946946,57997937,40073270,626812551,624127597,417115777,726064285,909628534,547694659,275183986,716709495,296297504,133449042,565233537,479190864,817804605,722063904,931177239,292307218,790110272,726363623,88759786,256022433,655495380,790894818,830840087,533891778,408355945,351907531,740081592,244113642,657217386,627883237,803774432,220517987,956653986,51736929,472718897,772294525,747391226,989873919,627719839,434751639,628865153,279257838,496329918,268041564,501682156,80459880,517090458,592087465,874260202,36709675,889379248,15197439,697887445,709990980,657754102,874595099,712334972,647427761,420741006,582413689,743295184,934587716,739790122,695101337,402509918,980626034,497784190,918160194,824462852,585190647,289065187,142056198,88626151,101327349,417507122,191337451,337088638,315237456,456960641,366865942,815851347,462850019,263910176,407345786,310841061,734891680,704688822,957552508,479297853,80477894,770282125,267290347,899230997,983909888,579397769,639179426,536612490,745950740,472025686,268719258,992040668,506013679,767870258,271507095,480708511,974271096,481057006,977497514,661021612,575739641,557666312,150377090,681718910,102754886,797662945,227291247,131436877,745170568,761066934,404146982,123426359},{1000000002,999999839,999996656,999946723,999256992,990486609,885210924,673633802,168151042,328427170,317146504,739882578,868040050,243446132,275241356,176530912,896590230,293673689,301058877,807003587,937998745,238281307,270558548,253600985,424658724,718995175,396164767,64877366,373393763,598859623,283419375,867195259,555086447,737428190,245908856,516973815,114855360,770053102,42926963,161013688,572251320,932087716,283581164,322969979,443588787,589137405,874605146,397878437,601100559,367400630,168405138,652260924,77757970,774458619,423957834,402523986,190269751,559163926,389283535,445886454,738024402,745131579,697069866,265608222,709606283,930786608,392906479,58829448,226826338,485439839,78109172,482405434,757685012,33513783,834417602,16186952,873687121,847299885,879529044,698065538,121940326,290249933,132065208,715960932,426269470,326516493,522099123,599995413,281239295,561383707,555847937,849287374,339465140,444470799,711629844,599477999,35679318,181567406,761491929,875519790,433094803,671404463,495196943,313029000,538872825,818412842,807983956,532295067,860981288,964682812,576342825,971423529,711111812,918783711,620148895,674931719,671682494,721664630,318792806,45098726,822710007,502236095,587083672,910369813,749973875,643234904,570054506,625084560,162906376,431308035,742520775,893955466,224025999,113413272,94597347,968080198,930668570,370370416,236561512,280388840,260121546,339881310,240507773,998386375,107166887,989844974,228098964,77120766,58414916,842241832,536979041,242227383,705896222,57667905,990943796,13271900,976122324,956459120,515921407,823485271,674454715,119388203,256254502,89076342,110654978,643612374,132250616,655137630,47752042,66857773,469144979,444491111,774642525,715686389,834620933,801462961,844026240,277176685,712362258,287679183,154563116,510738198,4500647,704101098,675519546,427193957,78189552,796936303,546247133,145731424,482877688,873115699,131381748,596704940,213523173,908442589,390821855,716095414,385359895,305332616,750757416,570839888,340132195,300428256,524325694,867867899,355230218,598881206,375501311,371526215,379099359,374649877,181076330,54582659,460241040,25398584,372588135,203102137,471749101,516749666,171947431,1954062,565331132,611811636,278695472,162809317,691673291,707513678,688147234,355282677,829785637,237894071,796081339,288081338,361033719,756329016,259113494,696427743,21763170,48890474,958390738,606400383,39332137,91808913,610027252,551184154,141471298,900333155,853667391,662608551,805069106,512266269,177401798,795500057,393885174,342719645,92095927,734379546,189352386,886172647,265696949,400762434,279522376,555689263,235859619,758658885,180273952,392988801,975630915,676437130,406653274,753954233,104742526,12526986,153981662,469488949,562975461,386729431,640471212,561727860,198348066,958184084,332257388,777981509,290825016,365245220,910243150,555300725,296757051,699933349,347358283,485582684,312812026,4519170,542821112,874577491,13849576,939460604,979118308,415560983,923814404,670797488,986999580,4106450,178557201,97199552,961680475,1357110,838996829,90940897,344478041,407370404,312693888,914734020,524361336,660053316,896714403,558853388,107556338,197597514,754166562,473282029,17654441,635724672,942460171,147860323,825945582,958574169,263281453,290738654,737218092,208479803,737252314,497671585,454858203,12030585,653210037,119239043,373889037,602405195,65762639,625053604,547824947,203262736,600072316,998280244,784829776,723429119,12427149,286202318,388683832,236148924,198242674,353698036,936866027,876072407,433262118,589620591,605795151,961269223,78520344,216908587,830122507,285302549,63277218,648288982,229870090,477443783,373772418,559950011,569858258,495829212,755122720,895807425,339449543,541097161,611703375,961437787,632477275,145003620,448750653,914635187,85160556,449756189,394790958,975108426,231444758,671863128,836674381,284036357,405585028,438721847,191576895,720679849,734721937,647402413,897222613,513691130,747723127,953757926,13940121,257088697,263025723,493952595,163749680,365228804,608949724,165352331,577596917,284583793,917841208,61726419,439575380,873421188,844984788,439518308,676319216,16349929,899180141,843381051,99296397,651083192,447905834,68475308,690553404,116903064,153192368,262121231,121471199,700169505,90223133,791923874,424254925,520048885,998696176,216398653,725842303,927080809,702740843,868150197,766211526,215195420,582837796,885786242,615311934,973600263,996889712,438613823,183637015,439012329,172617779,490109193,194060162,30950761,987552184,606749282,299453032,641216498,643345787,86174560,272580235,108946641,886945649,278451419,549918064,572753861,126705250,914026641,619833268,17593485,979182050,465149904,746040062,197507597,998934458,235016390,342972606,19745626,185877223,924244417,439391535,479489355,471675542,131320592,211686779,436747110,496271693,477556737,125155675,634087300,379099741,575275527,638123386,804042538,604715131,545383243,354762035,468148985,260963871,90211122,690501376,119373478,813693063,755998910,546521444,352568729,104259532,646641811,547276832,219569857,760852105,723867515,340588263,596354462,741482362,587622094,420154066,137985969,76223940,152471646,146339209,734359517,641856278,207585195,639416981,119042689,944948691,829532228,263700825,533961947,867558973,308651974,306820038,112018577,361991055,336226575,63482028,402695994,980750766,459844542,514688967,639241186,724382924,600129171,402413169,153085230,341552700,944930520,758338994,234923534,832514216,941264795,144787568,571643402,54228526,837248864,805168418,480596460,685504048,18352555,733916722,244471415,597128257,850139615,707079594,334874946,993883230,334643645,478893892,956899902,743253841,208068951,595529493,687669286,823569280,76555891,348555294,689991104,631818842,141899005,312955329,991306237,825629926,312645744,270625871,331846207,589218895,901731419,868580677,222759795,856281201,411644463,898401355,222347537,314241069,778568428,795457078,568098505,520756146,296914788,590228114,238996609,879455900,421694920,577839274,166034816,458799304,976058592,375486002,573996277,409403576,333468791,867405606,977317934,566515129,545593152,154429283,297207788,573704870,644738562,281651668,474473336,743042041,200687921,587157626,78545002,118325571,387658229,76860003,70103269,474216513,497813130,573247100,716714679,274033295,435817453,908218167,294133381,390126212,406578898,518993975,414207489,763990060,778877249,833079492,776114121,761340457,614891959,106909826,9837044,813459266,344201174,608515639,121495704,629788748,902476119,196617779,83944391,125459581,80677426,686064072,181212985,191929887,685942686,449578912,438112107,220590937,909910202,414951558,61766653,386435217,162744185,693955114,802448989,878931667,422280898,942142632,667806872,653667535,786550550,971582791,822045864,182602032,524244537,699970559,578211087,529487250,149871754,94568493,108983702,787719029,392107300,973410222,72064922,146168146,878068236,990880180,414226014,75298671,458787010,540501188,358810583,67374393,43816955,381618590,911848438,247856495,458030546,545056981,888196716,285661117,546810508,501780348,288233414,14208509,309936436,681659931,406117463,381782046,705773816,141638281,421915931,417504936,744992251,477941932,649742314,366465430,93715028,782674597,350585336,328363129,94305312,631692542,232277443,551254646,348197643,872065223,33405198,423262595,425532291,493330180,173265503,116540115,306049404,525778246,659852772,921594634,392974796,269828451,800147893,556745398,790342610,589860779,112567188,219241572,813419213,733915500,110737201,4012986,811998690,827097032,923482932,260101490,180245346,143423613,472155868,717662675,111676755,872238216,845356226,539134447,535936961,661289193,84794457,560357633,114065172,806493149,696612088,664358705,254300087,923989638,416892312,820602397,366646024,138165836,88013768,697899831,908697323,437164002,282330678,302274777,389570940,466081117,343341499,750216584,553827239,855517934,668272362,167057426,286139067,248747613,139620595,159920753,283327501,686127681,80680268,307400972,284448014,882834944,434475922,410371737,659495467,218235375,799744195,242867821,363587480,185689718,207898542,975433329,375181046,599205422,974240242,814023377,134537770,839884656,684984977,992265742,703129852,800618835,877540733,483402059,118999104,127186061,70394996,70920554,652171066,891372068,603199299,981275514,579077821,217354211,491924531,739480873,378992530,702465928,343649030,486444136,996512132,82281505,784864085,187327819,491472339,971701873,289920653,922368886,730363091,700685296,711801964,377261988,999718423,785592301,113892878,936120918,182601980,499699943,873429930,867324482,594964300,436467366,897022190,954299182,50816767,948597733,35294750,912707614,916921894,718691519,150503885,253707211,243638669,649055774,793190356,325971153,871050289,158991823,30749159,568260463,316047559,267354932,946802940,823094679,326613796,469268423,309760058,751272593,331881857,104161518,122087654,745955155,184871256,93844921,456286062,142227694,246844035,466631016,251971674,569530215,923040092,986861077,522226673,981492882,345787279,289457856,486212258,705791926,581796803,467465319,538238247,711876280,420925172,216797960,2702699,563933626,229102171,516658724,1857268,322791871,503349769,139674429,301276663,263331295,956724302,568428289,226984153,4930957,716748594,741368804,238673526,330784683,484000695,322634985,784404284,355821157,10491292,816518987,163651027,144200906,202972326,268471712,739294735,401947084,380122634,504945807,915922778,443537854,650571192,479264909,237731919,934769255,313939351,753750468,102667419,258788320,522938938,632932580,823395186,298083617,325929963,467160034,605913331,986690919,182677496,511296330,93323405,975303563,661739335,712457270,125562874,753952181,707476512,192419195,587470234,950169257,209601496,344586960,62407870,450582346,601820526,138946701,49799448,152945198,871299067,290672120,82679894,966387908,608412682,929137648,287352488,400861112,414445546,244774055,132173382,7294329,687520670,411404371,406187167,40537500,194101657,916248189,648220859,78469568,595046125,274058882,439689755,721001199,923653156,262185293,925683885,82363193,182654988,483918023,128895525,608958257,1351465,14164260,802837477,402373724,119135187,65853958,419605433,774604189,584459847,974694334,43177416,998492727,226837152,127070539,989396412,317198445,610000192,680192799,399687352,185830259,154769151,613295995,426015881,463493332,698099995,441627507,908054721,944342433,534912099,427483885,315293189,387242014,242148643,474785846,100419347,258717140,516509487,101500626,679686073,616016791,577474386,401854059,383502385,556385312,79256330,95458135,814121184,515315676,337244547,828339279,103340507,512332824,211327279,256963428,346335601,177298938,968586132,482944592,690972066,243179838,860055351,692867758,806023136,300965065,89008095,434204806,102958199,323634465,546466938,970684105,602171420,299587261,241716123,728226339,251867719,568346336,394450785,85328939,483792770,343357969,185966459,811765155,463475391,782381599,929522521,898904100,109049361,413156429,26095174,383616730,959092967,802433990,882882351,249988150,872211091,902275555,884326062,210108965,209643520,635396139,140362753,672023823,985481601,935830485,78429024,953109326,36476980,395475860,274966932,380984979,611069172,655695481,583590066,896370697,698361680,866466946,653167105,104126126,393355980,145821506,924749607,845418543,937995395,549986455,741678967,708956119,584794004,585407381,940654436,764153408,164077495,588278532,457673064,527123363,720568705,116318964,346062836,902018254,737583547,464427062,266921073,946354842,236771015,916707804,393020649,398271478,791026331,52804173,553489455,94018145,875473850,681123541,51034551,996841866,945496763,5181921,867324169,85535093,817992504,547683508,803694612,969744466,254527755,591048525,646615473,133369996,102240335,992194020,689975615,493778653,303705458,707266507,86001971,694224040,328152245,676217068,324444082,380253232,748250867,177910989,639794711,964511295,123615742,43079071,420279688,911981552,112865441,893611776,141371695,904649874,157081867,39966602,401243816,709237231,838070030,885522197,766328819,444176583,477935807,114081226,510217737,32766574,432157074,963201822,739666617,251114007,642721020,583983082,355467439,721048873,979040213,35220824,793943371,338170789,968240414,814194868,577928999,871712762,911200711,551990490,432945524,287940073,674876068,505513514,160070340,671986091,974204013,769066293,593595964,945085128,538644789,112570490,839557242,901958169,5645326,585036182,365701056,41898233,375925626,235100538,733636130,57600997,396021010,117088338,860200390,53739322,645986395,52021906,30511886,514259594,97045281,391828666,877781450,323288816,492958266,268570731,341480223,762943154,69773433,608698734,782718838,252831752,16635509,326191861,940853080,117509342,274144928,662404527,648772348,117109864,370371065,783466696,618348661,809749365,627294768,540989545,62139224,593699613,890903541,225937576,417608915,427428193,290614828,139670315,684919994,858124085,835587777,673026468,614234032,914730352,67789191,614681102,697948041,362239145,661517296,773372778,391289121,398498350,615754124,549964104,336682459,770493132,474584163,510176492,82701815,770698985,625055134,533511322,304791685,745723832,309547899,726993662,252575034,228052150,454152520,73609025,301759785,46532505,946028970,258593416,892611040,756114756,54134412,367380785,271979181,88336401,346291875,763492036,818235059,35762454,181260555,411640215,22991090,295103337,959115369,168372274,996684426,983879650,269873489,580417889,641681403,478145565,261062470,484550353,282868911,679828900,413114123,605406346,201093853,206428136,902860112,353465840,401884015,807862736,971951421,773264640,634023897,515891678,834657853,299292088,140811057,747041641,623573984,257873665,665489617,645119967,475025096,575280410,816297465,873608313,92366415,638774895,285410617,232680847,534662696,61475594,833271065,995014005,465052739,102419605,837987070,941943302,65388762,187838477,127750570,1056359,919518554,439215727,254227619,245007124,174337811,114073140,886872295,108313039,339407829,108846318,284868095,66495959,124598940,807578663,52167347,431840534,645939797,455137813,993198818,367597733,113182305,690965121,640494593,688668661,72413903,650488802,528758163,930477846,675301965,640337430,623755864,889433199,28245136,254546154,875299074,699649073,424746863,457490874,381447753,725315879,328108567,519619791,514222252,617382640,309900555,745830091,140268100,909291607,906416783,373017289,249349087,689623046,900015155,792839538,694221400,960229954,269846598,598278900,209484454,416593453,283794246,485940252,726674077,51117668,969311323,679872258,835167106,760637393,523899501,652250950,380025153,247749446,602773250,398518068,167842799,957821803,943675269,171411321,732986403,355927526,659438076,993213374,44270413,594969025,501852008,92891510,255118785,136304417,74268090,513014238,272504817,494210308,621045908,828682197,942454422,810423980,265653299,709730108,751568088,658557022,121992681,641282866,835818952,51683119,430666832,77182975,243392998,906030376,402026759,808950986,264979687,885045255,147427674,718905609,618546807,939769264,896408758,617826008,379479300,408562843,105126226,698359570,95714903,209485323,230125860,904479772,414555916,982466385,812273473,654810812,832392645,39148758,625679794,432801213,957643688,741437241,994906702,556576230,85511782,844645242,345112187,515540352,516419152,312882334,798463608,805533630,523931127,165073192,414397364,573238963,274990581,148029657,561098298,582528164,482290405,164097246,327390450,441458023,985557982,321961271,646566709,424102456,18281079,187446782,494485687,145542685,755170211,707812396,400425541,476087070,904398032,772748548,853294042,393537044,592465201,945661592,213789898,340660277,961127286,572682937,324038999,54625422,340953459,599567056,933194711,103804903,326341443,649163821,595326462,70252688,406231640,652273012,324214668,641870944,571994913,507971819,68714303,9339149,697839940,133531948,477942455,774518288,590313810,956998507,437043971,29932545,989905517,396039582,817837165,294212999,603566375,307720269,474674239,231870668,262813460,766008814,942746666,943245319,126295814,600784606,98597033,340937718,28555167,51694838,824285301,460463372,118847182,276324641,815476936,375150475,90995868,244851764,267834542,260911993,118548963,36824525,956356573,506289132,268333098,720146604,416259655,718802323,829780961,817382887,899394801,248929901,491900934,987952441,873551830,80717265,361823505,403345095,864682512,986400852,166259770,551385855,368696555,117696540,584172868,745764722,940437680,703212205,419968687,101565242,626528131,553867968,612866399,701751108,712257741,621329790,832865148,562459050,54062981,146171435,599282970,815939202,313424661,30671938,450767976,732080009,771944031,527602581,52068455,153142890,888690990,300241081,911084821,354105940,823265253,711560175,147177600,491966203,432815749,927431900,695691489,742771532,95785852,261469057,963540469,636210034,486100224,385609760,672513288,471971191,17727422,212416630,104988547,269262622,850641546,631057332,253793167,696464859,608119112,354418403,234304839,939693396,151162162,412137193,720699580,744764440,398162847,912802767,755319636,528702459,447484808,257876628,904734669,884561127,974015888,737678925,290208872,848376166,254220347,578916854,210516462,74251861,229645737,645717745,216855978,789812507,553477541,279185745,613611502,598993021,718082068,533611127,265160461,838279641,44981145,166307156,940505314,987387362,168105232,84741817,181233239,170295469,437013406,576135240,754537641,102221364,565533869,939527668,451576679,385511140,763868572,630789647,134496743,129336786,981380794,382853865,893075061,401153458,93019984,722312535,443185325,882578922,411798101,626990124,760121896,645681090,419777484,146607999,226154533,178153518,586980184,712980275,548572623,393374723,306314376,86927786,334948939,693274255,854484487,203476289,927800014,335298658,962795497,662746687,747317480,675915307,25410583,50824274,904354129,617841821,517271883,482392425,513675396,903493963,726888517,709094488,155547193,45614736,215658132,820168848,117157899,692761410,868468744,809819288,551613317,919097481,833021599,532734558,125928320,13285333,663798972,464657375,605886083,39459073,867370601,111992682,18588423,572763352,973454557,886111161,366991218,604646461,636678949,88820660,93767312,995334691,79887870,381752732,779720683,676353469,721356998,218240936,799128986,155147941,269411698,307405187,565153935,905065400,65144727,88334455,441933586,6203129,908324822,392891339,451561781,601076394,85309167,113090665,386309811,755661171,119134399,498179826,997048690,268277205,620004266,929999461,403798877,524507504,984581590,641519204,916955850,976772776,828963255,689912631,223168599,579658577,266556499,192381606,309792005,308730100,532700458,999875575,883463585,419961383,196997493,394366021,224151163,920482120,273422048,832382334,978592964,86206182,866721968,10824058,36703905,528594986,775007425,65915043,125879041,709177303,683843564,54250203,164199599,676901946,238215066,21208737,133306335,453470234,764090573,235970932,777479968,79579151,401572661,467172246,656135294,785737568,339250147,668120882,178592662,683894782,933573133,690067623,464399574,891452851,834486020,116154818,614062873,121067319,33012678,563954124,62790722,782058504,595137901,297491497,220449471,506397648,397406622,388237985,453043230,798817460,488457871,894753832,378599349,224790527,726396409,433096510,307609114,31800854,684238399,7574973,593863001,96747102,875647269,40699166,255983343,107293169,643992122,170285421,682381912,246626279,305753502,260745280,85581036,994453431,896680563,619148638,462626772,80018004,607498510,392841500,95393733,462071267,921893884,139493760,431281983,118643170,270505646,608316090,977106844,314572372,838962969,903999629,823620811,404584643,794093658} };

mint solve(int N, int M) {
	if (M == 0) return 1;

	vvm bin(4001, vm(4001));
	bin[0][0] = 1;
	repi(i, 1, 4000) repi(j, 0, i) {
		if (j > 0) bin[i][j] += bin[i - 1][j - 1];
		if (j < i) bin[i][j] += bin[i - 1][j];
	}

	if (N % 2 == 0) {
		int n = N - 2;

		vm seq(n + 1);
		repi(i, 0, n) {
			repi(j, 0, min(i, n - i)) {
				seq[i] += bin[n + 1][j];
			}
		}

		seq.resize(M + 1);
		rep(hoge, N) {
			repi(i, 1, M) seq[i] += seq[i - 1];
		}

		return seq[M];
	}
	else {
		int n = N / 2;
		int m = N - 1;

		vvm dp(n + 10, vm(m + 10));
		repi(i, 1, n) dp[i][2 * i] = ume[0][i - 1];
		repi(i, 1, n) dp[i][2 * i - 1] = ume[1][i - 1];
		repi(i, 2, n) dp[i][2 * i - 2] = ume[2][i - 2];
	
		repi(i, 1, n) dp[i][1] = 1;
		repi(i, 1, n) dp[i][2] = -(2 * i + 1);
		repi(i, 1, n - 1) dp[i + 1][3] = 4 + 11 * i + 6LL * i * i;
		repi(i, 1, n - 1) dp[i + 1][4] = (6 - 23 * i - 60LL * i * i - 28LL * i * i * i) / 3;
	
		auto dpsub = [&](const mint& x, const mint& y) { return dp[x.val()][y.val()]; };
		auto Power = [&](const mint& x, int n) { mint res = 1; rep(hoge, n) res *= x; return res; };

		repi(i, 4, n) repi(j, 5, 2 * i - 3) {
			mint nn1 = i;
			mint nn2 = j;

			dp[i][j] = -((2 * (350290987 * Power(nn1, 2) + nn1 * (-653275931 + 7133822 * nn2) + 4 * (-2 + nn2) * (-124554137 + 39715086 * nn2)) *
				dpsub(-1 + nn1, -4 + nn2) + (3307019976 + 252667810 * Power(nn1, 2) + 2 * nn1 * (-57538676 + 30007085 * nn2) +
					nn2 * (-2558567122 + 489830359 * nn2)) * dpsub(-1 + nn1, -3 + nn2) + 754582979 * dpsub(-1 + nn1, -2 + nn2) -
				2336968574 * nn1 * dpsub(-1 + nn1, -2 + nn2) + 826915879 * Power(nn1, 2) * dpsub(-1 + nn1, -2 + nn2) +
				3537671 * nn2 * dpsub(-1 + nn1, -2 + nn2) + 383835743 * nn1 * nn2 * dpsub(-1 + nn1, -2 + nn2) +
				39733361 * Power(nn2, 2) * dpsub(-1 + nn1, -2 + nn2) + 1202146003 * dpsub(-1 + nn1, -1 + nn2) -
				642575198 * nn1 * dpsub(-1 + nn1, -1 + nn2) + 217943917 * Power(nn1, 2) * dpsub(-1 + nn1, -1 + nn2) -
				2083004407 * nn2 * dpsub(-1 + nn1, -1 + nn2) + 457230820 * nn1 * nn2 * dpsub(-1 + nn1, -1 + nn2) +
				880858404 * Power(nn2, 2) * dpsub(-1 + nn1, -1 + nn2) + 1000000007 * dpsub(-1 + nn1, nn2) -
				973530593 * nn1 * dpsub(-1 + nn1, nn2) + 708777973 * Power(nn1, 2) * dpsub(-1 + nn1, nn2) -
				13234707 * nn2 * dpsub(-1 + nn1, nn2) + 119141603 * nn1 * nn2 * dpsub(-1 + nn1, nn2) +
				13234707 * Power(nn2, 2) * dpsub(-1 + nn1, nn2) +
				(218947614 + 782056090 * Power(nn1, 2) + 2755 * nn2 * (-248946 + 286093 * nn2) + nn1 * (828923273 + 151741142 * nn2)) *
				dpsub(nn1, -1 + nn2)) /
				(466898616 + 291222034 * Power(nn1, 2) + nn2 * (506631977 + 26469414 * nn2) + 10 * nn1 * (26475262 + 58963637 * nn2)));
		}

		vm seq(N);
		repi(i, 0, N - 1) seq[i] = bin[N - 1][i];
		repi(i, 1, N - 1) seq[i] += seq[i - 1];
	
		seq.resize(M + 1);
		repi(i, 0, m - 1) {
			if (N + i > M) break;
			seq[N + i] = dp[n][m - i];
		}

		rep(hoge, N) {
			repi(i, 1, M) seq[i] += seq[i - 1];
		}

		return seq[M];
	}
}


int main() {	
	int n, m;
	cin >> n >> m;

	EXIT(solve(n, m).val());
}
yukicoder

結果

ソースコード
