#433596 (PyPy3) No.148 試験監督（3）

• 問題: No.148 試験監督（3）
• ユーザー: chocorusk
• 提出日時: 2020-02-22 22:39:39
• 言語: PyPy3 (7.3.15)
• 結果: RE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 38,171 bytes
• コンパイル時間: 182 ms
• コンパイル使用メモリ: 87,000 KB
• 実行使用メモリ: 77,068 KB
• 最終ジャッジ日時: 2024-10-09 23:46:35
• 合計ジャッジ時間: 1,911 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	59 ms; 69,228 KB
testcase_01	AC	60 ms; 68,488 KB
testcase_02	AC	73 ms; 68,176 KB
testcase_03	AC	78 ms; 68,128 KB
testcase_04	AC	87 ms; 68,464 KB
testcase_05	AC	75 ms; 68,800 KB
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	AC	48 ms; 62,640 KB

ソースコード

f=[1,639926614,112481927,844943910,55098162,499068954,184039231,493165198,799018112,241125013,677867054,873794111,644524227,747095828,456882034,98043818,804570289,511595996,450800251,638565860,699421653,862520201,830309978,785830126,999080403,30760690,742334241,116356654,347644092,443451874,961631507,447918439,298264049,158157714,348997310,913579594,547915206,109157533,297667275,754169579,68604898,743964234,217532900,348104126,242165296,14179475,114046868,441199414,99769214,431734770,310065911,940050658,860919687,79321087,446550135,769913391,695517422,482678519,25743790,744214024,304751648,663193038,167771168,645740854,800304985,325422761,729253209,257991083,404296372,333031906,799057970,277534385,345504787,597828259,633988842,593572225,346396697,915803866,730628666,767344869,661521818,638927887,69113413,175954999,811907079,383686012,508635028,550010472,150066936,936181552,544576713,210687303,379369971,799369622,235504275,358470553,383295467,956553517,306542806,278659706,935785718,772683979,118968429,578140557,884263687,801434353,955821226,813827702,185573413,136439950,355714393,292874729,564595064,756498957,836183630,831129346,703180737,761908122,855025685,855144000,200891912,619148829,482599926,556516933,45268585,490484751,46636197,782509277,361946029,42242185,330868212,696944470,862561983,704644614,422258319,984581831,555223579,743934957,46450580,664098212,717470752,122135905,656215250,704210494,742784681,433118818,238079432,401243384,818749011,586614027,92612134,747272923,825255985,580947530,488369485,73425086,753131797,962148036,573776713,78354847,774984247,689976071,823290557,813469669,244818236,789787495,721541922,669318546,509057662,936151626,278396878,109840073,323909107,175746078,989478952,869299419,486700580,810059799,481647083,130506241,791867040,12388880,440663429,632957003,303567866,773247346,81323169,576439192,976227856,723784291,170962113,865273066,944323045,482012440,267666788,893512177,513842788,757138905,933979388,808523195,567328309,545281563,204420471,986139696,686789145,651553978,249517004,320781340,441779759,733143657,156110635,885578133,195814622,370595319,190477990,408619485,2372115,95461403,506594257,288543030,135277835,385566497,993142410,186026881,294954750,117865436,866791755,227373616,723496015,319989143,445587811,966077428,119271996,558933736,759509575,163278853,986547466,407130505,160425430,536866111,717213282,654601513,887500885,311994869,842873786,479831629,972908821,770303844,234208469,309739425,324315743,841402176,864111391,944736422,587966067,46637327,117175975,978569979,45662811,125364479,118474328,303459981,6932913,907475569,890000195,885405076,689060417,152888,504224423,616254591,999306917,791566242,508111147,248577658,914797305,415786952,725796711,241301623,214078934,654881272,802878396,317001358,975184243,12063011,246336953,510197841,42387060,9546426,468479803,331048663,749302094,3439359,310148765,510332059,907743213,84216407,702396285,249990892,155300,421020269,576460826,292759478,288544306,552597666,175957429,388527750,263101193,42821069,883569154,808700381,241353704,724850432,610938868,227271461,252532373,862855945,287010876,656609870,241144654,460318528,212131504,861981326,261273215,191557344,438039362,508802256,152754813,177437831,359800384,550686438,820374390,907783355,432795594,71965020,724637223,607012328,633410554,749060612,747994910,2915298,155137408,214531260,407104095,29665955,314936343,649659034,350598098,535035109,179257123,510311749,128882960,623258928,943713322,353667217,741593670,367293523,673162662,470298479,215874078,787367106,422288605,284277007,313505953,96097477,545194215,544757347,73442080,765787407,158939936,418369164,999917875,377845146,115503469,705308226,986642026,72904940,689488055,104958195,217170704,901860326,401702717,29253500,815265330,326108726,532814826,185619271,465000290,212588874,592763273,230228238,830230036,785110198,773200138,170357965,413627018,170252332,474494844,364442870,773832343,686350774,496413916,735970549,422735591,179574618,528795782,479888131,17294195,807958606,353056535,688790688,721236321,221835747,193856493,898095671,225259854,583782254,974131920,753579979,510158010,683638810,921613963,514187185,382571323,126477725,393169150,677774860,632120947,644889598,830738748,826598904,733616106,352993636,837700032,959920169,669383601,332296438,174096350,402283854,376834809,836924630,803328680,350301559,669032435,241497264,434966400,55194229,927659855,253613870,698398808,693008194,671589070,282101560,589644499,48533004,845964124,154210000,669724987,79753493,206936825,243181838,860591235,483076229,714594970,90111424,921625212,912922658,940222588,401539687,16363628,743447919,333538978,848593291,511768062,546435930,226500139,515382620,515388641,685624863,867300069,418273451,946983274,690525923,106792361,892749590,375285964,878404645,700008991,901011472,288822198,715366452,425042214,795104290,841563728,870733658,902386191,555623692,550332445,529136264,95298964,22157301,512378200,837126937,793704169,684993501,723231171,167580913,625959377,229833454,688050346,579237901,241540609,379313712,638916270,255883242,450200056,781313414,303773384,130531528,270029282,709357816,338440254,400189042,469529019,827603278,794857710,80965694,611830970,918266524,983752474,836459653,282048390,809771502,388318097,698642431,510915240,493292108,628785057,607344285,551461245,616706116,576616801,751331418,327673428,139452199,25029917,351825637,761107994,669055974,915971206,716766771,967380492,340600869,534292228,654866951,701912031,977271782,562759338,434113789,275149640,968172596,78040824,435507235,654240988,331648135,844961917,995136376,65793395,775607531,391581518,315270666,95353946,812556447,37735563,837414860,264806254,178879654,166114276,162362839,907582514,692126610,533068572,633856890,560032582,56721505,866703952,352462669,509099606,90186902,971782310,624033229,200714935,634055390,839681504,146083572,713353777,312149531,713554826,509588070,237157356,312847121,626185157,273252651,179375670,515773563,514984174,72709843,480054986,14665164,485251798,396003038,107595206,438931104,656102354,774131964,16819240,587554352,587843669,523173219,956000070,190275356,710027943,671330336,55417599,736253322,85325823,556467848,981284675,990384114,3718675,952153896,980890590,854022457,780721779,938357679,69880410,770097329,888259006,473264534,106938434,849262108,709912685,140315068,654114370,738257817,458901728,418801087,138959538,386496960,526677538,321654088,988887285,729052031,873562554,675125149,629778902,150340047,28552679,208020293,208910674,160401786,273046452,621762825,238343407,478590721,694930680,907506220,514595445,682820341,19258350,622666322,887424400,964459276,633408320,640359141,584841763,639401681,497294065,597995585,358970235,261517678,699279305,457742741,390813397,7813507,863781574,283503178,782384395,326440120,941853248,113720884,307678299,576954658,754504516,329656909,574166815,973272639,567820050,381117302,220100250,866628638,153017173,948793126,660073626,499682081,309672260,676742903,454376998,343444028,864251395,814393642,896761531,906774760,999648212,365456517,706420328,25620787,504204977,998341547,312971120,497980174,139941702,200405880,26964525,157535113,735693996,506664219,136559468,813430927,475650352,174440279,2235727,491852961,751284240,915547164,278358879,443992942,61380201,986675414,743062868,382563336,358232497,951186590,799891495,948158557,650878822,98482249,612185997,804290711,427480644,353347398,494676038,348636603,552589593,932529044,466379846,889870436,7500105,63042754,156482666,160912056,216677699,983374337,103153208,77648826,848980694,996956238,994963642,49419997,565479858,956551459,243895835,47580131,273508588,395624577,986629712,354097703,466692797,816378169,622343,228669680,613411243,351020549,650499988,165616155,300912167,766670254,28036257,529421482,686394608,854619342,220697711,400683998,943827276,694162123,805155584,781825090,838125279,505515263,899058119,981472394,585515687,420319401,446453324,461667907,370926564,363910627,859574405,34459894,947737740,372705778,764870155,788349698,905550006,587054476,884299416,104274383,780384258,238607062,101363290,421598915,985335993,766764842,442266074,871254765,380437817,873378188,239136706,494170186,436417804,50089210,43460505,406058899,952004841,252168778,565232080,781584171,168955240,24915362,866514378,838281425,310513812,8300731,374513568,951677009,254079069,502836498,359301494,360603608,734838326,794518561,312425857,711489174,209059985,892564549,283784745,810341606,189848103,207952489,646882658,472415452,178192696,904218962,409559234,799956962,239063132,653998648,877414581,822407009,724829800,407570410,183369218,911605892,471021218,768779888,63346383,188292620,22656326,175281203,290414273,500914036,940110791,444120173,973234333,914259986,670514782,574265631,789211101,898161392,160800189,281865874,36154354,337080661,60164301,924295560,878545989,727152560,534784668,810465630,402412573,261932858,623973502,445610366,241219483,505246359,444037086,264098773,816677864,878033697,781751482,478126546,972022368,111511512,292944263,45817506,167176950,797414450,109226380,434722139,796199407,324392026,542920902,273761199,799511455,138559141,293050078,219515013,866550338,575952549,501265668,180776494,940743062,701070580,293547492,134707686,585402750,947451914,678045668,111223388,528662796,180646621,870103700,718955841,869339972,355968844,199000138,831384042,277562090,214268049,973807329,429332151,612414824,616644624,712358272,433718073,748007561,202089505,567141781,864435113,619902861,898547013,667220314,801963042,984777754,768269846,930560330,475883093,185966977,983546989,520238050,801726892,98865979,419234624,188798676,681349435,667845864,425550698,915219645,103762795,790639064,57143988,875218552,190388222,356867670,694685736,107463226,480404422,489781331,636865396,924068096,106948632,987523804,510150898,373354885,727831015,723412210,338188714,161687663,501266714,571332907,887234080,742633209,899577855,33008244,912816636,899649882,395980348,424420620,798540873,172223561,581938207,759470919,824750858,490032230,934699640,163593758,216115945,532248036,837491342,739057315,99711200,733461058,923641617,423456589,298398094,864357307,131312077,229095807,730573802,39004186,924427529,555853709,304400563,666796032,270684879,703305033,602206423,19300991,75019264,37676111,812754296,866949601,411084554,556917497,612014120,152723250,949966945,626237626,161076992,632980031,825973444,477587933,523423431,28154382,961613238,86579014,362397567,812475803,244213712,514547315,801866685,342290061,538854447,693050268,674455282,378814433,791633404,125217703,265720464,311792214,75332589,130482512,520865783,811932026,380180830,299019516,671893755,628385664,899759169,724346562,671932536,925729472,912218530,979002975,589231618,483891986,497871651,992912018,820492166,104909388,772395364,873799509,110388872,838245993,873094120,668201403,755267989,226415225,490198536,714181755,109591717,80497756,369930780,139812135,532062881,905742254,601842343,666318906,458005656,760776367,179742136,300950886,888030469,59951296,918955765,377780181,103150167,502463774,466672422,94778030,806068121,432422968,47198565,50146737,1169342,529614143,87443069,410713805,129883730,987845867,752858255,703082768,743332217,941009243,886132355,805751509,199076765,680208181,347313937,23147230,191002498,129640287,937906602,261441717,191736061,135701022,116555201,43441457,865650697,93697263,343585554,127958501,589293795,580002085,956350020,819149817,780277170,736790935,946181514,105183516,764297212,647149348,444408487,424218462,606992889,963929930,992762860,288823986,804131226,456358064,500916892,800456223,781292072,393498474,346061803,51351450,903374507,345303775,268272146,798672667,22401666,836988638,405734894,903907958,331130338,663009951,870259171,184055828,959311522,688270876,216043485,729986992,353568962,821556726,747496997,780367705,104771131,61653598,709218975,711274425,800863903,10436780,7818988,540285976,214985982,40516807,997094539,513138166,743618070,602622268,978364285,970808980,735610607,365808294,356880264,927449108,113555273,624854174,312768216,171045419,66308743,764883550,784022591,685710083,730588189,133418712,847011901,351487976,233763124,979879958,565129276,825078772,763052478,883675628,61209883,418542842,626048082,802594907,711906851,349266839,714295382,960259381,216690922,699537107,561470632,657818185,11311527,771745955,855685561,789571797,827738818,674273249,402394052,869941376,419593071,120485514,998858593,925271608,746964307,634456816,495573156,584915231,445400526,843701973,199465759,373203547,770508284,640948126,389973724,780879573,862133517,908799711,759374454,162303580,921045708,619800466,955009692,219381059,455162418,278479489,248079245,988122582,617253606,614155260,925311357,809692587,771802288,89570528,414631711,524697206,313433272,184839894,654028009,890686281,357349080,795180796,114350502,255441194,591557156,881464099,761194443,208655553,622644356,915113484,235135441,818176738,486541857,341591688,224153759,234316848,641252505,498995507,42642297,355059206,755765382,51586816,138279862,328134956,176467107,443945687,972541380,168206574,874145433,39347074,468533757,937157388,847347807,242833838,516843807,816978580,762290916,91457343,164745346,176422569,65444461,20413191,565942691,755437061,220987436,951628308,707632755,653448585,192054583,779996743,312385579,104372309,311949097,338796444,723087867,277493780,392508020,892860888,249773509,817870252,516009706,982946909,785886973,509736736,135646358,223481740,476168852,467977765,696792818,755718134,649438118,33347068,787604759,136835943,596459811,537441964,159562634,908056287,748546302,30292019,52240729,751529808,790172219,828581950,904074594,559313015,189956392,303478168,884295505,269312807,43759411,255296787,237642100,517985998,127882938,226318316,685641095,241710052,633676788,205744264,819515596,494712236,918224362,27632923,396338745,296680941,335090192,92186650,519052157,986421688,356369698,148892391,959398638,990961945,861227431,626052914,277887692,685701902,350722739,122285044,126385370,387119998,480979863,885244951,683334905,408433396,950579674,369494295,511646442,608966446,210376771,227491286,532868322,971681392,980684216,978201674,925231585,904808929,857890656,280638485,221481387,690699313,627632139,366898179,293924799,528029658,187130767,400916139,601090388,476238874,301695950,936093782,969354412,840356432,798916670,457514504,353885146,352466237,446579091,799178457,752862870,338197584,4295955,77262843,662518691,173404829,509128287,887662440,32448807,862342043,178489560,311502312,365636691,694100109,491954836,433979195,268716921,180296458,435077940,62200437,858952048,439914052,160324219,841399346,570262387,722883215,974837095,399849157,786959182,366701760,977657506,55933275,559881485,622697443,881222850,269778121,820582786,279985854,611902161,314076684,64455342,935498489,60230386,346937429,83071794,327684235,145720501,587781485,980314373,295597943,426808223,403077288,684558917,818273452,721709939,120051495,558151553,974666902,133951492,341462465,700107938,340790120,611267423,804288108,506150402,407902694,146797709,354008902,143446265,850418698,466045032,773347166,908015781,807339189,987013454,273225862,185997124,525824981,905471820,977284051,878367995,36808213,631140413,711403642,892771910,217931482,420607674,332515431,943438445,195443724,209166918,72546287,935986300,577167667,537766250,70463395,716805828,685323762,854134151,383292501,682689636,988984842,473966377,583203296,353026187,712342882,744459282,58684392,28375949,46181551,649847092,59801553,653364713,2911614,879933214,934861184,989520086,928867061,212274540,123659858,772492041,869247099,651399187,172225366,469765886,858635594,67711297,16490486,316373927,902182235,649879620,640104831,572467073,171679539,94143767,651484064,177238776,738048410,704416838,414057597,362835231,889053801,919767209,912563140,863827554,260023631,1508681,516388569,438140142,960520231,278684662,982284977,263940799,682934507,54489082,354948305,483005593,924063343,675214746,845441532,891106570,410959281,970281560,249139343,353388431,351583923,993067900,112170128,802682411,397830808,312618014,852836789,260683170,416005455,621901949,363141564,237747964,204840415,356246188,95948290,875442203,559794719,484977011,593351477,710061836,978526164,925067336,538225430,109663520,239241330,63107359,684921161,320437147,811099941,715414661,437291872,562164763,743021254,41580183,753187673,579324298,975085223,497005405,197482933,746411264,435564148,455174429,175217286,484659949,809871942,427365270,930569788,432959621,689075478,222936083,733325632,134034106,661466799,660948896,206283594,35785896,356902799,584445373,860092876,478672220,23273055,487363981,264612104,186532772,553803586,139860864,375479413,709549427,879353099,230374220,433058282,696404349,247768234,341274621,824726232,835003900,221119012,110442745,663285168,324243000,663614496,686370100,610355794,347341854,787377531,75889957,410260572,924887920,617783779,726278407,141034667,882668651,596846316,722057156,801620565,793887366,32568110,664923877,280447634,471801954,514653558,859012435,539012567,992722806,729859569,842397008,582334448,731605044,877472626,216920153,117111267,700669089,373065010,868788020,192909957,822582560,196719961,247864761,901437820,416723811,268235664,651836669,242191138,486614248,757059131,372895670,473245986,402090309,563209164,679712825,119617826,763065382,944461191,596100162,582524622,191299652,273898799,579279427,27271548,690340417,333664103,920267720,763258578,891719612,211523672,624503403,517785257,199537492,886247641,624661890,740102975,152139495,449114782,126234289,807353604,430864073,57581314,898099214,677357433,68385094,719723084,947717180,502074113,194180543,270545422,538097205,763360936,959196524,128094044,981892255,37227708,616892301,473465871,429458039,928062158,440099147,812227095,273711764,453067630,338478950,958948813,320481246,416392863,230796899,416568517,846320165,403468924,874293813,609578057,854975576,390966467,709270764,174640789,884758286,90780688,546598919,116791879,78605502,97580941,665677258,925745345,874504282,397618185,79844459,358645436,212745597,444801884,924616248,232673222,115174633,718494493,463702589,100813613,35037425,905625902,690596139,890521000,232275629,439144581,888530800,57167972,159002220,809645601,187954241,993688590,622625328,571259258,502367172,432218919,703936104,311262977,707039391,907694187,91530937,379698006,954127655,350885718,919698574,619843354,131340035,916368173,628545404,42160512,474380103,44463032,617728036,709478648,884743272,312240882,285268762,139908674,403384345,863780380,505374889,884941258,121614335,664113576,407785566,7778675,633133367,373339002,810766980,277356393,489726212,258263369,349006058,574397869,956813136,721586861,27504611,64807900,855833254,126253992,913020121,568439116,885982797,589242422,447540511,884254362,214797986,11549592,39539485,793527033,334288685,397096484,927144715,634827367,842473825,458445106,444584255,242270229,434678171,361255684,429979229,166836929,284306401,976910987,745664943,699666005,358861915,2150404,746694164,782871805,880318683,443316393,606078267,430576594,601335339,777684982,37145118,69423864,352908673,707087052,575337280,551852289,800571556,865507019,479628478,854389404,470119661,533532812,877513094,33130302,550603285,413132426,998526931,690600649,574304958,714270532,352107498,389114637,328020831,89643262,93384197,594444305,858457261,995192060,684234210,378027483,342204740,902514038,612322154,501626534,779956376,12702894,833330939,769371462,152868271,979690039,333685400,565727105,543563058,634267440,928814017,185366687,601348870,334939555,430960874,760889594,188340786,636860911,457845184,622679145,886348246,85930321,448813105,531967768,945430827,861489579,208305558,895838088,973031834,851405289,552040245,631099033,6615390,878337741,325094653,636979633,119424618,190633712,518934111,966288648,464234119,839572979,132315604,722632929,710444267,235503430,265637221,487185734,988990525,160859135,121746329,674289231,38460352,771097762,310088216,978197320,807377613,550600832,374603080,42219437,500716175,575800070,490113929,631006005,756195743,822845411,486095306,62801370,416737423,858000590,901118446,477869560,162515478,384898593,803730215,150370443,430521009,507439274,837607573,708309474,980913729,402381047,612625075,569052485,167692766,626509050,658936085,373979365,738798533,460176257,422052810,110651678,354414441,634685289,520704596,526192057,643925973,220750078,268600476,1187964,483566681,89083865,678523591,604094093,627269229,463301760,754689216,92402540,227310899,507660081,794824936,199407377,91249987,702449588,343578158,263950464,418203385,537398267,790864921,85094825,672214191,229654588,268069944,143055746,456839309,688055620,933248606,488295779,883458788,328798970,518173220,242448163,110288476,427842169,33398755,271952450,688933934,751284778,138111969,88191394,896256578,650775846,654452148,640214992,646537175,481127310,855826469,291887361,791893026,347366892,460077768,38760888,464116925,879538271,824118572,143069496,155951580,236729338,723249097,957354294,768980364,392310873,494591444,970267065,138029715,388185121,814231847,791944735,374483640,891775805,484250645,188497194,484560330,716149552,239313079,644438434,256021737,225334976,683026443,778147734,965723709,159776367,832719615,540003575,133481170,277342719,845987264,909162269,186563756,491864353,920750999,307294631,792312767,139573388,648263595,117326469,251846962,220482058,635683300,318009725,842542892,145551673,339301563,133188612,824755994,427560112,5109160,150701170,812690262,459581631,570886675,968756181,726625754,573741145,92310764,75908005,13678643,518554794,746935356,226593925,724474971,399671101,472533279,597645956,378568593,886222352,242539921,881933480,558506312,853156638,916497068,899459287,870729368,299725842,554303355,455981899,964411771,518537539,315101353,229221768,163815481,191704527,75940933,807672432,749014424,521887243,128266835,414097149,332390749,614984507,897963614,643328910,851066845,863755312,570981588,465859747,360364184,963074481,870605132,254429407,461352935,929595666,623439391,523184583,411554339,79214981,250634210,71216457,351809319,949327946,780720279,323329780,770559122,196786108,955833369,538880177,803728868,433963860,512822402,339599190,802179745,704390821,640511301,794248796,582534131,316065737,556500353,185173563,289275793,6699409,841421440,244936068,732873676,38483473,151833667,257855397,302495532,170960979,385485432,449978612,674019967,638407207,377274874,725702638,369504741,382644711,843131160,935779255,814346534,238864169,783235012,177430235,123873269,351436318,718258991,442849413,460365766,961613609,689729001,379319626,347278963,318281898,417922452,300751979,740100354,28432453,344462766,635487273,45242679,979050321,88257530,183449414,650023583,707628336,986195696,5934499,629405321,126235787,146923995,378785317,50848609,723980861,442953114,861919911,992679077,833830166,939138665,678817974,875835259,978221508,395950453,268409923,485664380,331055451,895695960,203403445,902313430,525255292,124575985,572871951,345968218,213799456,121901871,443809175,931918556,107312351,788288314,295389783,333202367,544528622,777121530,505988742,663053085,995761696,326683179,840133940,614240148,692517325,57919366,846932417,321896467,108087266,594640033,746139508,175116758,765220737,854824864,669216033,294185439,840817915,938463265,75861584,303784489,697814275,617358821,858480227,538203935,978798992,20350308,466369788,738888369,920238518,926102356,200782437,569378386,874253665,170562467,410124462,423569608,786202045,632676588,398817445,598993644,654256752,402705174,968382032,446014770,411716630,763303906,980738344,71338963,247032837,166449040,56008451,788584224,654208743,678907764,983178362,848108679,806490133,276368153,179562483,753766154,781547274,58880011,823724361,493198567,565542888,229180192,469703761,841972674,657924938,650903731,906401712,470761740,692470053,534600375,312400795,820243702,948652317,451024494,531915860,805803700,666957103,958663123,313966891,710938611,109209174,377150753,499155799,703503962,58262415,209715123,188116091,65844153,370897049,364143239,542673699,701847376,892549348,74527441,973727253,288086592,961112653,476915210,756116696,882451517,965245359,101299157,555496689,592276862,757004519,438961614,953139148,687344123,343655647,794231206,664729273,642153777,336697977,841240383,301347505,477124368,654686396,823694344,874894370,135862096,187028283,715768750,769419863,476659146,60233496,291011460,39619555,731321107,800462487,803596417,844221994,847385288,114794740,82224163,437468538,304452422,632813750,703884447,567165362,404867962,179222567,105130308,826223750,449961891,150638034,456138347,237919972,209597160,696705501,609777247,889742229,58567611,495381441,529135074,340395341,332629610,131412950,380579648,391452566,480323851,465535902,951791127,470281592,994258045,722011579,196676153,861327653,649354313,479619155,861223790,391319516,361306281,962464173,649557013,846903225,566519445,446988894,990643745,165819062,202699377,905399450,87822984,626164401,213224530,595457269,431981945,316709929,29117694,634690650,569577313,521538790,441547716,318172468,477733636,990712756,436482531,292401281,541832,973874818,135835512,648313415,483627109,890738343,357946668,665445253,687923463,563978092,5011485,349420645,445364474,109958482,830856323,356507623,353790240,828180512,755599346,731781601,517363853,763297389,599676591,270291923,144734877,963971145,517713571,654743138,944781069,754096813,407738570,757566079,687303193,773609544,497362392,168870017,799400714,459522164,189773541,225057781,919049224,8038398,131387959,120418080,317819444,631562195,617865465,540394464,587833823,353217532,335894917,427555453,198100924,305814226,511124565,818393104,787361789,567542439,787452208,721313785,80069228,895416683,403956884,569889059,118752445,84833664,9765713,294052757,489414491,222068809,455665278,628996469,424812416,137353990,585963649,676947877,406729201,316612885,488314004,110013800,617865447,847273944,172299520,575328571,151040023,686340505,663633711,715612939,683628945,587953096,352978700,686287074,728252704,891163150,46169608,110709589,899838660,312873714,203964911,833693054,592975139,170456823,583354928,408300035,143895845,499030076,684850527,754986717,310028973,552288670,787401370,150962822,190769524,984000707,193669821,789267233,383767214,296655021,262352540,657139891,632076185,907848089,466878948,690553526,102605772,795824037,260427235,173520788,64804288,868241961,954997270,887773836,549640231,731318793,892524160,821819449,391215684,613986016,721136537,765327170,74800009,504817890,803568287,290957342,946056889,831254264,168339869,51515057,31240849,714194680,301592483,298123985,912899609,892153437,101434974,536388929,378504549,432990870,603504367,837285614,587140567,213690618,994075633,887505353,98189787,820549872,515655658,565277864,575129337,68492073,272747892,689278486,437698411,905288570,624084342,557861691,315781956,828076972,53194517,581591742,774605259,100771571,58192393,611469177,473767421,701929895,933141199,721401641,991786777,429147966,684276692,886605805,523284407,855717720,403963604,891304209,238573180,702005759,895612012,744333660,920789329,834355402,541962664,961674918,14089486,271364955,844482659,100553161,935001703,808645569,751506197,371466935,828899980,975796499,669755747,655892506,320545068,767810085,774403355,250396986,717680496,630847407,749923996,941279356,610966064,570582799,597662623,729075767,305715287,453848037,62496464,800993702,259418122,305413582,468836771,770657340,784836371,658578009,13351178,766607145,897031711,72025782,393941871,971669436,534487510,432456806,80930804,376976022,19220996,679768447,358191266,998395246,32788989,209753914,203751859,37787187,769596538,642309814,716727029,4364788,648574058,367985447,480465188,132965589,162752510,648596045,125073126,128993372,177652170,662634665,546656484,720948557,139402841,934081491,424398820,109037867,262294354,20395923,885847952,610879114,305301255,976333508,390557506,404218626,858811557,947778280,600695837,450266720,652767938,290901114,277844788,448278536,376640598,683388002,601702436,942359325,17753892,527020810,935921543,103147935,531062888,977326275,242767757,915945153,263081451,488693383,569906950,134763873,313737524,189698098,601890270,277012519,452862349,419374780,421048155,535042131,297789805,110616851,182111046,135597997,136991544,127872982,311912795,314986996,315924174,575257710,45437238,252256317,818584097,581134348,231949717,68819432,343920163,809887616,872247656,710348944,237564659,616715986,350344318,659566993,52783282,785224788,232619745,58566667,964373599,330000241,550401600,881119320,806976936,549806410,507311171,794882124,485629761,300312979,63901359,760605364,825226436,453241111,556066578,596819722,528844582,120873512,516833432,777355827,317579407,806993146,403876638,301096858,450285863,171910094,257314990,323138438,925081919,251834489,40985754,213574916,319798005,979979771,564480292,10167977,834616304,418698259,269374924,374850447,123293067,752813751,327555142,42675301,770392483,394025833,320694357,405592492,629919715,29105970,202500342,567866139,980177217,80840916,756167482,726487532,18965472,796020902,311251687,654764389,404226477,589114561,180129415,801424014,827077942,204474745,712493504,511556352,418532275,376387134,347010307,72985427,30033895,234987470,607168045,259198054,973449064,80775688,262326531,5296153,947857242,766942711,359823252,364712480,200832781,782094550,704727108,513492179,889261292,251204403,547918460,689208182,242943166,958598099,967394924,537952305,645991608,73582601,454347562,258038811,846472470,425563446,952851878,763984746,550826693,280068465,549907217,774069598,310028975,830973501,376495471,262498124,44701123,760007127,587891420,78555663,628485072,289646156,114828191,810048262,296245125,209940903,596145769,657047868,941156836,843351800,34504225,191398485,523359616,279527279,924088993,268298255,738974483,738627148,628142583,658283088,457370841,205145989,483290389,765417889,226587068,347868746,822616328,456927573,743331618,12854961,464982958,8524826,706436956,648847391,259008151,224312991,482867833,11192482,860180980,920209619,810358269,203518335,923444586,693030665,207106866,83599363,84976268,299952787,324355135,614624895,61341738,459888682,617394914,760355983,889280869,860767613,64973839,241204239,283039046,991095214,322107165,725553388,5304068,883905395,5631869,423530890,478419179,372652531,303510866,233709513,870180460,995253747,160262951,129164025,476981027,232004112,617899796,183143523,928461681,202405656,972731698,474024463,150649637,117946771,606450979,587482677,934936046,448386872,658797710,262947835,33469939,410333764,272723018,830758485,505304387,864568593,994259947,490545965,304530026,56579756,500545563,42715938,388170390,220176647,979233656,774365958,275942464,921696357,653843414,917430364,607595953,11563486,914103319,848838405,298385128,266164468,449138343,184884783,182026095,18571743,347685774,363325662,41444894,41441114,685946742,815621393,991971593,745465117,749523508,13287526,169823238,15551779,68493847,130498889,901521023,679107730,859953102,568838029,575201728,687476373,801266942,994918408,455851037,819430405,210725477,689158356,726301601,775862152,484089147,514272481,242015046,782239345,681968975,755554988,190248676,811723522,445104100,448513470,940133295,547849308,491150676,717322665,320179180,81414460,634864325,827827457,606364131,613114056,497776537,350229871,854269400,253729713,915085007,213613603,95854600,802528730,692760720,814952584,370832278,573376175,238705724,154931117,550437125,983900725,926787315,596054309,322510851,664450073,764672279,996378663,527039976,268599379,326849222,464177580,67627038,532934076,374628957,523761543,447049160,71347711,34306993,498980428,131501451,978594153,508057860,224645330,971668215,992827062,366996729,774166263,378872407,658562599,6082189,755880313,385686549,921758535,918477714,389249660,219624529,635725171,713545503,81743329,261555568,858138748,927007574,776397644,310938248,323974540,508579848,662396499,202396731,429108452,537403884,223245698,968534764,757104799,115805046,916069463,313464035,382275122,761403499,500419874,954217118,109361916,443443495,906869272,918135333,18766870,800092879,990436276,815212478,39576282,127832554,83413835,145702248,241828474,882916419,861165195,190171259,593771702,177909034,955992714,720605544,891182505,153737181,931625913,495705077,505520926,406976739,809913797,290598835,914944458,646172400,990584878,871791877,437618016,494425260,385913422,165129745,780748719,117631703,976567861,777943660,287745750,952111734,988873023,658547172,668145592,932696608,385236984,137104605,473456281,893310753,677028085,221779090,858413941,196483244,265052939,947945738,403840371,535845909,959365279,968479146,124177530,938933923,418677004,70144886,156052734,936883679,258798519,837222035,338271211,722164308,676383755,605518400,825889039,713308184,636025853,328056468,481429641,365603226,270238386,902512068,568086847,622566135,206316099,907074694,319713042,461560576,239739022,850901543,637601402,735945041,885152995,236002949,985820848,372967745,473139022,690129053,615081057,505078283,930824994,914358784,93144716,352960901,355594287,70315774,871762187,88096100,876223850,751627345,264406005,357047278,584874216,232630687,229027202,288648427,450993348,539269087,608867158,218836219,250278273,504202572,629817996,947910984,66731334,442938906,957350518,852980683,677818083,492614164,230748217,58267705,932165316,317241459,413544328,317018402,513087030,393232843,751446794,58170654,595832582,411139616,407065946,198984473,266493735,903650769,633316463,754573252,941688056,561246209,405732991,840780964,358758739,157764125,853124626,360924119,118809938,553309761,506932773,159859250,109331276,69709372,138867570,230270136,935297327,296443260,620602518,246290543,907221850,646335634,203718237,622979471,844856226,343835858,118905923,662845173,966689708,80179017,244232151,248618521,153251680,20204741,620997314,153646397,426805713,62036212,849656688,116014940,872205902,265270617,824764605,443417379,228749156,283553075,232538492,618629220,852770211,529458597,469650599,178734698,253065643,572520127,954790572,458847555,265234802,918164041,913835139,284183467,21716397,198722275,803336788,23475599,785998921,315889375,848078175,139978195,576621647,350354841,63095335,600168851,514060757,193900048,365945933,823640617,602374495,652081473,846347931,812217683,488838351,755950113,697336745,958327206,959753273,252936765,669160626,299773010,105481283,774087016,821006559,915508754,471659303,156150803,160283325,129012499,687019929,818317487,388159132,381317245,675067970,650325817,802885687,870767696,650147251,358970574,389624036,729167836,384820796,184597637,660804826,930295712,572532868,516642080,285141346,907395115,616933893,543241031,182787660,203720417,598368862,690910266,877327490,45502480,955007801,323409812,382590930,968055786,991174700,585089375,857184170,55115974,162133698,129713802,673044849,626095010,58160791,502234945,540793909,706486484,148888347,192222269,989761082,372475254,464964795,69968345,704780811,771836164,922938492,429465226,149705894,994301400,89012579,768196410,709106341,118122578,110574373,46533311,290338967,52069197,388391339,424609584,159090674,686784740,378503165,89791134,240217536,709053450,317247776,744644593,231979660,464100169,8038731,334447541,486009971,802353787,656691478,821377829,58744656,708008517,44251737,269911648,939539982,995838109,780947050,801928991,886306257,631853401,9218625,660740959,961840324,800370045,591467905,130032836,539629132,258926101,660897916,511383522,301328525,667225807,894672548,697003944,716428740,526597278,927151139,107253283,871630101,331411939,575483441,672136835,375199560,719612686,12732642,624810082,830130559,778888212,292282890,140028053,290925448,993339711,535590986,494021202,829465414,860723734,602061256,581355829,211530370,457345772,105810330,579361875,361396592,782602236,549519899,555584281,400138662,45576390,900104648,186657116,603341574,871102856,428472182,590844684,686762701,322191156,404847041,113402586,58838736,72897639,747230327,772466349,52491736,70193410,464453245,703971703,39812858,389340328,284822208,444163419,63337865,789278186,7040213,869685338,339383777,885924753,767161925,784047910,896610567,516896138,268629370,611924439,930075590,647010662,892069143,995946887,847941566,205384006,822121223,794305592,992976567,207484028,971455916,50563761,829026743,890048729,221846561,591040769,169121434,995170834,64553306,55592199,641809451,269719418,769796929,851805598,596495051,713816184,675275231,66496284,338610457,993809347,652246661,975782796,973198184,532074625,449517151,747410339,110547624,554125273,975374186,944548974,296987294,631449615,994429602,757325240,657130981,7345415,299117212,625169867,651477026,465309002,782066823,366582865,51672170,289940541,100306236,62351910,87842625,794059872,683957845,417757574,544076020,131478242,778001329,629350564,958369245,893179516,951091055,841743441,489903725,448355970,742690935,183484453,810815421,803275194,735367617,678976694,337265016,305982138,614080637,595412991,198776116,44210407,290990048,36654239,315375920,908605013,34499833,240792562,171041165,856879566,990980489,857451046,70438859,828942774,559407811,10906994,561102511,214224974,525864614,784902827,352530035,896387770,317820378,288315435,124242863,191836625,806036323,527419664,110675564,642213323,701425752,129718774,447342327,313166317,761690151,540887023,180221445,641410025,688462290,217369503,492266123,645731102,373529632,615817553,646138260,640203695,32050577,37454298,989111342,123130141,719463331,607900079,684129114,102652594,118313951,45534690,826436010,54126764,999322637,183253246,323519239,688639031,97750199,357081776,509866936,628324271,523426443,40209394,329230807,973545004,819087263,235427575,167031126,27584290,545301062,584267133,565600091,72988772,488598090,82650229,291742685]
t=int(input())
mod=10**9+7
def fac(n):
    m=n&((1<<18)-1)
    q=n>>18
    ret=f[q]
    for i in range(m):
        ret=ret*(i+1+(q<<18))%mod
    return ret
for _ in range(t):
    c, p=map(int, input().split())
    if p>=mod or c<2*p-1:
        print(0)
    else:
        x=(c-2*p+2)%mod
        y=(c-p+1)%mod
        if x==0 or x>y:
            print(0)
        else:
            print(fac(y)*pow(fac(x-1), mod-2, mod)%mod)