题意
给出一个递推式：
g(i)=0 (0≤i≤m)g(i)=i−1+i2j=0∑i−1g(j) (i>m)
给出 n,m ，求 g(n)
题解
g(n)=n−1+n2j=0∑n−1g(j)n⋅g(n)=n(n−1)+2j=0∑n−1g(j)同理：(n−1)⋅g(n−1)=(n−1)(n−2)+2j=0∑n−2g(j)相减得：n⋅g(n)=(n+1)⋅g(n−1)+2(n−1)两边同时除以 n(n+1)得：n+1g(n)=ng(n−1)+n(n+1)2(n−1)
令f(n)=n+1g(n)得：f(n)=f(n−1)+n(n+1)2(n−1)f(n)=f(m+1)+i=m+2∑ni(i+1)2(i−1)其中：f(m+1)=m+2m
i=m+2∑ni(i+1)2(i−1)可以由1∑n−1∑m+1求得
由于n,m最大为 109，分段打表即可
代码
#include<bits/stdc++.h>
#define N 100010
#define INF 0x3f3f3f3f
#define eps 1e-6
#define pi 3.141592653589793
#define mod 1000000007
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
LL a[5001]={0,143652562,619287034,394459081,453653146,323687978,611144187,109184994,558177943,514264340,168945990,159295507,145821786,381506427,539116349,591624843,652131332,287774949,19989848,36779702,950877767,116516658,208606586,180201121,452811293,475356450,652391504,903728581,742387842,857011466,479159364,161751710,584110738,339366006,286689047,49229745,389006451,436343728,228338202,178821580,23442289,69704095,156673404,115646637,959115449,855192577,951148747,845535887,201066424,63081866,444909953,31839190,265941388,569790196,563236229,568103325,220014577,834514328,562412726,894248225,829877272,282891462,668469326,931036760,669196038,407764534,112413586,186385663,114787850,115371545,333099126,384167579,675319805,149930790,286087513,712009163,951657770,225666081,55190851,936590919,249599666,419077802,770395613,253435930,553012350,839890558,191035816,793570355,335677301,716499799,62573145,479320652,168477640,496017701,680357685,27771070,11092558,609355696,605551651,379020305,129724558,953532884,343765319,872891239,36722031,811098873,695106708,421290594,628551364,221788164,22265474,435924048,574021513,738717279,571941372,662659334,817264480,900943266,752169031,488734861,703726937,514934256,682435953,767914853,341641483,739149726,553018448,116208143,548511947,350386000,512859250,974543806,231726392,412165273,263712531,644696978,325339337,77847629,87926310,799973410,110449055,564528987,21123396,467131398,244177609,367081003,982871584,145325040,55191839,773697747,762570980,297506910,528866852,161070417,322650336,890761900,259277933,659112339,925369179,752645229,625699180,732921095,79036212,695424149,356222889,496249507,803648715,633931396,258568877,360595569,380774515,697722902,449275272,997029591,862559032,163489376,423458533,546170299,985880816,163515192,135163598,668763138,124786469,253374363,115025530,642840140,88059282,817872312,966411796,971693461,28101551,594140024,587984829,438206550,756355838,970859258,64104762,101698306,308430461,185116722,330296556,262052836,444094095,597531441,514696990,794262822,327042573,942590934,142123345,773644186,996898411,243308553,717553228,11804233,695342517,824305474,944704316,900378874,950234303,949262559,557785078,175271570,643065201,487205678,76512883,318116692,98044624,194419369,309838738,182838974,651595057,709022164,68015384,935215949,714035299,180499057,709582298,122529959,244779072,683879128,264662091,748092492,808754818,716339984,553135368,311084625,258051071,211130101,299661927,114061695,907099558,982037905,182724340,274509235,284778615,128872021,602957287,898166882,741398344,969744027,342506520,544672709,893469377,483503534,757449214,25428489,113177604,306308320,90702065,450965489,644594154,905383701,150367213,768462394,201826030,691983355,560042630,159861924,768621945,293788315,194253720,420128722,546416185,117877731,85443751,476594736,899124685,10521026,452128995,440850791,414340934,518128642,222838999,780589989,671297391,196994940,102837352,18014849,394216622,817756390,276987145,436957731,832668349,210681125,420295003,197226925,459174426,994927025,627292959,42444779,146143694,684209926,907601920,469563325,386973260,981051849,58015346,1357239,435584124,711943167,398548742,494252275,549871329,127089821,603475585,646036193,679702006,41331815,324314399,242393979,667488843,464449074,278752145,781267661,567513953,127786895,36443375,831519259,227225225,182963491,631830750,893598809,786591319,764242170,445506690,812196464,73295415,967763882,6536916,346312677,960969607,115422352,566483831,647293509,32919809,157126804,719617876,339827907,604536887,376751714,266665075,990019991,915367405,329155551,802093622,49255682,480750887,337118449,301017391,782460896,60048132,492231884,674259801,609462440,671486853,154629271,6249502,218143660,18185568,761815141,186280023,13866792,599896750,448390272,686625741,930176477,332216527,738266274,282380685,842755369,964252705,839750420,166542770,189331796,808719692,801453482,78934827,871039250,905634468,938677402,797720693,743771918,739194081,922669893,610229080,839069856,531009876,387322726,951012470,590540711,226737726,851455816,90221387,829719225,504662628,862052605,726684431,259826695,546762048,860326865,221978852,564079334,781525130,974814806,697161205,604258995,318873557,145078502,280661670,278227372,938949761,666340635,33491682,487052372,907574303,470650002,822787102,278185923,922299354,824740043,316572818,413734254,43187613,586310588,277352059,804715020,88676038,643547259,325833565,335501479,344283537,663673342,901793043,129462848,512237694,51024409,279171828,887123392,165185156,65184179,295984323,167063988,937902648,165751304,201129225,408552111,260678276,6379586,268996447,77641459,627692870,751435631,583564667,981512131,34796318,96595596,969384155,537620790,775445331,740401875,704256642,964280551,883336057,197429424,355078700,658514989,930380537,463608054,786312060,760202636,796515535,188202810,683637978,128118335,28453889,554622652,217639160,32257279,391528342,672847756,128908212,521386476,655144945,547825679,512085630,696858754,24490899,606726069,703686706,853144973,296811331,335794341,196382021,935492947,847255179,570319344,982232999,155962203,270761921,108732134,334733625,525333596,954912960,215941764,958084921,417451776,715111296,610070254,357094967,488209365,993683074,148840709,468080708,167261384,302114207,789436905,915380009,250889050,690028170,630216127,650141205,660523963,939112363,600866167,295106953,439046600,952521279,116063973,430483664,378245130,54691593,88723101,150900545,814927320,150161869,559151197,568585432,719012648,651347836,221830277,88152105,425206041,495897943,847338854,709284612,741172353,948499925,370208786,793029263,925332167,767767639,584312480,59384072,906739064,410132650,783559922,489468140,924840170,251328047,400693892,851896400,331868950,554614470,100163693,825740674,263200651,245848111,971056883,341707097,927012472,911132795,4008244,559651437,132016403,457799477,981384671,876263028,855648999,598022370,13319448,334806296,775979271,960811339,4446183,705748254,359406560,20168966,235753263,445976735,289580976,471571705,783747532,809760214,960317603,182593088,758734992,404826715,821830608,390603273,531804369,335285604,284946362,41662237,950349940,806943907,126442132,109289301,169364636,441244401,689435837,488022892,827956002,5140302,488837270,73189226,100338349,262361686,199395433,473584560,41576568,251296360,647138893,433691413,198545966,902926972,826185958,982871386,969481329,671609043,348653822,606242224,319961691,304704308,256898303,180014871,351221054,990156377,911746879,750909939,699711473,640610510,10866070,94998875,403691403,130331266,870106508,48593537,205825246,324714359,222635011,393384746,300433684,778448790,198283956,408464934,145764738,580379304,853080384,313639537,652898684,592419867,161064152,339193845,601845599,736750801,191084137,43455306,457544105,319895591,920991316,653822507,796567972,577387919,697549033,634183620,209773811,709447990,314538831,176237513,695183701,381468586,540894186,58890692,243015938,951003465,905551596,268804506,184826900,334190640,42232374,774523612,6919069,897249492,154533428,994181215,547886795,490616934,428511475,477242306,106702388,711784894,820728886,119547796,794575729,323108020,120262375,426431492,398136348,750783189,193085812,862830596,319044760,547258897,211934564,480515970,815772978,387286616,162774033,5068628,932555324,390121210,435880930,697079671,989674747,497891604,690556729,145680958,735137618,91537085,544975752,349352362,34766387,549576166,761637432,858376676,238816222,316405075,5056990,103805979,224700158,483143092,640772125,287611251,6501061,469767908,907469842,234879937,217137122,708440759,187181483,140032986,267728271,13250806,29323087,113904817,904536623,488499498,747001645,934633351,346952108,558678361,753168726,285930831,414272476,647033023,880186833,858050104,590030655,442642962,727824273,645374964,677543167,854085659,341142758,775043179,511009836,124435349,305073649,789698330,545737254,45021387,760585305,215727615,264191762,751292408,798054347,921678565,189232785,819433626,942241155,140760131,575809822,141253407,228221436,925011889,791871152,842711843,946919031,207959590,309101141,588329967,527351255,681099933,606686962,97976586,739370256,62397881,818531288,938348780,743162250,848118588,339105343,297927768,566348556,975220383,303232043,628791496,541546480,757420465,168001029,815205076,138201557,891664585,664919587,18500963,209803738,790886545,202304764,188363905,721600029,505662737,407653521,366031477,831915696,273250140,10698088,44866220,964964589,959033633,846121577,630082366,926232467,498940409,133505092,527107674,881430331,866030050,192062141,266535204,966545692,247213650,108847344,756339442,323104054,622896130,973471141,794859053,87824846,939346250,778130682,86912554,574458527,118371103,174637690,466775026,15806489,463419936,984996057,18245753,90586816,834364075,965611784,814032327,133668698,888036209,916092619,110712679,677160891,867267873,424187713,495379805,296234596,467454809,957922598,329887151,240918208,425967782,452404603,732133004,924710893,72172008,668116179,908721427,6930173,704502809,162978154,413988968,11750203,406956228,987606191,881253753,416877136,688601129,786852314,777728582,744752057,154497274,581399560,589874560,619789264,929203120,459052182,137784573,911000060,138613510,905473015,211133733,264978422,934611817,569093067,47802096,722025877,314729927,920531202,561334755,632984835,86959331,233379681,37816318,681509589,913459858,73500047,690854543,891572156,239186958,149383348,741575703,77021583,67064543,711442126,31823743,331987178,82426719,733557181,269696166,370353114,140990561,135874968,430502230,468815898,1373327,751996803,586537760,101455360,666716920,832872097,681180627,313077529,439919526,425623327,287037107,592095937,887204929,759412082,278958035,562263165,3661653,712205766,439932514,340598184,184498193,404223608,406834962,161933992,526925021,830573801,794611129,581662127,241657780,520882333,394004504,613341175,12051183,788198069,117531731,62022917,584252300,214509569,722523714,987988665,533880845,135672464,142494138,295110835,345994243,28452023,82722843,510011710,409352869,437343850,456896166,500515415,704911939,569859315,281002636,259928431,316706362,159205062,27905688,348619068,8049339,775300181,871279882,519019760,209414355,416017753,803273865,71045740,277771501,642493689,178377007,466680891,816149092,828801205,851100128,43401195,17635311,483785872,453621292,802560185,991709498,385580439,770420796,418061312,148728032,776450187,127431439,581254977,908103519,353215817,924845683,24312539,615345592,911892395,126302075,202392504,919247983,264169555,1679213,386148880,403639119,936710082,392415299,264580773,603342952,488195719,60127574,12804622,226992308,844574606,761834068,641460841,534034733,42458058,847807345,838230499,437832270,55657965,594409597,362518420,20480542,206758443,832500858,987930827,272766064,786109553,23174978,447248021,896194725,984927805,579185829,747082521,112888414,173709456,953595658,155284461,696782302,938989251,315854059,407899889,301489922,715292292,449059993,201711893,59333051,245594167,630522196,540480873,360974031,314531458,136916253,815116429,414227009,418782642,341199840,173484508,443589589,105240387,559137516,965532499,313797354,962142745,211253939,826719649,288423158,707325269,553447969,864185477,324030254,231552064,19589600,39589011,212853665,316248094,263375271,818738961,755069044,67543328,800071861,891221058,498189249,565708168,709332408,304773319,290898104,190371515,729055289,970322473,291005820,469483704,477052263,648097875,170054544,729278190,717207035,179961164,470789119,72896818,339769382,391538569,324828960,933015781,85491291,205489372,987045576,952409990,714924823,733061003,514286530,685188535,441130533,117452352,44905857,42553126,811062831,135336631,824611329,21325019,370364042,716285791,860583118,669749057,808964458,722264256,999576860,17333551,488782956,259158711,733217240,68912199,395713909,941386677,21598190,215261636,282468937,83177690,360685301,616918939,358386541,828685343,465543575,57517952,99808143,390017570,922048522,306042455,85045852,825242885,24741132,661183642,872621210,394957902,117190255,213365355,873985680,805401925,604912475,792774170,501194499,427269762,904708937,825949439,684430620,291902176,492218798,173866086,671559366,668310770,827029851,229788961,142737042,742137673,633451862,443237046,834787566,886459680,510028127,504409047,278568902,84539147,394282208,706438689,927575963,797114722,618305732,281956854,275951334,591921032,411621527,382635225,870636666,293361860,552385052,373946596,557062237,964761129,118985165,214683215,24142344,373668310,114464416,72357478,748241005,390083953,366374735,628355837,814748845,913989332,953695262,668486537,99606078,281416953,774030551,494101075,876572491,940211099,586924103,348481422,113462698,392673090,704245553,450786009,517502650,755258353,783859550,74839163,369521725,337155144,846539632,945819988,204516236,964445498,780913103,41357526,534723928,911084034,624833821,972625629,452937933,349544902,71772675,248809319,334054017,738321924,873192276,703028358,106944420,458220571,212159785,906720198,643278054,181524992,989332325,71925339,357767922,372559176,426574715,995106693,509910804,249613050,319868275,640788900,694824746,593965916,382533232,337106364,201843362,680999406,124362764,946549901,585727317,712034013,275994943,379501995,190481137,335556010,991342710,289496819,732841204,354298416,141396514,234285971,988427924,23800737,111216112,266520980,452830900,592976745,293381036,888828489,849392903,984665181,379242584,276120121,214178212,418497333,981458641,139289083,763719863,845763504,89155085,631449752,559474687,996603897,890701761,71733715,271031779,995585418,25198256,312055888,54643822,456018714,237762082,412086949,628287621,512796977,904519282,757559846,649817170,205954572,596340342,920182172,20331995,755141073,307861732,208093236,344983913,883745054,647219901,117797471,655868225,264670307,434362029,998392688,199421600,79615225,117947897,287637280,852940713,102415262,22566376,490170662,619609028,833028614,957766035,266133591,550402320,88518986,378547177,840218774,659935898,929709548,534537306,649385551,597772613,435917640,651214808,225673670,294064737,519835882,439741313,232817530,735067203,755385366,472488837,278507429,693924523,965577643,791639612,712861328,302538667,122315616,770819669,294086955,807352543,481178455,237809605,327428133,378244563,273806447,270358929,975693069,818032868,973110212,351011943,978062939,309760104,302914585,60323184,183728486,269780974,1082688,886744448,681957667,797969899,148967664,373792146,670929187,906269932,413833546,279845960,756075731,153788466,590625129,144173214,234176724,33070824,724766366,768623719,632083266,643849496,729344876,774715908,818311423,582123763,821891000,913900515,463099438,168575909,271088343,737124338,198516361,427120616,719534659,365604776,120498847,565386130,968309317,68591578,305620343,349125204,921035780,143069942,513647243,722640899,904443983,624015097,43337979,340617575,68318134,271640271,53120817,591093685,229485237,244973184,282533320,565449864,900521186,246108444,855918688,687775285,817641449,874885441,794796458,786206109,616552021,556336370,511107240,192514914,196288389,790288654,623587472,772561958,171005855,4226320,49308517,380500518,758482796,492221915,969905024,947779145,79986028,859835283,992893951,90944758,822255703,492285042,309604535,559408936,202514103,556115859,938866138,371937881,160537613,144072661,416150708,422039052,893669565,598448959,199117751,210394741,328840001,262562469,141662910,705080338,594510767,917357228,39921655,740376176,115415437,735790373,885711255,989696933,910874647,842427000,706298780,60316035,759190743,650462745,711178859,548994907,330724996,643645235,940618250,473415715,365099906,307520328,982650135,102993356,958981723,571358221,200724434,442263454,841315034,762513870,719377018,922753472,915403780,945004944,325986152,317492459,858403730,957308111,54070668,287274892,145285647,224662481,39134732,414180042,838457229,346548660,752842534,820050970,218789803,303346536,708411103,752271889,205914998,624105380,80847306,21487368,269149596,113752736,7114455,187802426,121326536,764886663,156603821,373932097,862720347,239903152,568337793,86331412,605220514,162358922,793484728,477256103,178381651,709733557,998810380,177017291,787602970,995317699,443844878,897308669,824899230,677613531,713975239,721785002,575622125,995512278,716740076,349662870,309800113,369922980,839507722,91792403,790759938,439267716,426831453,68951685,12465273,724685735,162862620,171661407,495272661,759235355,763544885,867399196,403962646,586814280,286486038,639133541,552842569,980521959,888646730,200938668,191745065,159031208,122442510,534389158,552258787,841401804,490076116,694114852,971044198,751850065,678045644,660762538,253896142,632253007,527081049,928529500,856584242,192237239,874008787,421899076,91593901,832363813,762456915,18947751,567019911,792139871,485982848,941335113,605372341,695389448,728343499,662526543,670550459,426675949,313945700,294778653,82960218,139249893,425181158,728324193,242272881,360570505,77947422,769352060,517048712,95858951,30099544,972799419,286150572,528269233,676352490,368659915,510779483,46982056,874773066,175523468,685193659,304180253,448119495,413225468,268166015,953749798,438868671,850121493,209764122,11157160,610092694,177618917,504168398,369037632,839955562,797682884,481784436,216420143,24734126,126235130,872807308,372811798,32671454,674231427,735927468,781141213,530355315,586093888,825068400,875064952,243686328,345234661,691277096,398878603,362174386,33874607,411779893,747347284,685394867,499371346,76772665,398165161,941843388,944719344,297364640,203661701,653448502,137940301,82691481,759473104,614183188,405160303,328971722,909433996,172179120,333757192,412460059,48633687,520893814,171858152,316789560,861512402,906925019,163490125,196383885,795005682,630393313,882506594,311211586,677140455,857774536,907834582,908218471,293936277,176734338,540847443,147061977,18796135,235727540,615517611,931614897,511347415,113606795,465941565,660505761,597827402,334917395,171798367,462988561,523172257,241307048,703386529,452259691,569441737,273330019,919741509,996545101,737558860,499937403,614573683,178940766,975571213,684543122,505423131,266764383,623532260,51633789,818693903,921276962,360781377,575465138,856276289,156314580,501561303,997852641,7368942,990345569,57757691,704800088,797370956,511373783,481033965,995840195,66160269,959555105,163586937,19278986,185004884,692603222,339807341,841631022,599372002,303016844,201967441,121650306,25702356,699999865,788754947,689019425,586552789,955568298,681645156,974549783,458663245,385408093,163163984,878228482,889368401,328421290,304162860,471660051,165282533,892093962,55201868,428674880,414941465,643712701,123276937,665237744,137043720,854523938,907515711,453522502,762912349,743010769,907021199,377451447,297030786,212922161,537211271,523844764,503354353,545995417,545995812,798321552,567580440,719689441,531803136,619131285,459153823,714230580,18308528,965294946,623221012,506755536,793451552,448501940,792095692,139066287,701831527,506393786,984834396,241505689,348336481,327057982,10584036,836035138,127717440,945617568,143061791,473785599,373012994,51703553,506678569,262300506,438085506,251763265,223062458,804872608,543713528,119677709,763927584,628603095,605466921,676210769,795485799,607115762,680838593,539664725,423666671,389854770,516851918,846094552,717127777,612868492,987751829,628668444,357148884,211077992,334261727,461624394,731622734,14585784,952135795,633930924,443370534,137101048,334954148,354104964,456533460,504143553,243409565,245285574,398104085,301153603,374870182,342746000,412603637,852797142,188785250,133482093,15312384,699374381,902447219,645739488,381600826,68113416,418452858,922262003,536390283,129960238,254032122,392792530,507195320,378809017,516534298,156377731,421955627,830601311,322928341,774892636,910685772,710399220,474268706,342633727,216567361,320205148,910736757,147714585,584851511,538139845,826748357,261369473,785507191,454196011,479328746,42524308,194498509,444373718,249677792,558561330,735851606,768754060,654291888,137521361,769303593,994394003,34085007,628870711,992611804,898113979,145967273,307567036,369933632,251112029,229239979,49986729,744251561,739230688,530736040,328914953,587174122,332505161,48060235,401563839,555678853,522782273,171679354,861917024,366126276,564195928,413959000,392303567,547391298,475223917,63419652,911807182,746511146,519419120,633002318,746154113,493566181,578494028,215190300,337412068,181168423,3750579,447446803,571680222,375512217,2350642,138045509,809694168,647604541,389869478,216334139,822606238,971984469,277553055,759689035,198462926,967543848,320443251,351440846,519557494,102883372,810223165,596543298,771314976,223984301,505216705,88881298,255007795,389957223,92582493,345077757,317701781,105878071,607370087,473186321,854418896,803174804,443899898,333746101,61402514,163396620,863030845,878113432,132858847,319381057,310766437,901639040,21215594,245593752,71252860,248019533,304694213,368652640,885286460,529665277,932452749,31250355,81231810,47632673,959137838,14820614,2090771,144831116,785242331,202898543,28751328,453403804,605558561,200695383,989900282,441980459,408301523,245294151,465590816,965048641,900153690,28232339,503618590,190711502,79624458,447741711,626788080,915757766,999276233,613152409,247795250,140255354,433619454,663017409,169302348,870421401,55762755,697890665,802028153,58615890,885994774,664049990,403658300,412324582,78419632,575214175,162602783,897889013,489746507,174326329,685471283,299095982,210816494,41028150,940318677,760123658,313796181,107349740,679100231,72098227,712667400,812391836,754371197,529002543,859614187,305541848,924506276,869201136,255311776,417517,637079501,188463887,983511138,391637103,511124994,292309012,842224139,252837541,973427678,465234212,78333545,689206967,610786493,195779000,701995131,184970334,418737460,687994356,214136074,924605627,64993308,769772729,80485771,983227181,704248815,669681761,265697446,74240656,942421166,251952915,335831004,715178171,6260102,275036245,672715014,687182769,608458224,92915285,302076760,42041787,502919353,381379669,692116884,348650452,411296549,922604060,398259199,346639291,90490869,229386582,988101545,490129947,575970283,807030894,314442129,568226361,28789645,116972328,297173663,847594891,531286280,770127670,118265974,882584286,662920955,866239719,892701984,592662852,238619196,110784276,332425933,444783696,308663407,335703458,753366391,808173805,371491095,302023379,921223430,107061618,681449192,123164709,605551987,710724064,345008335,856288354,672934370,857906427,925177089,241767329,139372820,261697452,414080709,441041097,657262661,189531430,729048472,897643747,679396157,39711142,454876335,867112793,71627265,990606011,10702229,500497696,265587642,508222774,271116105,137693940,466799281,194241200,889867217,849863082,47649774,135087029,819218605,301136936,223581164,517824592,168142338,138583421,512986030,353100942,714942256,805471154,856438895,377333952,247799588,65169283,171324136,463025849,640195045,663033117,740162211,984774707,679925830,212338416,262591753,49993619,543829100,368971208,293636656,902138578,584303193,549654301,192420222,155270895,411936710,331107150,44220606,338358015,25043845,104058709,579397060,327778149,393347653,452400074,965087617,618593898,826619065,807422531,537002285,248211171,363757273,186164361,159036237,210618996,945755029,496504446,512850504,317469145,105194008,605317839,886250179,564431745,461323047,153385064,576122666,648459108,869826887,249846532,198461636,694670998,966346810,130974009,291904591,915989631,329650158,258140632,650144464,366375724,20182789,754920005,350274341,198544957,402427238,273862962,456011218,527330365,182760921,351060252,225193013,795983664,249661937,33002737,985773466,366869555,739279146,400385585,768906323,978968219,201124221,192311781,699542102,63099570,632704096,519859671,405383535,190398237,7961858,285587960,471080182,680857177,3007078,884737804,658987905,831190634,990314064,446713809,632310297,829943989,173658977,854564199,710404463,985799029,369667631,144950751,463022072,660291313,836494418,379593862,190234562,117849299,89518067,485655974,47308886,766708813,626810648,113037228,983284433,648721907,415288674,821284078,829995887,301963750,575708538,859485815,377018192,507108019,734215944,184611128,696025358,219466525,152624188,180365478,593753420,760508427,490554844,364671483,529165900,20750290,343902322,389676099,254565853,138726312,44257491,670621975,37888379,600672356,909374483,930334195,420913384,452263417,438172570,330447864,163360188,940236633,97256082,282097522,86816807,331464451,972373466,890242528,259604460,806344139,475378636,812933469,929353580,961729871,156817950,572579175,545650739,144736798,200462084,704506248,21578717,773965925,357173422,240912826,219499690,37749940,644008807,434952315,232338808,509611888,191430575,48852648,597520557,646559450,508602608,735828616,475295631,417552006,960162822,220747914,746110830,745499191,92697831,766400296,112867397,775304306,866994965,730209042,666451444,206643438,780565194,149515578,223383350,318054623,116079993,721934089,452618396,611371905,890665435,394224958,946621017,280418083,403023849,74661172,228672187,751566892,846613308,944561991,33645361,510438724,562973464,894947219,988105026,390734383,690019193,13441752,853059602,290905667,180630999,745764195,32085734,344834849,247604808,45121457,753396642,301155571,515510689,700242384,386412032,309400762,298323492,848202561,602784442,941036545,145728401,206072687,436189309,152772848,111119851,956159078,318981746,353676886,239671681,880919417,62607862,588881988,236539885,165137462,646391451,712646227,228571397,322496795,708566220,120187790,222565699,380324248,686385886,60927848,257305155,113481644,947983686,97138248,289278083,186264055,278931692,722512272,319792851,130902069,84413702,530293638,275770665,369783040,429592114,803144771,648276223,48250944,113380695,477304412,753591717,234673132,329552167,315222724,204406803,978158694,671215506,318368394,414405185,860678496,464356482,723636213,621256517,296813450,639944535,577056664,434456398,331579459,917152966,313154383,531275320,124646914,704890345,71098124,600135298,338151439,264215970,460452963,590430391,450690949,247990153,75256352,822435401,142155234,463020071,812071329,237129075,846528977,827002013,288330547,29852182,518989673,282044069,343392287,423016438,438212785,446445701,979231103,982256623,139224452,596913759,550953013,368795206,87433968,973525049,265014571,882801949,482592728,67390344,115552810,922121869,575776450,536474235,219949455,706503881,287609059,572172066,960985599,211835219,720654407,218226055,603695993,691013367,790262424,489105087,982506577,201597546,901406757,429793174,722396112,854523162,22701803,215591188,161220144,439047768,325307759,507308478,120753533,226838898,292536229,776873978,705095144,199368678,541016549,192709952,200087915,233040795,813959508,385918338,203580335,549738383,545811490,998361231,787999546,392498449,122248957,390480246,145985471,166735532,546742614,890176799,479574775,406873615,258543684,632901319,820141628,768406814,986859643,398521800,582328920,295811951,92240278,478017583,688373330,865747399,190545224,147134108,997280693,54525826,33240784,840335536,618381503,878072016,576290516,765750457,212769445,938905209,466257837,666044646,814460815,42263604,129421202,434387384,142659500,740086452,631662778,914070533,315519380,69737247,331322408,538056527,124864127,595020250,781176012,602826381,147860616,890284648,544121515,931537255,247576597,122917144,272651893,420600903,669688482,457073518,23786729,88654480,232607090,697472757,333189746,985180581,613195913,346426890,529137607,531887143,330169982,187405123,973126328,248077033,106708714,534508031,340418688,798127115,607639125,545552305,421818356,161454154,1059317,49900925,332076179,823721177,899397722,218771606,939328992,351673861,399979478,951282490,538630897,963500353,953395621,329185767,220579244,763723661,420890196,973967623,424911194,801926212,784416981,288834930,592778100,846794318,458141561,882134155,269700418,222775301,630029550,235605167,387651674,557885638,16409628,623163328,42342363,711291480,142046836,871056342,458329899,934895737,198442599,950147808,209961429,151823824,16297847,798812567,74242559,41396674,382693545,705295667,734259240,335384943,645802751,741327679,627691150,172847370,772713875,848980082,247333542,768097347,761012259,419652284,856566087,419252664,759865906,223717112,311201282,671831402,445323147,636218174,272714349,366013828,369179972,948122638,771003851,26337018,975986472,506071853,804569271,157847370,66477469,522110961,479467557,661407657,683006511,240681492,880552322,44287085,755928485,127853491,703334273,932513895,651919720,147496351,716345812,341347036,282609810,391934717,317091194,210314767,385194836,635741020,833559254,253115981,998866087,671377928,698930041,176943926,827463837,186630177,243290974,820573302,861391266,81050839,974215262,164695608,753484276,2318566,158778705,765223300,145659794,344171675,224021331,83332580,625275714,839189307,421012510,384366009,237653009,713385886,455294257,700507324,470669913,605678533,278279131,334730600,831926727,598503291,418745304,6250803,847306060,893272332,868694329,898757933,130198481,963918163,805494880,372643855,270739307,479851688,223674288,669851719,438965252,455296385,202715440,945036034,564368575,5233436,139282600,14488071,677368677,226806907,667012430,194929842,565167858,831915045,190650450,691156092,795633247,652217463,119293734,312505302,291201504,595946429,272997434,283354399,629146827,291014386,158249599,477840657,856731825,808463297,134667445,542557020,326022604,409614988,542658636,91687824,381096287,797822788,965710452,993785553,729381953,779471392,250004118,22936611,256551596,396773516,417130472,164745216,329431823,317486373,446781709,373412328,283777081,817387452,915163132,721769532,983650335,808260305,99712058,136277682,924781042,367079447,866948741,643916939,178136716,809140667,108973394,831887862,576647910,779819793,374001914,839084800,812549514,882440948,9125348,68531946,228816547,47108366,162483695,569638049,627530648,474071062,16232722,838702,312672906,969608551,363921276,652523929,475880710,314953712,271420392,929269701,789654557,586776203,444464222,400198801,74856510,840112636,405809423,683667453,668103439,404128153,583898666,397483081,591189903,697026074,10713545,636165925,38868335,430956121,774901965,121637886,413126190,77674449,935650769,47629891,948925294,438975540,418247028,362839824,330585559,94229589,9703290,703882517,194228484,369130899,446296374,207458195,177983354,862553443,148858874,958797224,358155905,990138660,572835333,63432153,766854223,278749919,932308804,174570994,394382879,487493461,256511641,749622633,75027392,246512519,387907067,403116764,479412371,492290617,419410613,751018447,976316243,405313256,281816216,536715799,496849553,449984466,105594020,613408089,349794869,835091367,572892723,999242994,236993425,84316027,543239730,867466395,463567432,60720531,929814779,585459746,69746326,216233605,629202175,294468487,151237686,426036067,317072397,449695867,407190957,906533626,232477383,296244106,100714815,179515046,742264951,418519336,585683751,95096980,819389055,758371992,925527562,482826216,89161321,534440043,141634347,178184420,939233565,487874425,385644448,847781438,685368433,866006627,46974041,96802024,749867097,18520311,61971007,469014913,358976870,648028704,239520339,517531508,683448791,105162820,183797807,768265874,801447307,651970164,732306282,880158502,489047012,880940112,696791414,811912662,776293146,258231743,179752916,277266188,673010951,884278083,477887564,955783543,855374756,855986685,706242544,946449573,49091213,663232989,232266474,692975616,748692230,517235044,967443365,447886785,290722481,112576575,697602506,700551919,374927370,696034244,983320828,365627030,844953740,297042991,456366092,168900203,613843126,834711742,635138963,106390899,28104399,269574173,600910742,159104469,100092171,507688936,262810029,575785566,118996438,750892926,875347483,828740941,984315512,319217942,494041358,878884424,509967223,734095718,391550285,163449439,95900343,602549206,633695389,824284930,503336895,256351987,905956591,955660849,31134059,665782341,311452770,918818847,434253386,554908942,448930521,703573937,722296968,981792261,758972002,668084744,968899307,983960397,462087259,967301485,518572728,788221096,847769732,26036000,478625053,36886594,682334324,637429883,162514988,868919946,770085104,903529105,776347263,323891230,950319978,903173872,886901613,248815631,8698038,54388473,457815937,115249238,808176447,496716111,419361585,16745227,399351635,150721260,997796107,133983936,799279866,803111848,624500258,805260539,480913348,732404119,197807297,632206181,163197100,660173803,359162083,463795090,162707517,954332672,697723062,918845231,505110501,167171606,544412511,430290196,854721315,469597860,163369178,198140235,953759397,906918757,195889367,852596903,558633760,373914348,579026939,742274300,298761001,133054434,360236645,742697244,914432971,866724882,117434647,117650650,553125139,674871939,62424582,868888844,165726343,504316997,701754892,205220990,38779099,115370669,34015227,415880504,820351148,646119424,568731820,393567992,291419124,360508852,440032609,175419098,917054191,456933972,472994200,421203720,231562406,354483934,739668704,535608179,129713383,504918802,880883053,921042493,985581887,846390516,170919622,226086094,272485821,932729448,783081277,11220690,69347702,314946713,856943948,796183462,23341138,142953844,343507463,782022989,860208602,810768827,492472499,840192593,241380650,751706492,517570902,658016069,490640389,875086112,336004239,327466592,522344308,316400953,287381147,487406131,399322083,647939637,241886871,814962461,436905864,492895149,200550742,158407915,678058207,150897912,576894534,577296148,742472995,402417826,136720106,556399839,337371788,859486294,897304984,396560081,446939004,274396112,585772903,99046256,344163739,753131276,48736855,748335643,798831496,188375972,839441403,917905871,678395366,699862238,477144486,72589952,947816620,739219620,952607266,298053324,933033780,575057787,931995746,183021570,393088621,57888628,552325499,324785679,161597993,305179953,533851046,842161441,232971340,793989763,837488045,938828658,604073683,215791960,651977661,481475094,305028597,882359422,184714227,882172600,356099714,284553762,299145692,580385566,23782705,87962692,448795223,209448619,95377353,75024565,540303098,449718555,464489682,882726682,835940209,818375836,752074189,263274326,546639301,367587708,855773878,310866126,702857825,724218259,279571430,266634209,802454242,599157030,636918494,65809309,523499037,147126852,700582744,619675056,409813579,10786044,198695866,787204911,736102128,660917881,906317950,440951500,222595994,215382295,161451185,787813830,964638273,912445031,17502154,700916909,866806599,163823265,490138016,84299997,200283115,399945620,707560229,462829597,433930646,247435068,228737236,101642614,421450851,925678871,207613797,866549985,449184658,668782384,951319784,161558371,324078262,961629958,935223144,241579772,302861770,768024516,213329170,477686970,193368799,387055937,274173934,514347192,993751293,675480872,162142653,29028902,986894593,624485045,816305781,18524757,640261027,685467181,548070777,649797315,277304513,786330042,18100112,993266956,238720984,447123620,215643712,942762369,231827544,301987811,581752197,576671181,905307498,805016747,148102341,34062330,876881025,160277648,125940301,611960457,557706960,130234481,474989674,536692515,559138880,789116564,469617682,221467176,718315800,316152421,9543812,221326809,643374696,91230515,209129670,583541854,500948167,803563212,929379318,667963201,253394974,122180013,461140156,301141723,590621153,376454512,745022975,267591217,221882735,399683740,44164002,204179587,817158955,666449820,133518819,356363186,81971147,787838043,184686440,776580696,926174646,273982442,88825814,58542521,296292823,207475982,559277983,361542465,847776259,163242750,580515700,412180643,152456706,834108660,198982135,618280239,905808763,971656386,294389113,101629855,807716181,95758166,286377171,249433960,949099490,662933835,147158786,410190321,357113199,36074868,473413170,517259145,325383967,588240859,216631347,939988037,704740432,362062734,699125527,529878085,894640294,934852530,270052507,300233347,898924834,480021354,49341094,350170576,543808014,948208351,361832004,342022060,563356669,684153247,446247086,426184429,938498307,814529662,663390989,978491956,79336254,418235816,522547985,280103736,610285614,960954107,669418237,636681955,29060699,143240431,605920828,65272615,161857710,193022947,44791878,898779300,805941855,970942283,88760155,250839669,996800734,50504812,509949437,330707943,892959909,213521467,471333460,862522982,895731003,117033073,904179663,933534763,112103596,375189620,946098914,679494622,622277947,317340324,205890758,720954080,147777497,218527591,579018064,504238963,834849264,434511459,817009515,27435857,399494624,332423559,689077345,259717685,936720947,932682608,697859822,358107569,133081707,649086179,438327184,481856446,448634245,773059184,386703506,881471848,859060302,461156947,325530734,678971412,58409931,591004860,428208380,549849955,408266547,10948558,644472645,584415254,557077597,308462480,262618186,922638127,891170395,378992741,665114719,250436048,203223244,100131219,27753587,999001484,372082752,842278838,953202935,728857066,71219079,465872517,140871211,45287885,583397136,43342448,917844041,519102564,636911689,677136946,774844340,890614185,728078770,715300078,614850504,525944747,828983541,15901244,563059891,861147376,115748404,891479459,860105355,887775571,173686420,721964447,974299564,675536840,909099210,69787508,598132937,215735505,763867452,307780305,315224795,257069339,699000597,42631697,426760096,761522432,725173221,8172191,346143827,881421693,485134539,61373840,387999664,841644043,639289454,710847217,407315778,827184982,872977809,514712427,650977926,388697767,651986940,650560857,545265050,871072597,9158938,360310916,467525870,557679888,382363831,884867355,497998931,999420121,351583878,464052781,195332831,297510797,416116628,855721502,838388373,262073373,490376398,281135652,865364722,723632763,774629821,895845889,586602452,299189703,502989057,860222236,942221328,448686115,712446597,889562469,226244205,861993530,873623138,392301894,59153546,384055087,488214999,764542457,139220830,289946689,614898152,362357552,990730731,123451692,3658653,486931213,842852999,777065322,19417237,841972685,465838688,276928498,689181078,268488311,828957665,794199813,555268280,891718688,649533491,409831381,604703160,832109463,167046828,1680011,662119807,118699441,636729064,15194321,54926539,104935161,848528585,413667886,236251608,996889429,877740580,90262338,635438974,788586152,692471881,420701505,775113402,552782467,458257458,567394085,296232690,258206439,458113733,729737845,540692798,605211276,104514999,657793986,430891998,693644824,482632240,482571299,768807337,371540193,485312580,279681022,302747931,322514472,481057734,558282531,262194731,810613042,342165041,798286677,115501613,327052423,971973386,985217663,15706515,780390294,685378102,134259288,162591066,444623838,430936802,197963627,226617977,460486881,586569446,815081303,999864324,853014369,481077205,951594519,190153522,776604740,960588495,395431724,720506779,32791068,923425485,200799429,407074527,736135860,640679800,910354422,224485194,367824224,17571799,640424877,463085563,792407340,436955535,290778939,560194316,96358442,204272324,483740179,939095572,503263308,662629979,634932097,773231794,10088660,257835076,128847296,629919717,148192775,9537129,600764913,18293157,872885820,57483957,830731516,324932691,707364374,606264262,406622056,131844564,555978454,680050596,643437718,671436318,490911066,767491486,83245941,734161832,461032329,263025007,570671980,179345453,222836,845675051,298540900,242053981,463193176,290862265,753722873,544730496,66815508,657709978,778192024,744085538,686963333,57756941,639149465,575648515,507967632,449830644,284123785,777291864,898709349,977325486,861120743,900043824,530170124,19765338,436353451,1241939,874467027,814614631,724631210,108400665,534546701,598415754,26614967,996246170,425664980,608018065,484083762,190880933,117363967,777473724,276421092,534920412,982635960,877882282,263854552,347888918,5925844,476049223,109891974,713174174,71740838,733011375,850362311,102250554,208292259,170760925,939090811,831791817,424574930,270901856,447707354,158927859,547975739,120377159,1407749,573986107,619344050,406588099,516934415,853237144,531428879,888666006,823387951,110722260,889958582,878470071,700353572,843313827,38477180,418114607,225009542,743436994,74616504,714191885,117481150,572745180,793357863,171885585,418645575,934539494,702351118,672414186,199339595,282783719,302404978,936813572,116381525,676802663,429574061,286163476,71752210,341719914,861800004,977363308,789415203,696633726,352154702,249421864,303633973,232953838,853228918,523112353,474425154,748648093,865608053,358672231,445822923,707888175,450361960,364532999,93600009,761647912,711484164,728436150,104296709,405636124,894114049,859633949,630060216,382229196,702891868,347082314,52729082,366208045,857470333,477880507,696199747,207667901,207866710,833743742,51857644,382363890,662051653,881565939,144619189,288624057,172575730,794502207,900713730,864805129,204918258,841768089,650631106,814187214,111422680,33442181,436460665,654346277,901342504,955201375,835319802,887811660,289661295,516516850,432238577,372148324,556008661,764829269,749915175,910830953,25255432,557242896,406556149,950992665,581324204,126283863,731228848,649809424,863641269,541542263,907821675,247494334,795449184,311600274,548936092,941667401,237624497,262391034,220684679,614045437,467282437,974124406,558867201,234528418,891636076,669086669,215303651,193244019,662224355,970849158,430607111,986759002,229234504,390235465,590204326,895070956,174243400,516716922,237207408,542966129,154312146,694833013,545852786,9221208,407722215,356601047,669096223,13409367,974644345,556274700,245780319,590378918,570825289,496438306,730668286,287419740,69075768,613515030,839773415,271088912,210578307,569123096,468390660,719005287,535989968,618837059,692643603,659668869,756332491,253619888,8555568,762315760,86111608,390599649,766044857,184643031,382862409,403692518,890701701,841764277,289777475,256984943,807231124,222005128,164928489,508888675,876526185,319856294,800030635,685883295,528503140,433531231,12805153,29483462,119083733,116065822,290463942,37244906,521968553,874716716,122800149,198897981,688187626,530744998,713063634,187480928,898305741,66077171,35454102,80232676,729155306,824421478,511154655,456063676,671194987,347352382,716185855,867130222,888056862,196441199,504161959,854772718,109803432,633227467,797283460,540450016,675049761,577876623,19933487,901270527,858460926,645612630,567384321,819147184,592504076,933183173,578185139,694670392,606403900,644007246,142593857,380660423,202275799,170386636,359094968,300655825,412089114,535792902,78168640,917714959,364474102,33522112,830162320,183699499,857767554,60578032,719865328,843724229,668407048,903824636,31285351,629219508,354539920,721973461,880217635,5061857,137637029,668079625,650418070,918714142,251678288,910868633,649130050,479419985,317988349,801781537,854829903,439207220,781788761,214467067,877355788,396269529,200212150,305711638,971698430,669434817,525245576,933990127,560047868,159841200,244117348,432555695,524996388,510232042,996274252,340069799,138045593,312562430,946931689,820502115,65622520,270770579,389121884,560763869,372856702,799308936,780232745,521994724,94024277,722192407,165168277,102771145,175756715,405627163,737321181,679255042,854889464,940740153,573137840,180888736,836603519,168098106,713065234,313567384,456402778,491507438,664072501,355911866,56651421,58354401,147828976,608505383,57310252,286303604,667404973,767391780,639790947,56510947,445836419,66935576,216998043,736156425,898031256,496158298,23959459,387180764,434346947,399472474,680404890,619781092,874200661,735984431,370824561,112289517,640219165,945861378,553563868,855299417,819119721,841821127,324789157,739430080,691901017,132572231,137391822,157533509,154377542,743356407,732636700,145307413,128574777,717429457,850571539,968017956,921734543,980682296,273630037,592619283,57538755,98032804,368786924,524288481,195938351,942513224,192969840,563994909,435484079,611141904,493445550,173945844,628890795,324811482,629660237,575568603,980807319,336072287,444874766,643989714,504017328,147792646,587040243,594992052,19760449,158573479,335164136,617536931,470053710,198171131,302839318,582436283,385942647,974527180,475802051,723554897,864391868,911228957,170226653,884553380,953529161,348936058,654772264,415298069,111366363,946022892,913620708,755116358,493757267,203269188,35186038,548820490,101410994,117501057,638812692,502026825,820131681,358084955,750969296,426598288,162226641,609356301,871259148,473323375,419163372,553066848,697944140,129060461,572747102,728079210,48593885,973156702,736743970,206038672,578679390,499390440,607935014,880422182,736955752,740647471,649989432,160490038,934337449,205312,119932738,771133699,389302166,903129660,337132750,64108811,900852270,333266103,424625164,36211704,103932155,874012303,778176542,459680773,964623517,410854952,454355456,767347760,907263668,379372068,225654162,598870122,66771044,89449473,374243668,880723026,749406143,856767579,252994265,264945519,499899445,984031700,61119934,549068907,322633092,141267010,819950466,824577674,47995357,413069673,614574732,609298973,275945475,256210671,591682660,152207761,201321771,402183750,720402771,955539498,354907943,305809234,430258274,413573598,732877590,325280447,105575399,54646452,264549423,301628072,496958980,692685207,368412157,636765016,563273546,111916843,850652562,266842427,939246547,826513306,54199019,61370932,836095338,327052358,83036812,850194853,110045523,899237253,212089358,376777544,888106815,630873457,977528333,613021629,596140575,792330983,820302183,519139282,652149738,553793111,91729862,586723745,234181959,278383713,8446989,923111034,60789406,937763655,101412157,957265574,251881654,196612867,861768639,939552677,601631828,956988981,659950822,26399074,412746319,53737693,112439270,314596913,355331813,808607426,256673699,334817671,402884594,539953523,405055249,56762655,91740426,53924917,236372226,428558422,447619685,638691048,211743835,350846971,871459918,975772611,935559617,967642012,930267863,8518313,552786353,215621393,154773204,653024285,672204761,69698930,439164614,19147554,420290640,8703884,539675493,762338139,207968681,410895820,683169303,235549969,309962064,648594925,167089204,150136477,403274556,167143848,197399569,731944045,115627071,141543183,770517260,268785796,792299693,967557354,896699868,407973786,180953959,863399364,191498617,263270876,916464585,681494214,366099626,421620663,192056203,799470241,273161874,693450274,694662672,771876946,435182874,958692906,739327339,467148816,863411417,212887729,475088201,482786779,964581398,508621177,464526831,886143074,581776387,533638222,305694298,72982060,623879315,941407510,63264964,326695345,984546992,252687963,727439838,683662892,525106558,999735806,873000126,757136099,440620527,308590300,838861457,36936782,263900303,780219244,991807968,967768700,803779314,337424343,606321694,956324462,880229859,204375349,799387042,339232453,960629622,46740582,25969934,910736911,269168294,17917453,559748915,628701021,617932757,406564943,262419613,534075397,37351027,870531351,988261477,6114807,557557143,370762031,967759908,78440718,776067064,964967734,805140697,764333723,505240854,490161374,902761762,590565389,646352522,435540386,14110908,45057809,662620007,693326656,888007327,256182354,230510779,832307448,975205042,873277505,542329510,980269301,705353140,235806828,685849553,176735549,691411806,164533879,879730188,382582191,771622376,983569264,719561281,966271689,718740024,113598839,715522208,56618240,47330751,999730467,9753687,756344310,303332282,978142516,844874551,101375722,237703029,449415065,257303986,834876428,303395820,101099844,444150646,10534448,586748602,116120283,678383315,973970383,581979514,562184638,198748755,374010992,836458387,229400724,205713548,361212696,981208281,218514126,837658921,213771957,975428840,689253068,333986422,441143036,81044352,765624531,162293244,140347903,653509995,483200976,608193736,290819038,927237101,536898121,339056670,569660058,884212051,849866128,495690157,887736474,540069284,446077371,313955368,922691325,366299612,962353585,601418226,680254202,740021802,502415259,337223972,859481043,400553671,212341589,70252912,148259753,984991018,545895023,152846565,91278990,276912193,106214106,958712923,797273234,191494978,319425808,33178555,162746851,966130833,958465423,803275665,792563564,927028263,533956703,817840616,926262942,645409737,828265418,23784180,837562334,129128308,714114974,841561505,406426138,926657070,54901487,980759353,708192933,180580719,692721026,793916848,951210902,223936079,684299996,650768659,220634024,727632446,244185399,58985714,363437189,368174620,801528008,797906501,54203457,241433630,242846429,866203672,438010680,130897302,50885878,372691780,393905359,674013330,62959868,54670551,753198684,337399267,104399553,10084419,635769717,955203129,874834571,42118666,102408464,614468979,367443788,31561236,733121657,515075742,644872048,96328001,898059729,555170039,471284152,960991073,432908882,504580022,610153512,203181177,258984485,37323685,951446001,17134794,693117284,247679562,9943142,515851588,751703966,923795328,375047853,465945996,76354674,540984874,78067904,803350503,476300857,719441936,157689186,603157648,136098134,326034853,633333338};
inline LL qpow(LL a,LL b){
LL res=1;
while(b){
if (b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
} return res;
}
LL cal(int x){
if (x==0) return 0;
if (x%200000==0) return a[x/200000];
LL t=a[x/200000],h=x/200000*200000+1;
LL w=qpow(h,mod-2);
for(int i=h;i<=x;i++){
LL y=qpow(i+1,mod-2);
t=(t+1ll*(2*i-2)*w%mod*y)%mod;
w=y;
}
return t;
}
int main(int argc, char const *argv[])
{
int T;
cin>>T;
while(T--){
LL n,m;
cin>>n>>m;
LL ans=((cal(n)-cal(m+1)+mod)%mod+m*qpow(m+2,mod-2))%mod;
ans=ans*(n+1)%mod;
cout<<ans<<endl;
}
return 0;
}