結果
| 問題 | No.2996 Floor Sum |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2024-12-20 11:07:28 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 4,165 ms / 5,000 ms |
| コード長 | 37,419 bytes |
| コンパイル時間 | 335 ms |
| コンパイル使用メモリ | 86,272 KB |
| 実行使用メモリ | 141,040 KB |
| 最終ジャッジ日時 | 2024-12-21 18:06:53 |
| 合計ジャッジ時間 | 18,131 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 126 ms
78,464 KB |
| testcase_01 | AC | 1,313 ms
93,800 KB |
| testcase_02 | AC | 237 ms
79,980 KB |
| testcase_03 | AC | 3,900 ms
141,040 KB |
| testcase_04 | AC | 1,451 ms
91,900 KB |
| testcase_05 | AC | 1,140 ms
90,096 KB |
| testcase_06 | AC | 1,596 ms
101,216 KB |
| testcase_07 | AC | 322 ms
80,880 KB |
| testcase_08 | AC | 896 ms
87,408 KB |
| testcase_09 | AC | 582 ms
83,948 KB |
| testcase_10 | AC | 468 ms
82,284 KB |
| testcase_11 | AC | 258 ms
79,588 KB |
| testcase_12 | AC | 634 ms
84,848 KB |
| testcase_13 | AC | 4,165 ms
139,408 KB |
ソースコード
R=range
class ModB:
B = 998244353
length_bound = 10**6 #User definition
length_max = min( length_bound , B )
inverse=None
factorial=None
factorial_inverse=None
def SetModulo(B):
ModB.B = int(B)
assert(ModB.B > 0)
ModB.length_max = min( ModB.length_bound , ModB.B )
ModB.inverse = [None,1 if ModB.B>1 else 0]
ModB.factorial = [1 if ModB.B>1 else 0]
ModB.factorial_inverse = [1 if ModB.B>1 else 0]
def __init__(self,val,valid = False):
self.val = int(val)
if not valid and not(0 <= self.val < ModB.B):self.val %= ModB.B
def ref(n):
return n if n.__class__ == __class__ else ModB(n,True)
def get(n):
return n.val if n.__class__ == __class__ else n
def copy(self):
return ModB(self.val,True)
def __str__(self):
return str(self.val)
def __eq__(self,x):
return x==self.val
def __ne__(self,other):
return not( self == other )
def __iadd__(self,x):
self.val += ModB.ref(x).val
if self.val >= ModB.B:self.val -= ModB.B
return self
def __add__(self,x):
a = self.copy()
a += x
return a
def __radd__(self,x):
return ModB(x + self.val)
def __neg__(self):
return ModB(ModB.B - self.val if self.val else 0,True)
def __isub__(self,x):
self.val -= ModB.ref(x).val
if self.val < 0:self.val += ModB.B
return self
def __sub__(self,x):
a = self.copy()
a -= x
return a
def __rsub__(self,x):
return ModB(x - self.val)
def __mul__(self,x):
return ModB.get(x) * self
def __rmul__(self,x):
return ModB(self.val * x)
def __pow__(self,n): #Supported only if n>=0.
answer = ModB(1)
power = self.copy()
while n > 0:
if n&1:answer *= power.val
power *= power.val
n >>= 1
return answer
def __xor__(self,n): #Supported only if B is a prime and val!=0, or n>=0.
return self ** ( ( n * (2 - ModB.B) )if n < 0 else n )
def Inverse(n): #Supported only if B is a prime.
if n < ModB.length_max:
while len(ModB.inverse) <= n:ModB.inverse+=[ModB.B - ModB.inverse[ModB.B % len(ModB.inverse)] * ( ModB.B // len(ModB.inverse) ) % ModB.B]
return ModB(ModB.inverse[n],True)
else:return ModB(n) ** ( ModB.B - 2 )
def __truediv__(self,x):
return ModB.Inverse(x) * self
def __rtruediv__(self,x):
return x * ModB(ModB.Inverse(self.val),True)
def Factorial(n):
while len(ModB.factorial) <= n:ModB.factorial+=[ModB.factorial[-1] * len(ModB.factorial) % ModB.B]
return ModB(ModB.factorial[n],True)
def FactorialInverse(n): #Supported only if B is a prime.
while len(ModB.factorial_inverse) <= n:ModB.factorial_inverse+=[ModB.factorial_inverse[-1] * ModB.Inverse( len(ModB.factorial_inverse) ).val % ModB.B]
return ModB(ModB.factorial_inverse[n],True)
def Combination(n,m): #Supported only if B is a prime.
return ModB.Factorial(n) * (ModB.FactorialInverse(m).val * ModB.FactorialInverse(n-m).val)if 0<=m<=n else ModB(0,True)
ModB.inverse = [None,1 if ModB.B>1 else 0]
ModB.factorial = [1 if ModB.B>1 else 0]
ModB.factorial_inverse = [1 if ModB.B>1 else 0]
def Log(n):
a=0
while n>1:n>>=1;a+=1
return a
s=[
[0,1],
[0,499122176,499122177],
[0,166374059,499122176,332748118],
[0,0,748683265,499122176,748683265],
[0,565671800,0,332748118,499122176,598946612],
[0,0,415935147,0,915057324,499122176,166374059],
[0,308980395,0,831870294,0,499122177,499122176,855638017],
[0,0,582309206,0,956650838,0,83187030,499122176,873463809],
[0,565671800,0,887328314,0,931694729,0,665496236,499122176,443664157],
[0,0,549034394,0,499122177,0,898419917,0,249561089,499122176,299473306],
[0,892369952,0,499122176,0,1,0,998244352,0,831870295,499122176,272248460],
[0,0,915057324,0,374341631,0,831870296,0,374341631,0,415935148,499122176,582309206],
[0,247549973,0,665496237,0,99824432,0,855638020,0,166374057,0,1,499122176,460728163],
[0,0,111708295,0,915057329,0,549034387,0,891289606,0,515759580,0,582309207,499122176,926941185],
[0,166374060,0,188557259,0,166374074,0,99824421,0,277290106,0,565671797,0,166374060,499122176,865145106],
[0,0,249561097,0,457528633,0,415935185,0,811073510,0,415935159,0,457528658,0,748683266,499122176,935854081],
[0,624392049,0,665496282,0,266198402,0,665496322,0,332748070,0,332748135,0,332748113,0,332748119,499122176,939524097],
[0,0,815232828,0,332748316,0,421480688,0,166374243,0,565671719,0,221832103,0,332748112,0,915057325,499122176,720954255],
[0,203902097,0,898419556,0,714,0,655988475,0,332748486,0,199648738,0,34,0,598946605,0,499122178,499122176,105078353],
[0,0,439703392,0,274515479,0,2261,0,434947731,0,831870994,0,149736443,0,855638063,0,274517189,0,83187031,499122176,149736653],
[0,293422811,0,602119123,0,99817563,0,6460,0,301054278,0,604997850,0,998244030,0,808102633,0,499122167,0,665496237,499122176,617960790],
[0,0,585328633,0,415953425,0,848483647,0,499139134,0,33267372,0,559624061,0,499121692,0,249561169,0,415935136,0,249561090,499122176,136124230],
[0,947614962,0,632180681,0,831950717,0,99748840,0,665537687,0,66534744,0,332751886,0,199648160,0,499122281,0,166374046,0,831870296,499122176,217009642],
[0,0,915128533,0,889866945,0,360785415,0,286777915,0,831965633,0,127524926,0,831876485,0,286994230,0,360477261,0,890101200,0,415935149,499122176,291154603],
[0,247463393,0,333317793,0,278383924,0,523946885,0,431992989,0,208012,0,926522877,0,332758023,0,698769605,0,665496404,0,732045842,0,2,499122176,319438193],
[0,0,597681530,0,835430765,0,827184899,0,15186942,0,580860296,0,333181476,0,157138608,0,582324683,0,582307203,0,831870505,0,831870275,0,582309208,499122176,729486258],
[0,167799576,0,521432946,0,351262566,0,648093339,0,43873388,0,828445598,0,666362952,0,871320199,0,831893965,0,166371318,0,411974121,0,332748096,0,166374061,499122176,480636170],
[0,0,268805570,0,25817150,0,582437194,0,66045769,0,917053630,0,366636066,0,1671525,0,659279299,0,748718771,0,124776844,0,641728833,0,374341608,0,748683267,499122176,962592769],
[0,56462502,0,179615163,0,144576040,0,333260070,0,316391765,0,65581165,0,482525572,0,3120180,0,498669226,0,52325,0,499117243,0,390,0,99824408,0,332748120,499122176,481911067],
[0,0,818706279,0,553526667,0,33287958,0,459384489,0,418413942,0,75300786,0,714304584,0,754338591,0,914327570,0,748759136,0,249554585,0,748683736,0,648858799,0,915057326,499122176,432572553],
[0,509507086,0,201107966,0,326426943,0,56341,0,533037277,0,324383553,0,864863289,0,430364815,0,509102164,0,497969934,0,499230564,0,499113694,0,499122742,0,166374025,0,499122179,499122176,128805723],
[0,0,909649362,0,61220207,0,189172676,0,624121042,0,753995641,0,588429757,0,275081560,0,771441557,0,765871021,0,871677833,0,521962276,0,561501492,0,748683939,0,790276742,0,83187032,499122176,967049217],
[0,481741584,0,718727351,0,791107066,0,864789376,0,111692293,0,378452132,0,66257990,0,919588779,0,688761955,0,28947800,0,377562076,0,726208384,0,798581458,0,443664956,0,665496194,0,665496238,499122176,756245722],
[0,0,961025665,0,189595616,0,358111451,0,572523117,0,69111261,0,42499010,0,298785884,0,212114511,0,98111839,0,47763870,0,566343114,0,292175,0,399279941,0,522890841,0,931694684,0,249561091,499122176,968884225],
[0,535945330,0,243684438,0,690303577,0,455941451,0,831872638,0,939612518,0,648667447,0,211400639,0,424229022,0,175568554,0,77331980,0,706997079,0,397358,0,133076832,0,475355558,0,732045809,0,831870297,499122176,370776474],
[0,0,394844098,0,634872303,0,865663748,0,871718951,0,915065527,0,577673746,0,124302088,0,649609714,0,824889765,0,806367146,0,123028150,0,157573598,0,534905,0,166346040,0,887329602,0,207967519,0,415935150,499122176,859599304],
[0,128883146,0,745151764,0,378454299,0,744220250,0,492142745,0,635273254,0,601467559,0,897271623,0,142518723,0,407087146,0,526705662,0,192565800,0,186976207,0,666209442,0,998209571,0,1496,0,499122117,0,3,499122176,242816194],
[0,0,387849495,0,903187699,0,836434981,0,197724509,0,323561627,0,794140788,0,92226305,0,889525459,0,126581094,0,54340173,0,341326239,0,296872275,0,841991729,0,666438687,0,598903714,0,249562818,0,748683200,0,582309209,499122176,551661353],
[0,332059229,0,919782858,0,76164912,0,832882300,0,945752855,0,573261428,0,785574068,0,899136208,0,990106673,0,253162188,0,240936173,0,129911024,0,451245858,0,1920978,0,666731172,0,798542898,0,831872286,0,99824365,0,166374062,499122176,486324172],
[0,0,984811024,0,482805865,0,495071928,0,566445977,0,194580899,0,864855288,0,477108870,0,195155801,0,980612713,0,294017396,0,18741435,0,211105414,0,676868787,0,73978816,0,667101653,0,37370076,0,249563373,0,690452268,0,748683268,499122176,573990503],
[0,289914080,0,486385182,0,867713861,0,119462059,0,742881048,0,72320499,0,741392515,0,274045967,0,459190120,0,750968405,0,655104026,0,32593800,0,537417533,0,337272338,0,997017442,0,667567742,0,499044495,0,855640628,0,665496153,0,332748121,499122176,97389693],
[0,0,952016875,0,493348527,0,106285991,0,237901420,0,450376979,0,995778303,0,388641735,0,265510886,0,491352855,0,291679789,0,676378765,0,55681075,0,732284069,0,137347226,0,231246904,0,418589265,0,748589590,0,419899408,0,166373970,0,915057327,499122176,308980395],
[0,155408555,0,351059661,0,550447956,0,637715946,0,777458509,0,358378893,0,222396843,0,89952505,0,362366791,0,718374181,0,583359578,0,410489801,0,93544206,0,251780238,0,130072234,0,442107980,0,442000487,0,898307508,0,665499611,0,332748022,0,499122180,499122176,510729669],
[0,0,845673050,0,30475032,0,950143959,0,682551239,0,448162965,0,36385592,0,896985522,0,54576541,0,255615785,0,995470095,0,777204865,0,943428467,0,1131671,0,30146668,0,718833857,0,469302054,0,647081000,0,407482177,0,831874114,0,307791906,0,83187033,499122176,68062115],
[0,888359911,0,757020615,0,68531411,0,410686347,0,120352031,0,794407507,0,891031506,0,235371084,0,493578466,0,14021403,0,374470832,0,792395844,0,23313363,0,704312453,0,975139687,0,666064575,0,625736072,0,670866921,0,565512131,0,221836388,0,232923572,0,665496239,499122176,288381702],
[0,0,522333114,0,780088183,0,14863406,0,438402540,0,42461963,0,732978357,0,154509454,0,911542262,0,235701812,0,281109245,0,130716659,0,986620031,0,616260255,0,98034791,0,963587354,0,343945724,0,534578815,0,589022563,0,748494183,0,748688113,0,249560970,0,249561092,499122176,108504821],
[0,904833245,0,23152924,0,987696295,0,240280147,0,576983505,0,903564102,0,213186883,0,939676357,0,763638695,0,990959904,0,853440335,0,261433318,0,138330344,0,606260722,0,362036776,0,367192085,0,993686585,0,987801972,0,840216630,0,498899157,0,499127616,0,499122050,0,831870298,499122176,191153174],
[0,0,799572021,0,272046857,0,582869781,0,787743143,0,216211591,0,45104164,0,216576645,0,77517600,0,52914795,0,531915939,0,325892368,0,96038434,0,864362916,0,803742422,0,434091702,0,695289055,0,991943909,0,624134117,0,93510129,0,511338183,0,273334898,0,124780409,0,415935151,499122176,644699478],
[0,368749953,0,814220100,0,215863380,0,574269288,0,873815586,0,126723381,0,320114506,0,693045264,0,688635272,0,343836188,0,645382516,0,593319346,0,423972438,0,538400831,0,986110094,0,446731975,0,648331588,0,105444460,0,27279767,0,345453471,0,598639824,0,142613131,0,266198350,0,4,499122176,692659347],
[0,0,549296848,0,989997048,0,764639917,0,522666330,0,488367830,0,767014894,0,122156418,0,125962415,0,654541809,0,642749790,0,76200577,0,129928949,0,645448925,0,692640366,0,878600628,0,964814561,0,170996901,0,587185783,0,849533777,0,847434352,0,698413128,0,7567,0,66549470,0,582309210,499122176,658841273],
[0,3453945,0,836244525,0,915771303,0,613098264,0,241716892,0,404864040,0,646416470,0,407188060,0,194316923,0,198842327,0,674718626,0,469466927,0,259857898,0,677667604,0,402496489,0,805270603,0,947593153,0,101674951,0,955371764,0,116497524,0,351728676,0,997828168,0,110924447,0,665496072,0,166374063,499122176,313174699],
[0,0,587197774,0,929235252,0,297223428,0,913768374,0,833458408,0,722427817,0,358314149,0,50106500,0,716938674,0,57837975,0,112128665,0,124153411,0,279357180,0,378685119,0,584419596,0,753082711,0,922267553,0,559974661,0,756817708,0,448007649,0,854918115,0,249078692,0,665505557,0,207967400,0,748683269,499122176,364743129],
[0,694992202,0,528399337,0,80900832,0,68850423,0,621076958,0,310005736,0,893222562,0,177361740,0,975350526,0,753746891,0,285824179,0,687527570,0,298168869,0,759853314,0,334799402,0,690503865,0,944677156,0,29726519,0,921889301,0,343594042,0,56908935,0,360619901,0,332190682,0,332758431,0,831870110,0,332748122,499122176,828731161],
[0,0,448894999,0,762264009,0,714624016,0,81792420,0,496623689,0,38199530,0,101539682,0,837071852,0,542628614,0,450150514,0,370953228,0,436858668,0,646199785,0,511352588,0,524929320,0,738110258,0,4578577,0,736989287,0,681592443,0,405349888,0,510488,0,139447231,0,165731796,0,804152672,0,682133446,0,915057328,499122176,240318085],
[0,773373544,0,94155158,0,845443085,0,806804745,0,490754520,0,169233671,0,772979188,0,964489467,0,545004900,0,123649875,0,16679204,0,567120167,0,983544497,0,294155217,0,676796032,0,44954379,0,663319866,0,976787176,0,967687678,0,636591274,0,509528039,0,975670446,0,766283289,0,997506434,0,356528390,0,898419711,0,499122181,499122176,54449692],
[0,0,304641047,0,795511246,0,595810416,0,680341401,0,702661154,0,692467296,0,184577230,0,507870300,0,667048397,0,90476068,0,41698010,0,259812515,0,583208368,0,43031130,0,575296490,0,170850747,0,779416150,0,937733545,0,559973763,0,126629737,0,643471376,0,720465881,0,547291889,0,186325284,0,392181229,0,623902502,0,83187034,499122176,980418561],
[0,495058659,0,29914877,0,524473390,0,773505916,0,240257972,0,763949971,0,832871284,0,23592090,0,28817348,0,232244557,0,906765750,0,926162229,0,382331163,0,285317029,0,151939034,0,73202350,0,380678027,0,248821487,0,313109731,0,573700809,0,416431922,0,768364279,0,186717112,0,57393700,0,498155854,0,15158,0,998244122,0,665496240,499122176,700522353],
[0,0,632873016,0,176725909,0,989519793,0,20885710,0,570874958,0,384468215,0,396242883,0,458388453,0,424003053,0,13038158,0,352858919,0,327927132,0,262277346,0,687778704,0,89035294,0,192781958,0,784996156,0,310780325,0,968786773,0,792567544,0,137338600,0,382821963,0,101161071,0,317716107,0,48810610,0,499138792,0,166373815,0,249561093,499122176,740077710],
[0,185278999,0,256612740,0,253180709,0,355529797,0,245512837,0,106084388,0,486711294,0,334245924,0,37186888,0,611315815,0,701506386,0,716210430,0,680931398,0,8830399,0,377313055,0,37776440,0,308579067,0,701904161,0,460189581,0,314535418,0,220338451,0,162032429,0,426865351,0,188554791,0,579795464,0,897167109,0,18183,0,266198237,0,831870299,499122176,727534020],
[0,0,973630882,0,790304856,0,659495658,0,750324091,0,350456950,0,854329692,0,767683428,0,483848580,0,565554512,0,555576213,0,792318741,0,13756356,0,9429937,0,838593345,0,908423067,0,818333576,0,740996336,0,512575705,0,740774464,0,114554218,0,856180684,0,421457102,0,873015674,0,294155536,0,843877744,0,422832394,0,942806200,0,440890985,0,415935152,499122176,715408453],
[0,10126758,0,505974933,0,499459095,0,946810833,0,676435077,0,822589524,0,487598895,0,76000653,0,122253957,0,472482205,0,18690911,0,981870245,0,232664125,0,242787494,0,840043018,0,534583826,0,761883336,0,129428744,0,345571458,0,371772750,0,265030012,0,126781414,0,229194685,0,328636157,0,686147792,0,111993505,0,497512981,0,665517908,0,831870009,0,5,499122176,654586461],
[0,0,308866119,0,478846169,0,585734544,0,606063763,0,233100993,0,188519335,0,627171513,0,726484394,0,913427253,0,193265284,0,97199542,0,457504652,0,430683791,0,885445738,0,842942364,0,707099058,0,251223473,0,108393777,0,449654777,0,816514532,0,479995432,0,584137832,0,716250402,0,895967202,0,757240758,0,880060261,0,580491411,0,938848654,0,582308906,0,582309211,499122176,563525038],
[0,319156225,0,393767008,0,746821860,0,624531776,0,736708707,0,950844014,0,361576023,0,795469085,0,359441333,0,774011940,0,665663634,0,739437369,0,815173344,0,915033568,0,584977598,0,687640375,0,148745813,0,958407248,0,802163089,0,49339564,0,406916902,0,111711813,0,960094579,0,413859917,0,74311432,0,920567196,0,652808474,0,763271520,0,530838152,0,831869979,0,166374064,499122176,205986930],
[0,0,570099734,0,212364258,0,853919059,0,925210324,0,947760748,0,499831485,0,129725574,0,948500000,0,758922489,0,441648905,0,726475262,0,318876020,0,900195338,0,62336822,0,629506344,0,74791411,0,539858394,0,678968331,0,515544728,0,976129731,0,610375353,0,91888890,0,338368752,0,480800869,0,652649242,0,424210320,0,96113651,0,858680460,0,748711157,0,723726825,0,748683270,499122176,982646785],
[0,549693494,0,848691658,0,921422667,0,819549497,0,35227101,0,523022587,0,848160279,0,753144653,0,165048678,0,87029195,0,442804153,0,111811532,0,417024870,0,765831873,0,378526451,0,365784509,0,447548298,0,644914428,0,257126086,0,974002163,0,720249735,0,745960747,0,463434539,0,248365034,0,281655135,0,662423464,0,625262766,0,148141134,0,596358211,0,30256,0,399297394,0,332748123,499122176,890741115],
[0,0,894884554,0,314940677,0,498757539,0,544593001,0,728098333,0,254241101,0,301425438,0,252087910,0,596009115,0,532405972,0,809162821,0,469196958,0,44317822,0,886534390,0,653766585,0,836585192,0,562005760,0,498932593,0,597438466,0,709289706,0,187731024,0,580177919,0,329338690,0,793856312,0,865273852,0,828029330,0,641715068,0,635420123,0,995343559,0,332780895,0,998243989,0,915057329,499122176,378122861],
[0,434007005,0,720817481,0,363888395,0,709593670,0,333452713,0,375612586,0,906822377,0,926974186,0,156610654,0,284015452,0,675031559,0,65045210,0,200505842,0,219248493,0,503052352,0,232638642,0,674926031,0,774569618,0,242478018,0,166381413,0,825266927,0,613155082,0,784377991,0,568671815,0,824807844,0,708724369,0,70556109,0,570409211,0,945906322,0,994999397,0,35464,0,665495854,0,499122182,499122176,432075914],
[0,0,64691549,0,344321659,0,902313293,0,702064133,0,537117777,0,932551860,0,132905888,0,13507536,0,804771735,0,552154023,0,104663967,0,264771574,0,363112077,0,988100915,0,857285092,0,799038517,0,948319632,0,498773789,0,900379620,0,103996105,0,294485165,0,253046816,0,79116350,0,24291053,0,785804318,0,625208989,0,364831937,0,236809077,0,989418232,0,395674207,0,38324,0,540715292,0,83187035,499122176,983564289],
[0,829021404,0,800845542,0,889446021,0,779374308,0,91430717,0,234881894,0,193893919,0,70109704,0,54030144,0,200737683,0,219257615,0,5627795,0,959757326,0,803588451,0,595815330,0,238223363,0,345760969,0,501950011,0,431032954,0,187708182,0,683777233,0,581772395,0,138366569,0,709164972,0,13337699,0,714990973,0,255945755,0,324015659,0,912979192,0,40585709,0,195609521,0,633847304,0,765320253,0,665496241,499122176,405084665],
[0,0,650396554,0,338286834,0,745307888,0,233515112,0,531047512,0,851448714,0,599104189,0,801470275,0,207115552,0,742457224,0,733046354,0,390521543,0,934499718,0,19434418,0,372130906,0,45742086,0,437450226,0,878883825,0,152194983,0,174059961,0,766832471,0,390515344,0,706672030,0,769863559,0,477598427,0,392024825,0,49751700,0,559665708,0,53463846,0,96585783,0,394802336,0,59463904,0,482484334,0,249561094,499122176,185388237],
[0,790748811,0,535002416,0,743038264,0,465368409,0,374320139,0,929157119,0,284594324,0,466582725,0,716480454,0,447822238,0,811116825,0,277923865,0,294864838,0,93540223,0,976310579,0,614885579,0,913774047,0,874900452,0,556590521,0,119594428,0,978903394,0,17937727,0,163804156,0,75485146,0,814592412,0,577233578,0,385925043,0,426318292,0,109377823,0,943240264,0,159930129,0,327753223,0,831918322,0,831869838,0,831870300,499122176,702988981],
[0,0,619863083,0,512093707,0,141168398,0,261947762,0,361710975,0,90356042,0,445055433,0,885045673,0,164132405,0,292051286,0,485082272,0,531036831,0,881995854,0,486752368,0,547036680,0,958740610,0,117207406,0,394505643,0,803519153,0,312104545,0,989316645,0,732253490,0,383033939,0,652370803,0,477915065,0,596175779,0,784710062,0,897026532,0,908393471,0,650320281,0,231447939,0,597564752,0,471444833,0,956650362,0,415935153,499122176,429799652],
[0,405173336,0,901293050,0,785736651,0,453773455,0,99093390,0,734071986,0,807585572,0,339426243,0,49052601,0,569436253,0,145680678,0,997695276,0,770720365,0,355500238,0,313510942,0,916321067,0,730555395,0,982665326,0,605809194,0,101235486,0,523738607,0,797575753,0,173361231,0,820407053,0,245553989,0,498542853,0,565046783,0,337560710,0,502616028,0,347175153,0,538485890,0,977543611,0,692633090,0,55522,0,998243856,0,6,499122176,382888245],
[0,0,813405822,0,975810691,0,76474567,0,272485909,0,723381747,0,971749346,0,75398163,0,862339241,0,698057725,0,431339141,0,483394977,0,539045582,0,820155165,0,712930402,0,696327002,0,283320,0,658381438,0,717092460,0,901095464,0,35018109,0,743933520,0,665316903,0,36406130,0,478222371,0,378473711,0,219952297,0,523541455,0,475686081,0,735869589,0,871606395,0,408613694,0,818656889,0,342596571,0,499181781,0,99823917,0,582309212,499122176,121408097],
[0,205397248,0,99123216,0,865875026,0,238020078,0,133034951,0,873408886,0,924214648,0,771262012,0,524097907,0,669723257,0,141429057,0,383418729,0,357751925,0,29511890,0,98090762,0,696157018,0,908130190,0,279677047,0,435940567,0,506758455,0,38855993,0,73078468,0,228931579,0,142277256,0,538862373,0,275130072,0,118755216,0,795150717,0,249783133,0,263098641,0,697336024,0,543339536,0,670930089,0,691272801,0,665560159,0,399297201,0,166374065,499122176,771975633],
[0,0,714686329,0,860315947,0,840994295,0,983632790,0,498639956,0,966705949,0,958172488,0,370996534,0,353626632,0,764534596,0,981266689,0,75158631,0,916794666,0,720778218,0,245226905,0,695763930,0,711382727,0,665847544,0,991756955,0,825391559,0,283295206,0,487563517,0,568566687,0,721430389,0,309171383,0,780762355,0,164937800,0,84515435,0,271362102,0,79312213,0,585940196,0,886287107,0,807795299,0,366071508,0,356584330,0,41592952,0,748683271,499122176,774952853],
[0,738248514,0,469736765,0,299274676,0,289202362,0,874857821,0,178167268,0,737077964,0,129717335,0,425447363,0,416262175,0,104902168,0,291115320,0,148622690,0,584118502,0,98980628,0,665604306,0,241123115,0,717600029,0,585279111,0,448086054,0,994350798,0,477492821,0,180127579,0,303446425,0,996719254,0,617313332,0,64835004,0,953909944,0,778183482,0,552583932,0,966142277,0,73042552,0,898055707,0,141548304,0,490013054,0,142679649,0,166373473,0,332748124,499122176,894530654],
[0,0,471725905,0,806916814,0,180462381,0,537522940,0,846763539,0,810491852,0,60951390,0,936216035,0,544434824,0,853926109,0,367157588,0,933994985,0,593727867,0,108959351,0,187500655,0,291414648,0,634153321,0,65229209,0,424142245,0,712829001,0,824732110,0,86929172,0,193013083,0,715542971,0,816211717,0,530158452,0,536114070,0,313381820,0,964261219,0,908798250,0,797368492,0,711782041,0,215861364,0,806205455,0,738663230,0,859677708,0,915056714,0,915057330,499122176,243162086],
[0,783042817,0,285941294,0,808618933,0,870015842,0,332806617,0,650103565,0,869973700,0,316947228,0,596203323,0,921568813,0,462205161,0,854525769,0,518277906,0,716969485,0,293063082,0,922595872,0,416549799,0,101277680,0,542203881,0,848284490,0,236132240,0,451351365,0,217226855,0,299080343,0,792697913,0,778561754,0,196354421,0,397309280,0,428838280,0,851801123,0,867505986,0,369257343,0,454840708,0,802570559,0,216931834,0,488114251,0,166457833,0,432571919,0,499122183,499122176,404352143],
[0,0,483738505,0,156996615,0,830746480,0,855012704,0,532859133,0,370058087,0,773553559,0,317121497,0,453807375,0,695375970,0,162370185,0,192422563,0,269371022,0,204647404,0,572083912,0,281169853,0,527463789,0,111332203,0,733169508,0,926678603,0,63869936,0,470070285,0,611774118,0,970561817,0,74534366,0,222964633,0,268773239,0,417883541,0,377573998,0,306305257,0,300334762,0,689765553,0,151182769,0,506676293,0,644120811,0,133499161,0,83276464,0,856825744,0,83187036,499122176,786117428],
[0,119470640,0,588013113,0,515457134,0,795258981,0,390570375,0,154610197,0,587943938,0,465389687,0,24330055,0,387131777,0,367349936,0,911981288,0,416103331,0,58696100,0,185900153,0,896719826,0,197626624,0,492599837,0,51861237,0,352117045,0,639477056,0,72397818,0,502932389,0,977599923,0,97410359,0,899853400,0,430724385,0,663191353,0,131163686,0,698078097,0,761734366,0,603209554,0,311426029,0,210315078,0,384908442,0,93079845,0,652259917,0,554675593,0,332747433,0,665496242,499122176,825708292],
[0,0,845583508,0,677016567,0,969205191,0,440383991,0,668009155,0,294935565,0,121729910,0,921059033,0,608607424,0,120429385,0,717269267,0,83203788,0,643623685,0,27193096,0,801403719,0,710065258,0,529536625,0,858788545,0,557129321,0,588256472,0,805458171,0,87903058,0,646887731,0,589065245,0,297558991,0,787390502,0,146964401,0,656220457,0,768354596,0,792668778,0,254536184,0,981803044,0,246080442,0,925805317,0,530957856,0,479056458,0,484633774,0,101673,0,998243642,0,249561095,499122176,547817023],
[0,104888550,0,485743884,0,521681557,0,230252304,0,241242140,0,986727198,0,554966333,0,998204959,0,802099460,0,840289514,0,375177184,0,343722517,0,392697747,0,327940394,0,489957452,0,799583435,0,887159543,0,955415992,0,473343513,0,761863966,0,178268591,0,793110482,0,115812490,0,703827806,0,517218979,0,204400320,0,483669649,0,691007892,0,436157741,0,509542597,0,230957013,0,885881261,0,608920479,0,92584706,0,984493930,0,697577610,0,223602869,0,782754829,0,855746292,0,998243615,0,831870301,499122176,60135202],
[0,0,359897413,0,96742063,0,62510342,0,392378948,0,5821056,0,336274825,0,651940327,0,374137276,0,592920634,0,791941730,0,961693761,0,897552435,0,754489862,0,900805857,0,290754974,0,545357869,0,139864168,0,95359903,0,849994766,0,932008900,0,946485759,0,89477730,0,35358301,0,676319890,0,479250651,0,863770547,0,392184040,0,667656571,0,228301248,0,588405418,0,293083673,0,790133196,0,811138376,0,201088187,0,169084164,0,388216820,0,992736183,0,132436992,0,142721552,0,474165302,0,415935154,499122176,653612374],
[0,555592414,0,94684034,0,826671176,0,750124104,0,334722338,0,135201187,0,483516118,0,256835031,0,909154208,0,151992035,0,173033861,0,821353306,0,819638605,0,905393283,0,509475395,0,240427865,0,26941367,0,934620615,0,27635713,0,64633333,0,34730059,0,131040038,0,167025096,0,169389767,0,446373845,0,378312221,0,502594070,0,689721475,0,458523182,0,138925711,0,106582753,0,58030113,0,53566065,0,227293625,0,548616509,0,284401914,0,528762726,0,792426332,0,779723125,0,122508,0,565671006,0,7,499122176,387553690],
[0,0,653057476,0,514669193,0,64990875,0,982358134,0,848651167,0,42617751,0,368719523,0,179020933,0,78418714,0,895527237,0,169417741,0,829283890,0,875069109,0,359859193,0,611643325,0,233099748,0,566475594,0,459815501,0,455860550,0,511687465,0,236661083,0,117021298,0,135025616,0,903067009,0,259713360,0,675985997,0,606260230,0,636905451,0,775240286,0,612746571,0,484236539,0,248644492,0,658858262,0,34555943,0,167055013,0,418939289,0,688301322,0,623570410,0,478556146,0,249691253,0,415934324,0,582309213,499122176,754487011],
[0,299947194,0,419834507,0,666706425,0,370640313,0,957358744,0,100946086,0,128356760,0,383701720,0,788194796,0,92251981,0,387451525,0,459867318,0,656599005,0,790768456,0,413146479,0,215551152,0,244474124,0,450709641,0,151454732,0,800462884,0,245483268,0,473322166,0,201457495,0,77154216,0,240400724,0,614108787,0,343490974,0,312724135,0,803327537,0,707026369,0,962060184,0,344118338,0,421121422,0,890396173,0,665164033,0,483543918,0,124331251,0,270165119,0,761276325,0,975856016,0,942924533,0,166373206,0,166374066,499122176,493385140],
[0,0,70526350,0,895884615,0,183921809,0,162516536,0,742363990,0,232736947,0,797645580,0,589011573,0,482127004,0,451208335,0,670074544,0,918335763,0,469350675,0,745754526,0,499353742,0,86907518,0,801726909,0,340531701,0,872143388,0,842586855,0,365894719,0,73766887,0,359316472,0,638964193,0,498156808,0,10009880,0,664318164,0,325407153,0,705869129,0,176680535,0,544951909,0,748542090,0,736613575,0,155619050,0,441666762,0,334721146,0,888111598,0,401211524,0,119629643,0,262647935,0,915203950,0,956649955,0,748683272,499122176,533153234],
[0,770442747,0,405032345,0,793903929,0,743490187,0,479890182,0,947690155,0,193265614,0,686543324,0,289149049,0,604294811,0,797462541,0,46451626,0,317668375,0,864239298,0,610712736,0,902297408,0,564501499,0,760834756,0,108444230,0,99404625,0,469370825,0,261293113,0,99888830,0,439131099,0,862314858,0,879138107,0,996029732,0,264313580,0,607461326,0,392965315,0,418530010,0,777047815,0,245530558,0,744004915,0,184003363,0,308401705,0,198380761,0,935571544,0,458527456,0,335434408,0,605770018,0,332903577,0,931693815,0,332748125,499122176,392568004],
[0,0,843516416,0,776453764,0,296431554,0,909276227,0,677342949,0,456926659,0,658191773,0,75480916,0,708727154,0,542886550,0,185990659,0,754567319,0,511493080,0,679254466,0,214590152,0,513025960,0,919823256,0,771792199,0,936997096,0,595516923,0,162748835,0,52089901,0,627282455,0,751831974,0,456816546,0,64903174,0,495472153,0,633979301,0,794450055,0,666085580,0,85570187,0,347496421,0,905840986,0,225087874,0,676026775,0,700102387,0,9266672,0,360055048,0,318423512,0,73697473,0,487050130,0,245764514,0,232922736,0,915057331,499122176,144190851],
[0,33109029,0,349383655,0,746810,0,673923442,0,108563093,0,913673037,0,936485621,0,954417579,0,986807410,0,782708977,0,472774273,0,814593392,0,919602513,0,41236345,0,421342367,0,11176483,0,673165816,0,226164759,0,393455635,0,780116502,0,308987917,0,596001931,0,104179802,0,542762681,0,199320514,0,923587358,0,279726129,0,810772614,0,895941596,0,145951029,0,720914632,0,835274805,0,173996782,0,69565277,0,944621805,0,435141960,0,849465349,0,210768877,0,641235173,0,577573039,0,525550238,0,467991445,0,142780738,0,998243374,0,499122184,499122176,65818309],
[0,0,9094290,0,711206592,0,344074736,0,927729770,0,888099711,0,689659991,0,596812595,0,873760120,0,552218115,0,616505004,0,95201835,0,426681670,0,722997913,0,882701386,0,645850423,0,499710164,0,274981850,0,987629399,0,180404646,0,926257342,0,835847879,0,120959146,0,683516038,0,633849193,0,203044239,0,118911347,0,970512505,0,568822233,0,613990431,0,171446843,0,220879438,0,828912299,0,481903285,0,166495029,0,728886170,0,882719206,0,410592732,0,423120321,0,581733643,0,993896801,0,364105772,0,91055585,0,499306718,0,374340620,0,83187037,499122176,553374587],
[0,835578572,0,278891560,0,508322445,0,814360362,0,942924851,0,803030513,0,119813022,0,332969406,0,911767535,0,782487888,0,561784023,0,380807340,0,372295322,0,319171686,0,734960908,0,467653001,0,969633762,0,437596762,0,890911682,0,348781907,0,593238291,0,93631793,0,824057658,0,679529799,0,660403522,0,248835370,0,620777730,0,534408896,0,392707278,0,382149350,0,929526689,0,496850733,0,620355920,0,542524588,0,221993372,0,30586545,0,387715291,0,863028385,0,38834712,0,677461964,0,142950092,0,259262636,0,861917609,0,332943265,0,499121130,0,665496243,499122176,42935241],
[0,0,921118184,0,494762652,0,392165250,0,233178943,0,683421855,0,483581446,0,795900789,0,562798687,0,551447460,0,244537879,0,514449803,0,976506266,0,487003430,0,988802789,0,681187850,0,204896501,0,185982771,0,964084243,0,131361234,0,636225172,0,386657888,0,628963624,0,233765976,0,755076537,0,589474165,0,867366638,0,736369084,0,887500488,0,216619179,0,93209316,0,895167857,0,332047021,0,692638914,0,624541645,0,123806448,0,413849253,0,446794446,0,727704355,0,123090953,0,238515139,0,576032519,0,714859784,0,409736532,0,748889500,0,515758501,0,249561096,499122176,95576587],
[0,25212850,0,578113097,0,117689810,0,845422651,0,549851849,0,667429659,0,348356727,0,196072050,0,58492366,0,679185867,0,714314562,0,496662627,0,956438920,0,216612900,0,72662967,0,519868676,0,734893723,0,128720111,0,992397940,0,163038202,0,314333697,0,473812368,0,271224357,0,467531952,0,144684814,0,107810860,0,69234046,0,859223966,0,465352943,0,598913019,0,520021243,0,416628668,0,818058396,0,956862889,0,735086374,0,206092101,0,929464603,0,120754857,0,253119949,0,121190644,0,363063377,0,375752249,0,238580413,0,855770468,0,499339998,0,565670683,0,831870302,499122176,819611153],
[0,0,199366022,0,4326200,0,532429521,0,431292083,0,731492977,0,542157457,0,438663681,0,290713988,0,86877631,0,980083074,0,362055555,0,94248070,0,883887746,0,734936625,0,729221572,0,669896323,0,908334527,0,866529257,0,484506144,0,636776818,0,639689718,0,115509110,0,668642080,0,925323655,0,75252276,0,657690311,0,380604728,0,281109812,0,848271575,0,199595682,0,523094582,0,556042907,0,996009324,0,353229453,0,141979205,0,230333563,0,586191100,0,899626836,0,372277140,0,393474978,0,164974261,0,436841762,0,832315262,0,515470429,0,527081109,0,790275626,0,415935155,499122176,322349739],
[0,919529569,0,390246586,0,83063040,0,599392775,0,940219591,0,485222077,0,87434913,0,12363370,0,584714382,0,228803956,0,630008691,0,903561406,0,761210330,0,258894966,0,849471578,0,454954424,0,769045977,0,808677079,0,683476654,0,40810101,0,30144228,0,778124908,0,911915670,0,579885077,0,549794306,0,82931087,0,776922530,0,192430922,0,315830575,0,737301454,0,232294487,0,559419279,0,68709935,0,250083451,0,187636175,0,37314307,0,562721435,0,750324608,0,927149493,0,705107500,0,133592597,0,611760017,0,974880325,0,505350212,0,948581051,0,523132455,0,332746927,0,8,499122176,699800165],
[0,0,175310388,0,978402710,0,344608127,0,404707470,0,235755291,0,511543583,0,534495872,0,449294563,0,488975895,0,910050316,0,191405223,0,74851751,0,689835317,0,682976628,0,18090204,0,630397333,0,814116917,0,875672002,0,693880561,0,373481692,0,782650493,0,717167376,0,317081258,0,402371071,0,188145923,0,864987625,0,323394684,0,297666263,0,820788272,0,759398131,0,250723464,0,114784148,0,539605302,0,899899056,0,46100624,0,563257345,0,993927323,0,800033615,0,269931288,0,106259579,0,389330788,0,551946965,0,879031963,0,783907473,0,478870985,0,475610192,0,332746889,0,582309214,499122176,845451850],
[0,377616162,0,735584243,0,210050409,0,831536366,0,746585379,0,557624047,0,16850268,0,364207391,0,358681280,0,52744901,0,919420298,0,338131477,0,652786831,0,433413974,0,173812402,0,411404125,0,752845381,0,83389791,0,134001719,0,182240755,0,795322644,0,321171025,0,763235692,0,469994981,0,804742142,0,674710002,0,902523513,0,140632992,0,686907672,0,43630358,0,238136978,0,722762395,0,280562415,0,163508310,0,410078932,0,626023032,0,523685833,0,393656822,0,745976141,0,410667498,0,399689068,0,375502491,0,460201615,0,324677700,0,336016267,0,208555106,0,222101566,0,931693462,0,166374067,499122176,584830025],
[0,0,723601665,0,985994925,0,970220866,0,58257911,0,702958087,0,856982064,0,546974475,0,444215342,0,974502687,0,111350607,0,144413929,0,770889622,0,757880784,0,35061450,0,373932056,0,555293383,0,812182592,0,978005190,0,60144271,0,825387501,0,448625728,0,473073718,0,774577378,0,657413288,0,874653507,0,401481730,0,157259911,0,819044384,0,828258146,0,171814526,0,380250981,0,353742247,0,919965799,0,149968479,0,922223982,0,860781669,0,444300740,0,223824337,0,63753559,0,333508267,0,506898859,0,192995419,0,982459182,0,864384589,0,469442329,0,636741749,0,283822,0,274515890,0,748683273,499122176,828542813],
[0,409187229,0,162191028,0,753255793,0,170089816,0,536394083,0,310312459,0,65187415,0,651763441,0,88060413,0,190278922,0,815453658,0,758092433,0,88825429,0,477729043,0,258590428,0,46980932,0,986961157,0,894458330,0,80197445,0,410176170,0,381862889,0,300436128,0,607610772,0,862185037,0,913840763,0,247000475,0,738677899,0,13678651,0,631319266,0,777809721,0,363486465,0,888785658,0,774582923,0,970805707,0,911776476,0,370961562,0,700542665,0,259652869,0,148074621,0,118608721,0,128286501,0,947478648,0,109612922,0,337552389,0,376758519,0,768174209,0,931546183,0,298760,0,499120829,0,332748126,499122176,889524671]
]
coef_prep=[]
coef=[]
memory={}
D01=21
for k in R(D01):
if len(coef_prep)<=k:
coef_prep+=[[ModB(0,True)for k1 in R(k)]]
for j1 in R(k):
for j2 in R(j1,k):coef_prep[k][j1]+=ModB.FactorialInverse(k-j2)*ModB.FactorialInverse(j2-j1)*(((k&1)==(j2&1))*2-1)
coef_prep[k][j1]*=ModB.Factorial(k)*ModB.FactorialInverse(j1)
for j in R(D01):
if len(coef)<=j:coef+=[[]]
for k in R(D01-j):
if len(coef[j])<=k:coef[j]+=[[[coef_prep[k][j1]*s[j][k1]for k1 in R(j+2)]for j1 in R(k)]]
def FloorSumComposition_Body(y,d,q,n,D01,init):
global coef_prep
global coef
global memory
if init:memory={}
D=60
hash=y|(d<<D)|(q<<(D+D))|(n<<(D+D+D))
if not hash in memory:memory[hash]=[]
answer=memory[hash]
if len(answer)<D01:
assert(q>0 and n >=0 and D01<=len(s))
n_mod=ModB(n)
Sn=[ModB(0,True)for j in R(D01)]
for j in R(D01):
n_power=ModB(1,True)
for k in R(1,j+2):
n_power*=n_mod
Sn[j]+=s[j][k]*n_power
d_0=d%q
temp=[[]for j in R(D01)]
if d_0<1:
for j in R(D01):
temp[j]=[ModB(0,True)for k in R(D01-j)]
temp[j][0]=Sn[j]
elif n:
y_0=y%q
m=(y_0+d_0*(n-1))//q
m_mod=ModB(m)
m_power=[ModB(1,True)]
for k in R(1,D01):m_power+=[m_power[-1]*m_mod]
prev=FloorSumComposition_Body(q+d_0-y_0-1,q,d_0,m,D01,False)
for j in R(D01):
temp[j]=[ModB(0,True)for k in R(D01-j)]
for k in R(D01-j):
coef_jk=coef[j][k]
temp[j][k]=Sn[j]*m_power[k]
for j1 in R(k):
for k1 in R(j+2):temp[j][k]+=prev[j1][k1]*coef_jk[j1][k1]
d_1=ModB(d//q)
y_1=ModB(y//q)
for j in R(D01):
if(len(answer)<=j):answer+=[[]]
for k in R(D01-j):
if len(answer[j])<=k:
answer[j]+=[ModB(0,True)]
if n:
y_1_power=ModB(1,True)
for k1 in R(k+1):
d_1_power=ModB(1,True)
for k2 in R(k-k1+1):
answer[j][k]+=temp[j+k2][k-k1-k2]*ModB.FactorialInverse(k2)*ModB.FactorialInverse(k1)*ModB.FactorialInverse(k-k1-k2)*y_1_power*d_1_power
d_1_power*=d_1
y_1_power*=y_1
answer[j][k]*=ModB.Factorial(k)
return answer
def FloorSumComposition(y,d,q,n,f):
D0=len(f)
D01=max(j+len(f[j])for j in R(D0))
coef=FloorSumComposition_Body(y,d,q,n,D01,True)
answer=ModB(0,True)
for j in R(D0):
for k in R(len(f[j])):answer+=f[j][k]*coef[j][k]
return answer
J=lambda:map(int,input().split())
for _ in R(sum(J())):
p,q,N,M,A,B=J()
f=[[]for j in R(p+1)]
f[p]=[ModB(0,True)for k in R(q+1)]
f[p][q]=ModB(1,True)
print(FloorSumComposition(B,A,M,N+1,f))