#486900 (Python3) No.148 試験監督（3）

• 問題: No.148 試験監督（3）
• ユーザー: maine_honzuki
• 提出日時: 2020-05-25 22:27:50
• 言語: Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
• 結果: TLE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 25,179 bytes
• コンパイル時間: 202 ms
• コンパイル使用メモリ: 15,104 KB
• 実行使用メモリ: 13,440 KB
• 最終ジャッジ日時: 2024-04-21 03:54:56
• 合計ジャッジ時間: 5,556 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	305 ms; 13,184 KB
testcase_01	AC	449 ms; 13,184 KB
testcase_02	AC	763 ms; 13,056 KB
testcase_03	AC	858 ms; 13,056 KB
testcase_04	TLE	-
testcase_05	AC	867 ms; 13,312 KB
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	AC	35 ms; 13,184 KB

ソースコード

mod = 10**9+7
table = [1,559805077,644158465,363599536,309854856,578095319,585806050,861745250,242744764,150478174,259081142,907400235,278955367,996965954,479920311,316220877,620898940,956413299,24521750,929871923,251368199,220087090,763414075,618104354,764421236,682498929,345470378,140864216,373126171,363224613,95936601,584319463,9045328,959173997,12442609,167332441,275742306,60332461,31223863,564190300,336060741,895642779,851161246,635103992,853414712,626497524,904851726,298693437,52298443,479708090,491101308,385457627,393222011,474567292,754437203,565768255,545648343,792180189,99934426,676012445,968999,244819707,902492598,979137619,474700377,638587686,353049206,921459833,850268753,919203761,19426633,862345480,542955556,181909169,582702682,76479948,930180103,28581913,685075984,672818243,842267748,451116854,650009312,868829344,695702195,485348706,827117592,296974594,649090736,760019200,544075857,550588097,706629399,854821744,596729075,798967520,198998756,952046139,924044367,924258126,723816384,53975412,63932312,807928028,545662462,721996174,480391065,151117811,522961673,489252071,323604647,268164416,90383486,800588969,169338716,398699886,139831846,475501867,499294891,114785958,294587621,457685563,254653019,172340144,258170000,67347853,16783532,402811155,110424728,581794056,196447201,118379156,850677980,777969547,748065817,228338256,521949545,701779420,445935909,15212588,762479457,808076198,8600742,586283387,152366450,811667359,386594397,333236625,205743536,242211856,27368307,987935647,692637504,422227498,883281454,59469516,89372661,599040453,324069108,833342486,766196482,812248718,59143878,732001446,759041389,86609485,658825730,562500933,724008021,995252950,340941507,324648749,59758328,265906250,61732363,625544428,644000584,9409022,631046702,714475801,808412394,316094660,544375689,79329551,64972739,585237443,62785084,44615465,42241449,929666976,361786913,107912795,703087658,2295485,805196528,595143852,742851567,973671409,243910108,57085695,199888908,274161939,470545797,244714186,54080847,579691190,169559902,588618211,478716222,614571924,459188207,508829534,355209596,947251800,986142683,439729802,349343101,212468510,259450229,704289349,899297830,405640886,961729079,281870391,798401543,888050723,298494436,628273353,247544137,412762822,736550105,534030848,610954403,253238972,522303856,85990869,617973869,111668651,125800325,184783824,56305184,912326839,756764497,706513987,897480658,168891766,450119928,349851104,160016093,546799298,927880474,673373340,83687737,298117414,753032322,934814019,546967731,26634340,30684171,981776332,567277637,888156482,350634174,998807506,324630241,44930135,856312450,987095152,816679377,375956346,47401357,322199735,382991165,497956225,259568406,281863274,414608027,963111262,597743038,516804319,692636218,283454561,79852813,378591066,879838297,14235602,603752857,790227812,191651583,277138066,400295761,212661821,674932318,245419396,721056741,421835306,620682731,859346814,929629213,483594161,661224977,792431280,107880912,925041977,995422447,168203998,731950688,851595228,771727692,310280612,544064410,792676030,500440019,199237620,238096591,583967898,423889038,740304600,89921218,187655305,751231582,787539126,710576505,275525858,682495521,623534362,332606953,714130414,17823426,447817657,243276029,545163218,688099880,787117889,543915886,60050552,731397402,838528120,198635873,515174333,395891998,586419431,935521357,780740034,265212968,159554990,520653845,332814802,14211262,423078378,970055531,40607687,829605980,148577573,727934933,487998999,634045080,585552623,386799500,441140793,82104855,528005624,959757496,190349508,175671239,513365505,803726808,881788966,136906899,155570288,1559745,25720042,177573201,677752342,581977030,261384175,245535187,80513018,439520189,92973848,323214113,298352021,946042845,711816007,285806889,444090941,522655892,257703472,26301094,862614058,80729842,907519187,614010914,279454856,430035302,664989237,512045319,661411739,814721633,271003610,195888993,8792644,142207463,540842540,10438986,457882808,620851842,286398811,397201286,424438049,212938473,348384180,545454871,557219900,71735354,827544702,674471405,356557690,72413193,538479815,677711203,533035983,579001093,908061115,927327790,66404266,864886893,168706834,346540153,865071734,195290384,105369595,251055417,259423383,48226379,349551356,441914739,14415592,698578769,627785281,83489485,669721484,16691404,109670626,811793940,52167191,989876896,943421142,26423599,568639586,547665832,515674128,867962375,65688464,993416534,350016754,483800403,182282878,735051019,699187663,296269301,946428264,302130199,29653283,675135087,23015220,91963875,707518700,865946552,315792222,748566338,677793008,316009903,698438828,653637010,109838563,976768405,743379209,621976669,669880848,105574531,61251444,452293734,962272195,902817853,542432219,483381085,146817944,601045763,974686011,325636655,837122513,498769510,616745496,781045243,630621321,828224642,243906544,950098683,24585059,933245637,613395893,31373935,776087191,194702413,238971581,376484863,643201093,217011832,214825867,557301633,73710858,231162188,312744814,372821319,848952161,407261940,61879608,821785476,825545235,925152039,837893999,974145698,62506502,671342714,724691727,796455047,454499514,671808625,332617055,238087006,584070283,463044231,266574253,345406040,910291942,666894368,800533801,683569260,447668677,492237273,14863281,84066292,521347279,504201844,834860913,797624286,662570964,710524918,722384751,368925948,128141880,672475624,780444992,31158979,740594930,196133374,784067427,205489214,890030947,806047532,751385829,879021109,224012738,16481395,172115341,395201336,677667796,472939116,220670562,116261993,991857982,836720967,557278802,803489706,268838846,422027886,638736741,936274462,600569863,243624360,299332708,835492163,250649611,656946705,481661251,163315222,77886816,170095245,463372147,95182730,928132071,440006366,596682713,27842076,115435332,566804955,954436899,621840415,187930450,136026497,588220375,19179738,355847369,141544165,710729672,233454730,981331732,269240725,968217984,366384665,859670660,904676787,757490458,196234471,270239666,39852073,994645885,91658702,791195765,79874094,613650278,678481982,595881374,593441490,112390913,199287301,12722112,143352852,960245410,103056890,220909560,275050620,667314832,59546001,339464594,956300519,483334477,469826147,982787195,108312174,213495567,194495711,744394023,324061977,479334442,237622412,75307485,367246992,750924279,135498044,796874733,381261137,6508639,649588249,591048681,203770813,884448724,913670594,660521215,353339603,578624825,53887029,65382100,444667960,839849206,363876491,448553303,874653794,655083733,736265527,114354987,84996211,321767973,33541892,217544623,488571552,224426443,891740370,285783983,618898635,876944194,337227397,200502210,75044998,380858207,779716363,416296106,117632702,665991924,898554793,649498583,914289783,535714239,176088357,54062950,197823988,920088375,281925319,520167099,419363534,609974294,787976961,188902380,21156992,160398980,365477695,141023870,432853212,422341486,990918946,548515509,384832279,686042136,252498130,450718279,414985236,28035029,341441066,651481497,648991369,324582904,28215403,73200626,732533504,500780548,834047892,439473227,623210256,558066773,39052406,98850072,760185403,820701420,521509517,460373282,709826006,213095340,631039161,205619551,461415770,45606936,648597040,367292711,951097561,643638805,624444413,576235495,745174361,789998567,668123525,585694480,132735686,189425696,412101608,673464765,209922927,739667609,959034974,337587116,199866123,357758924,837041881,240113750,753526942,841799766,670276685,2842216,966879926,886495348,504962686,698358362,99282640,296490792,162053428,128487469,325243771,328827203,30429569,264145497,299172297,464938358,33971220,802237942,401098691,577786541,303960799,587564278,349654693,443006185,773206631,856250990,146299241,405462479,942749789,204355779,76508631,126132194,251680833,763512297,30977140,872687840,155345351,658259464,122784513,363172638,349541490,136993731,54999362,278558807,472935553,873758230,845984324,717953996,765533635,587220627,187037910,42987704,512808433,930975319,793270300,113754130,911620065,185579598,297187956,522049725,481989863,53992733,744715706,125738917,335416359,550810519,80674155,347339841,262877922,472012302,609913278,408626290,603988527,271596392,332139472,139873662,508029503,499571407,444800132,464599136,381815654,613227212,62870178,847305694,309058615,741114654,943963703,173607295,854546438,580204973,221722420,910097241,113007508,729430386,954840109,821577890,616023889,183378516,937341831,895609896,932074667,333962357,909434502,313577942,836813268,203528675,978490631,928078729,718446896,386027524,417881441,6622174,428377643,616873080,724205533,111897624,487626661,197681757,851600426,715247054,651667233,24911986,780721596,587942632,830567832,637985919,703224736,990426067,398619836,68409439,967445876,661249755,437410655,130382065,189239124,437611321,471149790,764804584,199007164,943653305,724153585,559782639,470411531,567659902,811056092,228127265,411331165,608693296,48314078,825132993,479627509,761918447,436552374,497516166,985084650,447018815,145906122,193468566,786976399,148528617,191267209,100931272,596093059,265187723,882148737,248528148,897437810,319640243,611578390,701445829,860362535,76142147,24241426,320111308,302177126,613897160,816787370,191656767,567920383,241107368,194742388,454022261,690972016,210305537,940567523,838405179,157588295,230720777,540124639,325334066,830679914,743716196,538017325,315284618,115312728,318753931,508133625,216198217,294829425,218129285,932843935,341598119,169501510,587573660,180002392,302311490,189039628,311881126,146729215,917084264,4794797,453362362,545480202,814906938,435327356,922714159,552348113,468099850,480752775,421623838,820519069,273532342,184110060,593253319,59883031,598142207,32072083,288750955,5095624,79716267,192830460,756147480,366214156,310763081,429277690,311514806,315334936,573147130,99630959,316486674,714885313,997082517,120666598,132813978,940338439,353502954,193798014,137818624,481544618,940524812,498645632,324273785,542143734,153647676,833550543,89990507,2388484,752057652,811327365,996164327,321244755,926249712,168966149,492562803,697611981,708146737,448070840,563983446,50890241,274192146,413045253,743405594,102670030,451751420,925347821,986220607,677344487,821240174,623193347,893732627,473981189,215948550,749948197,599092339,358655417,583160135,340690733,528735091,293503505,581830879,509586056,689449821,864507704,994038437,347046911,752213561,106265119,810184598,843924853,125354499,365421825,231048116,193960834,6035002,247662371,947743059,363840458,31628362,957418529,568392357,983211324,83735188,893327224,763538123,209244402,716850596,97587647,793797606,434078209,149586983,303751319,400254261,516564199,783203950,309134554,296824558,811476109,488334472,880648014,263053337,985650598,419136857,588444116,942971003,780072518,469073466,906534263,238082550,988770034,990826116,199204020,443563763,717903632,797385788,155569943,146598405,867292155,111145334,130359475,711553356,800639067,876432387,285754648,337234235,451373308,327120461,439847431,358541327,113595532,462639908,632738698,54745397,26499318,296301818,654611901,318351795,845395490,877658697,487989369,41815820,370999052,715657404,424629988,971901418,675258797,949238642,89183561,285201003,68493027,934281721,115836197,329796660,170688640,246971298,275105629,44673585,151904385,11034295,736481265,325912072,312363713,708382039,337778689,267512809,252551589,956613828,497985400,409094906,320060926,554917439,250993499,749521773,853329772,754948228,754363835,324458366,199336973,759415866,375598506,909210595,700755004,907013091,878065545,394359162,719566487,19360802,538410830,782386712,568881907,424989675,560500372,830324646,501026094,268675400,50590510,930059515,932297089,747776616,229386209,198768464,241822340,515625587,789870803,861828251,99199382,811051461,739303690,338230961,474683954,747407118,363810556,938222670,393708383,396133072,497196934,806683867,927957338,294813632,795382466,726997875,569565538,59049178,477072797,342634621,296229203,609696820,621340527,469448617,477527263,703397904,48845205,140231825,961921035,612842106,732868367,376263315,415616232,942401605,800362473,26031303,48755035,632078189,150230048,802627671,216665960,908760486,701253820,106460787,341934027,352946234,814053802,765506212,982076387,965931947,733333339,432445966,847302953,270177936,563443841,459878625,208372493,748932782,183753738,62568726,16634739,818220387,361648749,268151658,298852345,68718097,294891752,315170969,53792521,827351663,404206040,793946555,404917720,321673283,184607674,97830135,545104222,378307888,206861090,989655902,31131935,602293534,389038888,699689146,316227381,864326453,96158832,958542649,170961663,530328239,167831173,753712331,817219959,229070827,628303842,718498895,559961787,707233111,657496548,288199605,608823837,249236264,262774210,229265100,243591881,385388084,9582985,20303770,562008185,636134163,681756977,565417478,657564216,53730313,578460779,313132653,781307067,379008804,282185454,263223296,442795120,632289515,457210799,976656728,636009706,256141983,268795108,452130570,620695667,186801565,636578562,366772204,859354557,191659036,18081311,553033642,863225538,555731982,553084997,829373573,919273670,9051229,809437256,903263782,34185477,326686486,94825580,231310558,379278321,482926441,141827977,365864597,111873860,123637707,176377554,693305776,540005807,292411226,898227295,950055170,186576440,50118951,259165544,650817063,96594580,565456578,296527297,220797542,813409093,26724420,519397500,181681081,701572379,663329044,362041517,696628828,795808108,796426218,587068363,148505764,370732451,278185962,573509777,277209248,514994610,915265013,501404039,681242817,745638450,105200925,923043932,407356104,763025936,2989898,394923655,777901604,488630304,243034420,89120113,800607974,637939935,395358411,907816292,982937783,719072900,490676632,471929788,621887590,292909707,238296988,462528877,369525491,38124644,808722011,428387930,798895521,75853166,508267768,641108112,761776308,699767918,525486772,696896168,449939558,149268478,811575797,512277222,112891394,665736716,168631060,606870929,463528680,154281667,785149129,151054828,179111720,237769647,593926876,482335897,993649414,508038818,771818046,83264202,723407599,812668005,752550134,883929124,988557002,67620895,121061403,848924691,319954157,871705611,427351467,152373822,34629406,491671763,254524151,570308920,544811678,435904287,849489362,589672369,847509284,548430222,208184231,181134117,874464388,200377679,767288966,206330671,596844380,752825233,753134199,539562642,131772368,544099511,194916555,256255312,146162018,648711554,584495484,197533041,687257851,360777215,523696723,792476159,246329273,8300915,295294842,25058942,865177945,486033494,304038136,845991325,817928963,152438502,461763427,235481106,837898265,724464507,835830978,551315810,697617046,921015986,701453022,721919690,490065418,154495299,72509488,281230685,510446188,181224475,521329716,607307402,596949867,498928970,145135624,930570143,467192613,303076380,366069684,677309335,771759239,936868840,272814771,17704676,670999343,993602760,193370243,48824684,757819171,880826935,955098935,450039887,939889684,443114259,886867149,759427018,955654747,48527183,445129483,188875807,715555451,365537558,484458461,580929149,232629505,529700323,673032615,326159309,313027690,425343432,455315503,60511994,668422905,750208636,210143574,810028347,477169522,965656187,369499175,801756649,590906591,226784434,359960756,729604909,251867424,65822009,222489048,407934361,120587974,460076831,595916891,50253054,456152084,694188722,207214810,895560303,891996014,124804049,751677875,107094470,168655116,127290321,920251227,10679073,323940868,817279053,424610493,483924582,984402270,807755216,248636352,342008720,167087470,873784528,157167077,574400690,989612191,903466878,558765053,279153607,849646812,11779782,368114731,614562174,192200875,432824950,588320903,388728584,605240,22602811,337060250,36228319,249153339,960535678,87626727,493952635,307920342,322908524,242283503,877718665,466501375,658442906,92255682,169999754,930731151,454538013,931433486,15570863,930762614,564730215,243133049,782066883,744158074,796850043,526627922,306534040,920947137,334326205,849929912,239473327,483405622,334547062,98349682,262989398,184790555,958445403,783054273,769795511,820483088,909017757,932616287,768208088,888146074,362567344,732526251,548032144,931021597,582627184,971149798,880462874,912118240,644572432,919419361,371739314,370692399,222125557,944154377,986708498,835585917,30384659,940526817,648517190,373745190,629489405,113312623,834203858,116940940,256853930,423574692,162638132,526240263,121163959,702823274,250642319,494063841,489134659,129015470,308186532,351359004,690998709,37542184,75147725,180350107,612015056,552162842,593443248,823246366,606241871,897002443,94230023,21430807,618924870,273712630,25534662,366267355,442310407,661225829,682189174,787940705,64685867,337651405,988034294,946867127,655392623,921736853,638544222,100107979,502371023,905845514,790485759,413972507,257426299,825871994,848886378,756445317,972951283,60331080,701506133,96436642,177546793,494271604,885681419,341779962,799261956,848518926,24345594,488335568,815463367,869492348,649106694,607061640,124722795,49187570,446331630,454804469,928529467,494966152,957939114,337515306,351235669,880615277,828744337,933376898,989183409,985593892,725055952,837168087,338121343,147503783,364396002,886677604,719537828,869630152,426305490,458037451,412687469,685092513,632627667,317246521,807947426,20121898,825283988,435887178,500860184,510020354,982966892,146168758,129621197,405196353,973851619,164164627,76050898,827722926,868946348,800461354,761123504,299417930,918513230,527015648,868169900,988894879,884369503,547838438,914861719,174368041,217650875,724929305,852304035,783630094,750642922,262218995,581282403,689189630,664079643,363994545,626539241,810853769,567033437,130223610,380766745,145628232,660389112,212842957,59476749,616831860,378430921,350285832,404149413,558661806,423750826,202330828,620676040,663307737,808454200,546696895,963774716,965328448,206282795,996017320,330624860,16741224,580069277,488906585,30569161,80281513,336908710,450727414,280700600,96079152,107971406,34566831,411765386,534279149,830184839,56838370,826025098,401776532,375297772,517845614,148428940,649876656,979071936,922377372,474115783,310792516,156910777,749805383,219932130,136961239,205625235,200048852,73943059,701050258,684265803,552965451,206241913,692292858,863002719,812982323,790641838,201252328,352817240,217598709,480698499,876412019,442413206,832120781,810551911,767557384,361003283,709545031,448564967,247844667,432551669,854684600,232511639,390009248,812283640,595405397,770779245,594845000,374647549,857241854,567393268,789013621,828454750,62553593,624148346,621725636,621143544,741504235,98533460,564827277,652975242,977482822,934007482,905426828,478982047,229040223,409534564,834121669,133770918,454039189,63767449,110933513,117263578,544744689,48562889,472970036,276850119,492337064,856718199,671734977,75057840,664888764,809192204,419328516,508831870,410260274,361191448,677880815,314836111,897162044,636998925,886004348,653085093,120855817,892168027,488676042,831017977,981671640,927715727,277714559,694383920,287466494,902649100,921742704,624500515,494570163,556926990,363293787,216856467,808691930,67853838,825214384,996283144,205394803,895205045,523665938,517718457,818574611,427084870,628829100,143380801,759002288,364455291,837453770,919717789,727771800,140909847,15369004,966548302,748510389,699766608,130016019,594901690,661412735,574455974,452410737,28726649,368429004,431184348,172096141,316340630,33107859,865506733,876108626,581418893,523597876,797757269,793616977,160630660,15391652,815626120,393720508,412237041,241071717,203191898,552822041,417942539,81856390,277650223,880691101,625278603,197666986,501938887,569600455,986598821,607363865,870740081,481923877,214956689,264688936,449958460,41076631,770162507,183658929,785804644,954270606,604867835,495838143,219425152,423951674,119813352,268343768,923820379,341205900,696623384,830126743,286246546,934953895,183229029,161960209,910171678,326083992,908732533,13527023,541120825,941211285,31728844,832712633,142493387,841656666,282938781,540979506,169823238,961773117,629786193,230477028,794471639,50055621,221210182,269571439,587183657,513958026,565647910,831650763,76770272,199774070,302464254,644042531,365500410,421943723,549348080,655814211,397780223,825689399,751040886,55212870,580413046,633010409,895966774,672850561,671006344,713879575,283738625,218139373,493689107,321889979,214217407,919788603,79499595,100228913,810904041,162490176,957200574,683285538,639655136,181994733,960676473,21121378,823154790,929893103,642380089,941348051,445446563,902980332,814362881,427675611,314431839,345167956,617304201,406024012,726229501,472901360,249429164,674533527,10065330,196741756,753152516,849578441,468928447,983737173,915099068,849525756,114886454,430048364,551060742,143407998,179435628,539765360,494268880,823845496,428887477,240477416,313294171,193434473,946421040,63641538,394899231,434031342,443618781,842203531,95905616,353782904,996380924,653867289,894247956,823173026,267728794,862941821,975226699,885362182,411820693,983946932,864162465,978954289,116667533,791371507,484444661,894838313,616418505,241427979,961319002,273943424,704279434,329834703,281804989,220356705,55398199,450861796,118238106,563796647,630585326,75201573,294139525,626642230,774625892,768834255,146628973,182299808,116225473,256473217,702144552,795985707,641863188,969473023,918860977,2947098,745744394,505255660,325145582,753513874,406578925,471703615,144571505,21686669,304644842,837580332,219698501,377516953,75061610,161362528,294206968,976521022,270285846,451709693,627655552,355876825,923770521,441274033,800849785,799289297,657258899,352886272,338657310,535099780,816701166,407896543,128635371,579659907,578690901,787113234,164950881,744064735,450562136,976366438,701220427,144453590,242444386,576861374,655829165,245795606,43209047,760649561,215263617,347049376,10475577,646820311,360639233,672056268,88327015,759404319,275928212,43792231,77927268,978578801,491466901,987488759,815053082,908499163,943554485,114495791,704711488,865233543,52347419,999091970,586445753,768945489,467351091,410651368,368295944,718623833,301479375,218494741,35795743,662334405,66547751,858133770,45194888,451790389,671164082,351472920,359808887,407003192,7603723,856523182,494166907,677692576,140475489,840570768,640321280,172114298,154345160,870605651,645545349,443215535,364380585,818312619,878161899,897560127,284440679,965683742,907002124,694688662,453026551,827102807,117483873,699952443,469449264,119067966,370019264,237120480,229619983,259773735,964404181,109152123,193781724,638406068,605076602,714457410,381785483,107141741,224849215,866444111,279355497,343331898,793307102,25469363,657738639,3624695,231276098,236455213,901161015,114049054,386979036,289805123,14162538,506228345,609048943,344492349,366746787,778983779,210337196,599368778,991853918,575349415,49389215,82441236,855143395,188880105,492881183,859637374,505825384,500512522,260616058,29878651,713258160,905773713,371429170,445933418,780699748,923333660,3991476,80563352,757901773,364058973,83868974,817729704,359056292,293714317,872372077,217298111,302862755,113646516,19270208,844172795,176966527,258450659,129724336,950540131,186631946,105359006,245338485,808138529,629602874,73691665,10430738,802245045,906169092,826784106,58085060,315103615,282183879,300834556,937290323,832860641,708233401,311568885,636346220,525040405,407154607,946149627,841250413,733904456,514349511,25454838,281329488,205004338,483562350,946781127,4283891,31503476,567255816,354893353,960458533,468399808,965785236,387255176,701918934,633400565,942140453,916291845,668677123,178909003,747296925,437155518,899946391,43744543,929269243,775543604,381350331,512634493,339271869,687740343,924265341,789825490,121000338,171989322,490484575,644960213,63126637,492741665,510950308,916660987,343799473,271361010,165393390,302780015,682610501,114644779,473979326,917041303,207172258,492897596,745391035,429707160,741626808,877891340,53635336,348421260,73903881,536841269,30514807,875410153,386541987,953786104,377329025,599685896,845486631,894553004,371930700,859917803,389995666,379943099,888140011,802932692,373451745,639054294,756614559,925139828,557583419,823495900,578471809,676216445,78835193,120815665,73146164,630786699,291993453,585347275,707764537,847549272,384826244,247001105,550507082,378750527,646654592,946033733,616017573,999340546,85104325,205951465,676290554,765080455,95568681,434360362,780882948,385914044,723091468,35784547,696559662,598245292,139066955,547380283,306032293,590393084,698611116]


T = int(input())

def fact(n):
    N = n//(4 * 10**5)
    ret = table[N]
    for i in range(N*(4 * 10**5)+1,n+1):
        ret = ret * i % mod
    return ret

def inv(x):
    return pow(x,mod-2,mod)

for _ in range(T):
    C,P = map(int,input().split())
    if P >= mod or P*2-1 > C:
        print(0)
        continue
    a = C-P+1
    b = C-2*P+1
    a %= mod
    b %= mod
    if a<b:
        print(0)
    else:
        print(fact(a)*inv(fact(b))%mod)