dx4J-cheat.cc

#include <cstdio>
#define Z 0,0,0,0,0,0,0,0
#define Y 0,0,0,0
#define X 1,1,1,1,1
#define Q Z,Z
#define LL long long
const int MAXN = 21;
const LL INF = 1e9+7;
LL C(LL n,LL m){
long double res = 1;
for(long double i=1;i<=n;i+=1)res*=i;
for (long double i = 1;i <= m;i+=1) res /= i;
for (long double i = 1;i <= n-m;i+=1) res/=i;
LL r = res;
r %= INF;
return r;
}

LL Pow(LL n,LL m){
LL res = 1;
for (int i = 1;i <= m;i++) res = (res*n)%INF;
return res;
}

LL n,k,l,T;
LL f[MAXN][MAXN][MAXN] = {1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,1,Z,Z,Y,2,1,Z,Z,0,0,0,3,1,1,Z,Z,0,0,4,1,1,1,Z,Z,0,5,1,1,1,1,Z,Z,6,X,Z,Y,0,0,0,7,X,1,Z,Y,0,0,8,X,1,1,Z,Y,0,9,X,1,1,1,Z,Y,10,X,1,1,1,1,Z,0,0,0,11,1,1,1,1,X,1,Z,0,0,12,X,X,1,Z,0,13,X,X,1,1,Z,14,X,X,1,1,1,Y,0,0,0,15,X,X,1,1,1,1,Y,0,0,16,X,X,X,Y,0,17,X,X,X,1,Y,18,X,X,X,1,1,0,0,0,19,X,X,X,1,1,1,0,0,20,X,X,X,1,1,1,1,0,21,1,1,1,1,X,X,X,1,1,Z,Z,Y,4,3,1,Z,Z,0,0,9,5,6,2,1,Z,Z,16,7,8,9,3,2,1,Z,Y,0,0,25,9,10,11,12,4,3,2,1,Z,Y,36,11,12,13,14,15,5,4,3,2,1,Z,0,0,49,13,14,15,16,17,18,6,5,4,3,2,1,Z,64,15,16,17,18,19,20,21,7,6,5,4,3,2,1,Y,0,0,81,17,18,19,20,21,22,23,24,8,7,6,5,4,3,2,1,Y,100,19,20,21,22,23,24,25,26,27,9,8,7,6,5,4,3,2,1,0,0,121,21,22,23,24,25,26,27,28,29,30,10,9,8,7,6,5,4,3,2,1,144,23,24,25,26,27,28,29,30,31,32,33,11,10,9,8,7,6,5,4,3,169,25,26,27,28,29,30,31,32,33,34,35,36,12,11,10,9,8,7,6,5,196,27,28,29,30,31,32,33,34,35,36,37,38,39,13,12,11,10,9,8,7,225,29,30,31,32,33,34,35,36,37,38,39,40,41,42,14,13,12,11,10,9,256,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,15,14,13,12,11,289,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,16,15,14,13,324,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,17,16,15,361,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,18,17,400,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,19,441,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,1,Z,Z,Y,8,7,4,1,Z,Z,0,27,19,23,13,10,3,1,Z,Y,0,0,64,37,44,50,31,24,17,6,3,1,Z,0,0,0,125,61,71,80,92,54,47,36,25,10,6,3,1,Z,216,91,104,116,131,145,86,75,64,49,34,15,10,6,3,1,Y,0,343,127,143,158,176,193,213,123,112,97,82,63,44,21,15,10,6,3,1,0,0,512,169,188,206,227,247,270,292,169,154,139,120,101,78,55,28,21,15,10,6,3,729,217,239,260,284,307,333,358,386,220,205,186,167,144,121,94,67,36,28,21,15,1000,271,296,320,347,373,402,430,461,491,280,261,242,219,196,169,142,111,80,45,36,1331,331,359,386,416,445,477,508,542,575,611,345,326,303,280,253,226,195,164,129,94,1728,397,428,458,491,523,558,592,629,665,704,742,419,396,373,346,319,288,257,222,187,2197,469,503,536,572,607,645,682,722,761,803,844,888,498,475,448,421,390,359,324,289,2744,547,584,620,659,697,738,778,821,863,908,952,999,1045,586,559,532,501,470,435,400,3375,631,671,710,752,793,837,880,926,971,1019,1066,1116,1165,1217,679,652,621,590,555,520,4096,721,764,806,851,895,942,988,1037,1085,1136,1186,1239,1291,1346,1400,781,750,719,684,649,4913,817,863,908,956,1003,1053,1102,1154,1205,1259,1312,1368,1423,1481,1538,1598,888,857,822,787,5832,919,968,1016,1067,1117,1170,1222,1277,1331,1388,1444,1503,1561,1622,1682,1745,1807,1004,969,934,6859,1027,1079,1130,1184,1237,1293,1348,1406,1463,1523,1582,1644,1705,1769,1832,1898,1963,2031,1125,1090,8000,1141,1196,1250,1307,1363,1422,1480,1541,1601,1664,1726,1791,1855,1922,1988,2057,2125,2196,2266,1255,9261,1261,1319,1376,1436,1495,1557,1618,1682,1745,1811,1876,1944,2011,2081,2150,2222,2293,2367,2440,2516,1,Z,Z,Y,16,15,11,5,1,Z,Z,81,65,76,55,50,26,15,4,1,Z,Y,256,175,208,230,182,158,138,84,53,29,10,4,1,Z,625,369,436,488,551,412,400,342,302,187,136,86,48,20,10,4,1,Y,1296,671,784,878,995,1083,836,786,750,635,547,362,272,196,126,73,35,20,10,4,1,2401,1105,1276,1424,1607,1757,1941,1448,1432,1313,1241,1048,897,614,488,367,265,174,105,56,35,4096,1695,1936,2150,2411,2635,2905,3143,2380,2277,2217,2032,1885,1602,1363,967,789,626,473,344,231,6561,2465,2788,3080,3431,3741,4109,4441,4845,3555,3523,3346,3215,2936,2709,2305,1966,1432,1199,978,777,10000,3439,3856,4238,4691,5099,5577,6015,6537,6994,5191,5038,4927,4664,4449,4053,3718,3184,2714,2030,1729,14641,4641,5164,5648,6215,6733,7333,7889,8541,9124,9832,7140,7065,6818,6631,6239,5928,5394,4936,4244,3634,20736,6095,6736,7334,8027,8667,9401,10087,10881,11602,12460,13235,9661,9446,9287,8919,8628,8110,7664,6980,6374,28561,7825,8596,9320,10151,10925,11805,12633,13581,14452,15472,16405,17486,12580,12465,12121,11866,11364,10942,10270,9684,38416,9855,10768,11630,12611,13531,14569,15551,16665,17698,18892,19995,21258,22435,16197,15893,15674,15204,14810,14162,13596,50625,12209,13276,14288,15431,16509,17717,18865,20157,21364,22744,24029,25486,26853,28406,20267,20100,19662,19312,18688,18158,65536,14911,16144,17318,18635,19883,21273,22599,24081,25474,27052,28531,30194,31763,33530,35178,25176,24786,24480,23896,23402,83521,17985,19396,20744,22247,23677,25261,26777,28461,30052,31840,33525,35406,37189,39182,41052,43161,30608,30362,29818,29376,104976,21455,23056,24590,26291,27915,29705,31423,33321,35122,37132,39035,41146,43155,45386,47490,49845,52063,36990,36502,36112,130321,25345,27148,28880,30791,32621,34629,36561,38685,40708,42952,45085,47438,49685,52166,54516,57129,59601,62335,43980,43658,160000,29679,31696,33638,35771,37819,40057,42215,44577,46834,49324,51699,54306,56803,59546,62154,65037,67775,70787,73659,52046,194481,34481,36724,38888,41255,43533,46013,48409,51021,53524,56272,58901,61774,64533,67550,70428,73593,76609,79911,83069,86527,1,Z,Z,Y,32,31,26,16,6,1,Z,Y,0,0,0,243,211,237,196,192,131,96,45,21,5,1,Z,0,0,1024,781,912,977,867,806,772,590,451,326,186,100,46,15,5,1,Y,0,3125,2101,2477,2722,2968,2516,2552,2335,2262,1756,1481,1135,837,505,320,176,86,35,15,5,1,7776,4651,5472,6077,6768,7167,6292,6130,6117,5611,5327,4330,3702,3090,2360,1752,1146,770,490,280,147,16807,9031,10557,11762,13198,14187,15323,12990,13227,12686,12612,11490,11048,9015,7995,6717,5601,4315,3251,2245,1607,32768,15961,18512,20617,23158,25077,27343,28951,25037,24686,24832,23820,23523,21485,20461,17027,15146,13295,11131,9245,7227,59049,26281,30237,33602,37668,40917,44773,47801,51318,43051,43852,42865,43113,40975,40396,36692,35167,29405,26606,23500,20492,100000,40951,46752,51797,57868,62907,68873,73821,79648,84002,71547,71140,71868,70175,69941,66477,65187,59435,56222,47990,43562,161051,61051,69197,76402,85018,92367,101023,108451,117208,124157,132598,110360,112288,110870,111766,108257,107947,102055,99562,90885,86328,248832,87781,98832,108737,120498,130737,142723,153251,165618,175822,188173,198141,166603,166335,168156,165562,166057,160765,158842,150565,146303,371293,122461,137037,150242,165808,179577,195593,209901,226618,240797,257838,272071,289064,238605,242426,240462,242862,237955,237417,229415,226543,537824,166531,185312,202477,222568,240567,261373,280201,302068,321002,343573,362891,385739,405136,337091,336952,340937,337635,338427,331695,329893,759375,221551,245277,267122,292518,315507,341923,366071,393948,418477,447478,472761,502404,528156,558642,457387,464352,462290,465797,460035,460643,1048576,289201,318672,345977,377518,406317,439223,469551,504358,535382,571773,603961,641399,674486,713267,746588,615942,616635,622492,619205,621958,1419857,371281,407357,440962,479548,515037,555373,592801,635518,673997,718798,758891,805184,846646,894822,936933,987223,803345,813267,812010,818578,1889568,469711,513312,554117,600708,643827,692593,738101,789768,836722,891013,940071,996339,1047276,1106007,1158048,1219493,1273056,1041277,1043885,1053823,2476099,586531,638637,687602,743218,794967,853223,907851,969568,1026077,1090998,1150141,1217564,1279136,1349642,1412813,1486673,1551956,1627808,1317825,1333168,3200000,723901,785552,843697,909418,970857,1039723,1104571,1177498,1244702,1321453,1391861,1471679,1545106,1628667,1704228,1791823,1870126,1960338,2041726,1660088,4084101,884101,956397,1024802,1101768,1174017,1254673,1330901,1416258,1495357,1585198,1668111,1761624,1848186,1946142,2035413,2138123,2230806,2336798,2433256,2544189,1,Z,Z,Y,64,63,57,42,22,7,1,Z,Y,0,0,729,665,722,644,651,519,435,272,168,71,28,6,1,Z,4096,3367,3840,4011,3769,3637,3616,3120,2686,2241,1610,1093,690,362,171,69,21,6,1,0,0,15625,11529,13438,14464,15298,13899,14260,13573,13603,11914,10928,9374,7992,5964,4548,3136,2052,1172,662,327,145,46656,31031,36416,39887,43397,44930,42079,41621,42103,40414,39871,35927,33300,30162,26040,22224,17529,13730,10418,7278,4913,117649,70993,83274,92040,101766,107308,113072,102763,105187,103247,104326,99325,99565,89258,84618,77292,70338,60826,52812,42419,34631,262144,144495,168832,187363,208825,222906,238661,247258,229046,228716,231871,227594,229591,219167,217281,198522,187626,175519,160884,145493,127169,531441,269297,312950,347696,388754,418124,452000,474270,498343,450579,461185,456537,465397,452815,456536,434521,433397,395186,379193,354714,332264,1000000,468559,541248,600999,672213,726202,789269,835202,887012,919138,842189,844525,860697,851954,860820,841581,844086,805545,798480,736522,704397,1771561,771561,885826,982072,1097062,1187940,1294568,1377334,1472571,1538291,1613750,1449657,1485563,1478997,1505235,1484765,1502732,1459547,1466366,1396145,1387716,2985984,1214423,1385984,1533275,1709081,1852418,2020637,2156946,2315200,2432034,2569494,2664080,2421173,2433475,2478084,2470181,2503407,2468396,2486765,2421114,2421732,4826809,1840825,2088942,2305248,2562690,2777716,3029576,3240038,3485159,3674767,3899998,4066792,4261998,3803007,3890028,3891845,3963792,3930664,3985450,3915776,3947958,7529536,2702727,3050560,3357631,3721669,4031634,4393565,4703050,5063508,5352050,5695682,5962704,6276978,6505734,5861236,5901740,6014262,6012713,6097855,6053105,6113053,11390625,3861089,4336058,4759784,5259878,5692412,6195584,6633582,7142827,7561323,8059206,8459576,8930838,9294566,9722325,8623059,8817537,8840496,8998821,8969533,9095805,16777216,5386591,6020736,6591507,7261977,7849450,8530133,9131114,9827936,10412626,11106190,11678488,12350478,12890218,13525243,14009650,12536656,12633664,12862451,12898622,13086865,24137569,7360353,8190694,8943760,9824146,10604028,11503952,12307726,13236615,14029319,14965934,15754560,16677198,17440050,18335381,19045529,19897009,17553486,17914966,18005445,18322951,34012224,9874655,10943552,11919383,13054805,14070026,15236741,16288818,17500324,18548802,19782138,20837672,22067418,23106902,24322359,25314378,26500448,27428141,24368965,24589333,25026007,47045881,13033657,14389170,15633816,17075334,18374644,19861880,21213830,22764923,24123235,25713622,27093184,28693398,30069814,31672357,33009397,34600737,35884333,37402622,32853465,33503998,64000000,16954119,18650368,20215819,22020793,23659122,25527149,27236962,29191392,30920258,32935046,34702656,36743958,38524746,40588835,42341426,44416456,46130145,48145931,49807584,44018573,85766121,21766121,23863646,25808192,28040642,30079460,32395448,34527894,36956551,39123711,41637630,43864568,46425198,48685298,51293253,53539665,56184905,58410857,61014530,63209006,65784694,1,Z,Z,Y,128,127,120,99,64,29,8,1,Z,Y,0,2187,2059,2179,2031,2074,1814,1647,1226,897,511,274,105,36,7,1,Y,0,0,16384,14197,15808,16228,15703,15443,15543,14358,13259,11999,9857,7756,5812,3857,2367,1338,644,273,99,28,7,78125,61741,70835,74818,77444,73193,74973,72948,73803,68937,66228,60781,56073,47327,40307,32012,24746,17486,12125,7658,4565,279936,201811,234880,253346,269622,275004,266101,264811,268158,263292,263174,250145,242035,229775,213067,195995,171963,148981,126148,101878,80264,823543,543607,636043,695242,755240,783323,809708,765731,781174,774593,784184,764456,773945,731066,716780,685925,655481,606340,566302,500213,446749,2097152,1273609,1490624,1642216,1807508,1901020,1998770,2039340,1958735,1963389,1987596,1971186,1994234,1950109,1955053,1875953,1830907,1773576,1707183,1620500,1514361,4782969,2685817,3135883,3469538,3848316,4089255,4355152,4498790,4644552,4383877,4469957,4447961,4529319,4462465,4514498,4408399,4439717,4243771,4188942,4049920,3945321,10000000,5217031,6067840,6726358,7491074,8017508,8615324,8990956,9394227,9600908,9153391,9192372,9350919,9305786,9408184,9323743,9388801,9186569,9226794,8873046,8725691,19487171,9487171,10984115,12181066,13588592,14613979,15796316,16613718,17521402,18061465,18640562,17504858,17892361,17855649,18139452,18040430,18264493,17996055,18194809,17744790,17858165,35831808,16344637,18831808,20871692,23286000,25121028,27253678,28826996,30609267,31776880,33087512,33849495,32124341,32300380,32825634,32854243,33256848,33065613,33406201,32982964,33219693,62748517,26916709,30860419,34161346,38078708,41155655,44744480,47518270,50697132,52923383,55487022,57148911,59041050,55160763,56295346,56441954,57362503,57150324,58014729,57462916,58126365,105413504,42664987,48679808,53798698,59875406,64775020,70495352,75073140,80353507,84236644,88771952,91934403,95589233,97825750,92215202,92941837,94525629,94711869,96069445,95800397,96888872,170859375,65445871,74323195,81983498,91066104,98547003,107275564,114450926,122754222,129092413,136550522,142027971,148408398,152696370,157661073,146713366,149758023,150316621,152932034,152803287,155008444,268435456,97576081,110315200,121437136,134595212,145625804,158475146,169265308,181765587,191592200,203194512,212052135,222406665,229831106,238486524,244289447,229119746,231008652,235071749,235990643,239390553,410338673,141903217,159744923,175478242,194039660,209832583,228188048,243870006,262032592,276653995,293932502,307525695,323430434,335384638,349363423,359316527,371022963,343721553,350672682,352613359,358685568,612220032,201881359,226344064,248103326,273692058,295741140,321300340,343449500,369072147,390108028,414948152,434964531,458367705,476596926,497926530,513802467,532601289,545602912,509076781,513843750,522795437,893871739,281651707,314570083,344072458,378648896,408768635,443583452,474114790,509371362,538797569,573483522,601987443,635256438,661904090,693055485,717044177,745520485,766220603,790728488,729897588,744301659,279999993,386128261,429694400,468999988,514903784,555271348,601792454,643004196,690490867,730684768,777947432,817427031,863397953,901054330,944993248,979752287,21012814,52157863,88984754,116025842,36785263,801088534,521088541,577895635,629450306,689445732,742645479,803769376,858389198,921173172,974961535,38028855,91445608,153475363,205228879,265469572,314177140,371905720,416789186,469728957,510213755,557873804,1,Z,Z,Y,256,255,247,219,163,93,37,9,1,Z,Y,6561,6305,6552,6269,6404,5919,5634,4687,3834,2634,1711,890,423,148,45,8,1,Y,65536,58975,64256,65244,64108,63623,64153,61551,59130,56085,50035,43270,36086,27688,20053,13677,8381,4706,2419,1072,414,390625,325089,366568,381248,389197,376357,383427,377555,381963,368953,363037,346666,333747,303252,276563,240465,205662,165294,130389,96400,68809,1679616,1288991,1483008,1576172,1647367,1665348,1638125,1634191,1650123,1637113,1641364,1602820,1582755,1542724,1487699,1426056,1330718,1227450,1113765,982644,850612,5764801,4085185,4749176,5128416,5475853,5609130,5723310,5539605,5621857,5597989,5652376,5577766,5640820,5480506,5452873,5342846,5239298,5034324,4881686,4564958,4301840,16777216,11012415,12858112,14035100,15229111,15809092,16373388,16552020,16204447,16248787,16390682,16327824,16472620,16303260,16365904,16078170,15929162,15706590,15474698,15088014,14621936,43046721,26269505,30693576,33736064,37015117,38861754,40796302,41648178,42473952,41099063,41674224,41562652,42109314,41761486,42143844,41670434,41962411,41077714,40997494,40335006,40010032,100000000,56953279,66445568,73340268,81052807,85854276,91107708,93926484,96819226,98052342,95541384,95877104,97068462,96817736,97585564,97248466,97777917,96833432,97355997,95626490,95164526,214358881,114358881,133048408,147194912,163392397,174229258,186400302,193819602,201753808,205817422,209900265,202348338,205711800,205430908,207742784,207261828,209097447,207489274,209377711,206785870,208218159,429981696,215622815,249981696,276837596,308038903,330072900,355216780,371949396,390349674,401005782,412358553,417971153,406334396,407993796,412785410,413411036,416852965,415843432,419026317,416516136,419090407,815730721,385749025,445474472,493371840,549519181,590866842,638506638,672281970,710121760,734014062,760454697,775426183,792083421,760802842,772638096,774471166,783390729,781855158,790586757,786265778,793212693,475789049,660058335,759152896,840306284,935932807,8743997,93107125,155827021,226965875,274834415,329118706,362920218,401210106,420861170,374537601,383469477,400707378,403079605,417976876,416069125,427754880,562890611,87101562,245171761,376897881,532527110,654288739,795788711,904921867,29701442,117849248,219387803,287127049,364825807,409945401,461639163,358732742,396358627,403355430,434940943,433619648,459615263,294967268,732076664,975870201,182039438,425836713,620921654,847905278,28140351,235259317,387291201,564158724,688436380,832138716,923287044,28494541,90809399,943399434,969402251,23720973,35218084,78529285,975757399,680790131,45991795,358731755,728427832,29909342,380689522,665867158,994555076,243408747,534665798,747737668,995307898,162930109,357460191,481746217,624189558,324750248,428214651,454780526,539932249,19960499,44203107,577509604,39180745,584287716,36039450,561233746,996577578,499088041,889377733,347725121,693990217,97359458,384424954,718695226,944982564,207886084,368953355,961176284,35175830,173725845,983562929,963602430,725096174,390559855,174899541,834001298,599196399,243863308,988306442,578999105,273785109,812619811,440949442,905950636,448339079,832475409,282588791,576802738,924778707,161338909,406836986,599999825,616436903,682279105,621478038,726043050,665512432,754274737,684244466,757778881,625223270,645823778,454782227,398013708,118344525,958940957,576129568,302933728,802521863,393515925,777775812,766082255,822859102,222859277,688322317,989193694,515361245,827231459,344483849,655808102,168212614,409541261,869133057,47533969,420345248,496079459,750856926,699608097,819708391,621020667,568338581,220216165,988941532,1,Z,Z,Y,512,511,502,466,382,256,130,46,10,1,Z,0,0,0,19683,19171,19673,19126,19472,18592,18176,16240,14318,11155,8272,5235,3061,1461,625,201,55,9,1,0,0,262144,242461,259328,261587,259127,258247,259980,254563,249743,243221,228199,209592,187460,158319,128047,98770,70621,47337,29693,16866,8745,1953125,1690981,1874393,1926530,1950108,1911397,1936716,1919506,1936512,1902674,1893145,1848426,1819014,1726719,1642315,1513180,1379384,1204296,1034852,849330,679651,10077696,8124571,9225728,9677771,9977460,10035968,9953484,9940357,10005087,9971249,9995009,9888306,9848205,9732825,9576142,9384320,9065855,8683578,8227214,7662396,7038773,40353607,30275911,34884857,37220834,39145158,39750593,40229395,39472777,39872529,39775700,40035416,39753111,40062790,39492255,39499888,39137681,38857313,38107995,37640196,36368349,35329319,134217728,93864121,109023488,117811907,126045618,129472040,132580534,133336898,131858721,132136532,132870131,132618969,133351741,132728802,133089428,132125561,131713475,130950468,130297443,128818608,127120472,387420489,253202761,295183673,321872642,348960624,362427845,375778927,380560127,385061482,377969237,381441725,380841126,384018361,382202607,384478406,382366250,384205839,380406558,380887032,377970771,377519558,1000000000,612579511,714787328,784251515,858494448,900172688,943887022,963802250,983501569,990548748,976781369,979144473,986961223,985510941,990322115,988961786,992205567,987989787,991558498,983763168,983018819,357947677,357947684,583106706,744034779,922026643,31093339,149721981,213068341,278474748,307367813,334729046,285863213,311828415,309460100,325901440,323214544,335882072,326160326,339717948,325322135,336309797,159780317,801832647,259780331,600172958,985431897,237571740,518429642,685937142,864616361,955996540,48445235,87695853,11905098,25045364,63373510,69316873,94361459,88734500,112118583,97568231,117014792,604499303,444718986,317321711,986551640,755877139,285797749,885462063,273068360,696466603,936979488,192000160,318497636,456624084,212772985,322279881,339106386,414292915,401880976,474707612,441075349,498647968,661046644,56547341,631431091,870498263,309869066,342586295,523494830,334524643,235739371,789254694,395730739,732724685,107561632,269320326,900099282,993198798,156831557,177294470,314264970,298176638,399171806,443359109,782312472,497283373,679079496,231088063,123916244,303182904,871988345,636723690,787605732,77774771,857837187,738297992,179242595,682411747,754257683,162473881,232153852,557758628,536591710,792756841,719476260,276117151,776328210,457906585,782907396,80271366,893016767,742316406,975442412,186229786,704391990,328278402,181232238,216594477,403709862,30374827,653583434,958624661,583000072,695527143,160125382,587875671,868399418,78501098,67529033,120859438,624226568,3903521,918239413,528555750,514590711,105291623,218870670,799286977,971973257,476007016,917511785,521982845,376093054,713830887,14512632,30928984,359288982,771413318,985107338,422859807,550673631,406085480,684460544,802373732,108360005,932088838,850679886,442773790,907469006,88639665,928214421,911804016,297828497,147506365,805482878,783715565,627200965,687695525,328406543,318003326,781438117,837873550,643738403,673371893,601078642,460594752,648442348,697103354,221263420,269455507,784460332,510118005,191984295,728572105,580873688,133889414,983061143,605490603,999996423,312300898,461062950,86698783,575283651,513272354,815521000,765053128,732134666,417037759,109527490,632949971,677007567,460003866,332423153,455681631,211750726,573546749,278073888,295362034,1256994,280041023,280044607,740279207,372780016,615158871,607228047,548975597,503929947,16005049,108869985,867452071,250421292,620375816,401137075,604988679,691342592,659736938,793214688,323534723,922842520,281301601,1,Z,Z,Y,1024,1023,1013,968,848,638,386,176,56,11,1,Z,0,0,59049,58025,59038,57970,58773,57190,56706,53008,49116,41713,34001,24662,16698,9757,5193,2287,891,265,66,10,1,1048576,989527,1042432,1047497,1042167,1040584,1045323,1034392,1025520,1012885,978965,933356,873690,786801,686237,576714,458630,346944,248861,166119,103640,9765625,8717049,9509746,9689936,9759216,9642606,9728179,9676831,9734629,9646294,9641091,9525265,9471494,9218130,8986273,8583773,8144784,7505878,6832652,6020543,5203409,60466176,50700551,56796160,58925525,60155257,60343157,60093740,60047695,60289017,60200682,60293642,60008636,59951092,59646568,59247551,58712734,57773982,56540636,54969920,52894381,50430190,282475249,222009073,253178374,267139064,277460228,280130876,282102813,279017637,280858993,280432521,281570515,280484255,281821545,279816930,280223637,279048080,278496745,275959575,274833663,270281363,266808383,73741817,791266575,912498688,976166273,31010062,50549118,67151172,70284205,64044027,65532845,69071626,68023219,71340488,69073749,70725905,67620918,66684316,64249936,62825069,57726626,52350306,486784380,413042563,800773068,27949451,243900619,338514563,427263964,453130728,477086590,441055090,460811518,457482654,474537604,465046424,477313429,467556115,477582339,461317821,466906203,454251041,456882599,999999937,513215557,584080847,263306005,952871185,301223030,650611668,785373933,915024474,954270647,879945287,895068216,942406975,934059483,961448013,955490146,972904008,954225095,974004320,940074920,942710945,937424426,937424496,576435184,353488060,240895978,297964771,407490509,924314025,441985548,639938734,817369776,507300066,693907283,674748370,783118434,765622200,845851271,786394890,872383628,792545557,863515904,917363797,979939378,917363937,106056567,697614903,477104530,487197171,88814254,748858776,499091578,221481085,487239437,5824604,100235212,383719538,428554233,595314362,561512714,713675337,629405001,754758627,858490890,941127100,341589722,421066569,599022595,144463202,389032282,638916362,164159125,475094453,822285465,847097301,946951704,92710256,33926229,167936044,752716450,649135748,197960473,940650633,367423550,254652953,396162070,739486007,111662839,37751960,161069106,33847120,60519939,959891106,61837382,508512538,710257021,213516104,488872326,617173969,501261496,928943820,76192089,213256676,72335052,849311513,650386593,395733640,746902722,844916367,278833660,663606816,909722305,488370691,316227389,638974789,215547247,748973026,234252318,333054918,12907602,894985366,975147586,589434191,644739100,353376760,638741050,511620083,861233497,646500739,504091956,662987570,449880392,16170428,153219768,354149937,7276281,61906485,192240841,850970590,987322990,718695065,756218856,256110903,518507092,55375747,21728463,526922706,993886344,482266261,909908696,322526302,430305456,424225425,25686778,195263183,703261400,615791107,358515738,511734064,560058755,164660282,683679775,598847553,738377164,730404197,553923945,612055228,613915943,467201634,473315297,760819007,191913176,891616039,554050619,139532715,345845133,133664551,36032470,74115286,758616459,866154708,346151667,537401995,815003673,5900529,203719487,541046193,302993011,605985070,66214884,599013257,193571879,604039034,432884389,848564980,176326313,42913334,846125715,305521144,409072811,232838870,220202768,848916774,308151250,731578851,134298811,845905026,140059443,207429652,985081747,999928327,933713443,939836901,744887378,899687375,934250570,497332947,612847135,83685279,833788944,202455114,240920893,330855691,537432446,753721404,457788266,251996403,496793559,259507682,141143088,88924796,880861448,880933128,937691363,323534317,974124996,868773640,441295838,222040748,800454700,638333424,973416660,776236471,718017357,81210349,576301660,845166688,315961113,777780475,46415379,7626044,969857924,1,Z,Z,Y,2048,2047,2036,1981,1816,1486,1024,562,232,67,12,1,Z,0,177147,175099,177135,175033,176794,173933,173637,166904,159678,143837,125468,100376,75747,51117,31824,17237,8427,3443,1233,341,78,4194304,4017157,4180992,4192190,4180651,4177790,4189573,4167846,4152535,4130216,4058958,3956646,3811524,3580412,3287406,2934878,2516724,2075645,1640003,1226984,870376,48828125,44633821,48001439,48611554,48814472,48463460,48742631,48587210,48771077,48535445,48577454,48283115,48220417,47569379,47003969,45870034,44596114,42544733,40236814,37204805,33903916,362797056,313968931,347068416,356870648,361832386,362432391,361676395,361513505,362367272,362131640,362444338,361693454,361683248,360926489,360001467,358630824,356118666,352530453,347719374,340951149,332422181,977326736,614529680,821076736,902546355,956618297,968170056,976206075,963714890,971909397,969968974,974725991,970473103,975895952,968795195,971467217,967510749,967249092,958939866,957271345,942120976,932119119,589934536,612607807,562009551,12293730,368083000,476638589,563498650,576322690,550082323,557440145,573808256,569319000,583386364,575101413,581905861,571980682,570518287,562961725,561281203,544840842,529773430,381059392,791124863,296504945,184331454,858993789,504957297,79192107,215738845,341207179,160096236,268381942,249781710,337145418,287806806,350624772,303771999,355081082,283927931,321942867,265648373,295633056,999999307,618939915,598904791,83388682,310360458,137155594,846447717,730256348,564052427,779036151,381981889,473793629,746235769,699357857,846647452,817851146,904983588,821432348,920987929,774315014,808923646,311668616,311669316,575981086,737474260,193809118,138153303,191160144,265404046,246006184,568971094,693651205,754203134,33762140,888552056,570633143,447383929,932962529,568413099,81840384,633916273,60417840,8365487,696696878,8366957,345611301,547352392,290138331,524361543,303499282,232786321,204842885,689904785,450900005,449051123,86263204,79065223,381011538,434144932,220102056,144543516,655026612,399448023,160381493,152016006,537044268,848714039,778665672,275866538,4310724,962296146,682720207,135752994,26996133,96216586,601067129,766800325,468372875,448632258,774680903,921676337,823821483,897838445,886261349,565141321,404759828,465774137,557985123,441806133,28208502,597383557,214843975,413720080,286586177,344046526,746226029,417679677,171560146,222440416,128702504,900395944,842272419,687059377,496403958,74805617,755798832,190657511,152017612,716498270,914181627,439069496,543571489,72536818,388746614,148510399,98726922,8281267,511717528,286763408,413097927,52731751,616684529,626597905,596941725,201874374,388122557,185921272,430122447,819597496,929918804,180406896,813528937,957963457,725097600,785478065,235049717,945781926,808069592,232665517,386656089,45726282,482854198,339574628,193422949,455471510,82570369,11722119,896067736,710146464,986016437,981521281,748391911,506600816,603947661,181756143,912529684,752767506,913025413,231341357,270618985,624121084,147046793,900168842,49721085,272857857,365513061,369949931,989618869,409629356,513561627,595887213,684704790,120507559,830323706,796941962,147064048,709822373,90269418,122382145,398992199,438665727,915273642,16300536,258918930,972803962,786419484,127701480,7200518,756933765,258082789,848453440,429265353,163000162,258885534,607864889,979160541,732558874,744497904,202409850,596058162,217450188,872098856,478956404,643133122,96327352,301256944,343881371,976154920,418412782,49399597,998566407,740483618,449719112,323025663,158747142,718884855,786167858,191762239,526037193,198179066,258809204,749846169,340455356,372455754,47215746,607205373,190469779,937698084,462578477,158896393,330742737,498090282,499523882,511643776,339895684,17038536,666472153,444674733,210687507,654874907,470677949,636457298,695224309,482711139,990523758,218906843,454930065,897042732,774543763,79143731,556983341,830266619,1,Z,Z,Y,4096,4095,4083,4017,3797,3302,2510,1586,794,299,79,13,1,Z,531441,527345,531428,527267,530998,525760,526345,514474,502035,470419,430469,369681,302615,227240,159250,100178,57720,29107,13170,5017,1664,16777216,16245775,16748544,16773042,16748114,16742876,16770524,16727498,16702519,16666748,16525155,16311313,15986300,15424260,14653370,13642778,12340762,10834541,9194094,7480267,5830808,244140625,227363409,241483420,243517024,244111523,243055690,243945674,243471480,244035808,243389478,243645129,242890943,242946503,241339744,240110528,237147018,233806563,227838351,220785840,210758927,199099318,176782322,932641704,109673458,153982108,173785149,175697387,173394460,172826358,175744930,175098600,176067406,174085825,174429641,172616290,170653946,167362993,161150895,151522521,138090108,118001747,91387447,841287110,664504788,11208985,477608821,756030520,805358323,837899248,787571887,823184199,814354605,833716183,816865317,838199429,812607215,825942727,811756296,816537720,789256961,791651070,743159226,718871308,719476260,878189157,189129294,312225195,573776766,165380141,613574790,665761037,555639090,590283256,663946797,644574972,701847000,671286469,697838321,665627220,666378089,642615943,647604018,596439361,559387823,429534507,710058254,860326656,243915172,949968819,263427907,906783099,615932237,265697337,362132873,941192328,837476407,272445960,18335330,331464432,100164418,356060228,35336133,254544085,994232636,194929353,999993007,570458500,201302364,909229698,887824642,294933375,826539764,491905625,768112453,932591373,826592748,366316231,882051935,625596906,389832207,240526018,660304701,281113779,759218213,120071675,356077311,428354755,428361755,426107579,52645978,93850977,430683503,287759789,573867389,550463582,242823377,254954496,252344621,746565992,705531006,873604968,993552714,863198513,636962621,616784103,68740453,562437566,100385844,672031096,100401244,399911319,890144674,586729415,473649068,99811120,140945634,636012375,430644647,924375717,465025894,580942230,109434103,7717532,441748233,53771887,446882400,598763892,832142025,84959395,984573558,916581283,656617667,896448580,924593894,377622041,575161904,316225705,410899477,837566930,115839343,449599445,744173026,619180712,369145226,345146954,498174281,304372790,176936031,517516288,911978445,827019050,711206757,201557548,743624126,433809093,365770393,946718466,635070805,377451435,858832612,327738855,636194799,571192069,917154764,712473959,980367455,430859616,281267026,701453284,64705539,336982403,425003965,327445106,605626989,37663911,324562469,131527254,282292808,729621242,500720677,375597590,623454637,825823542,293733244,342158722,299852561,475856775,101785195,391958756,99524493,964645520,974740338,637757935,281066090,477785650,75117163,93187587,278429382,232980394,190518490,633896230,454456586,696475874,643729372,28415166,100976044,937610496,233949184,455118923,527278668,27198479,595111205,233151407,258411076,826583090,307378422,643858505,483929483,770798033,164300957,491800107,413584293,773130133,307396146,460656157,996471769,964986079,306598020,492360260,288076666,495042677,980655971,386963243,373328359,140176952,167532778,403487270,333519230,102364175,820762048,850035173,722550240,408293978,423590057,875120640,414669644,266527437,882892491,888998516,670580775,428253618,325136499,174231320,745987981,903572963,530244604,917608801,672441066,312643649,563584183,97359360,931971570,67769966,956201492,699292305,177195209,908295326,553588883,238788095,412606683,457073540,889620764,855381103,972856217,988206479,971328007,67755044,682447411,248688644,168756774,685302081,592502928,342499872,632835397,662054491,581162912,820451706,80999784,406997572,708499791,710614453,732636470,418416082,171801610,40611254,242094396,459895852,488567852,459329449,805463032,296061051,744901059,681412700,426570244,435273852,586088544,465445802,681363746,916826770,612539380,88100854,113435389,322116850,336211413,367765317,810166969,730662248,1,Z,Z,Y,8192,8191,8178,8100,7814,7099,5812,4096,2380,1093,378,92,14,1,Y,0,0,0,1594323,1586131,1594309,1586040,1593776,1584025,1587120,1566579,1546651,1486928,1406225,1270569,1105275,899536,690691,486668,317942,187005,100296,47294,19930,67108864,65514541,67047424,67100581,67046891,67037140,67099620,67014104,66975443,66924847,66655266,66233467,65553634,64282284,62414067,59773000,56111082,51520963,46083949,39908284,33394726,220703118,153594254,212200062,218895803,220641145,217467323,220259881,218809326,220508987,218689168,219730572,217745653,218455352,214557546,212224228,204888107,196879952,180812353,161190857,131068152,94064434,60693925,839990814,775481260,972858869,51365525,57458130,50399105,48461245,58203590,56383771,59244058,53955786,55782861,51498929,47728305,40202554,25855091,1634503,966897576,911669102,835341438,889009735,828315810,494478513,123047097,538547918,747460829,878714915,676603444,828724415,789094577,866704630,799506705,882375820,788367603,847978245,793836665,829073126,736875486,772144892,618374467,574546478,755810045,866800317,396945948,712694294,861815157,40331066,331460791,543403754,81709314,239790990,565083478,481723576,708876220,595151917,696155496,588428747,609433003,531251625,581594778,423352275,348370540,865810542,110000497,40068454,380460470,114368439,422826680,210471687,854474650,191709811,706973978,751495828,176814667,305078522,8995217,548581909,389390623,655378574,168660215,343513462,97433046,238042135,999930007,134119465,890928652,75902733,688181028,990293847,869630805,584874674,584462755,841093443,724740831,830553453,70419093,696628282,570368957,770559850,755496609,9725157,257251610,433318125,774766424,711902277,711972277,262143186,478006939,183793294,879191615,78365684,519694057,822892026,252369458,436713101,742150661,841614843,687449714,664794530,478643783,240547252,729081366,834302761,161511722,652226581,204630121,492727851,204791121,898119206,266839747,176661754,683776362,842993077,92627261,265961521,30834565,234878505,912185998,640527217,224451681,604413548,78344252,38560078,757431523,178953390,752982777,104472128,899842014,823958085,392715458,132455767,15480748,346280482,731342249,556080053,821283682,567887709,325825045,812028005,689634795,859311947,87628427,103861019,486084337,957078253,995910927,728506921,767698146,663226018,258052060,684304372,487458916,289042977,958878404,849018013,47403247,688027191,972156969,714029912,278629645,352860806,727645019,271181761,131854309,221102934,769095328,799760129,534720935,54736010,287037871,845791761,992739945,942638565,789015157,974154851,225286866,737583406,823331509,492850141,763281586,772102124,760465215,14682883,533457687,392626182,48667804,477171827,553670400,328561882,595845303,541109293,972427463,213918666,758317037,9936467,388454326,598969292,894144045,525320325,426644273,469069367,491074212,634148123,399495626,74566973,765666818,650071182,417031747,435791630,297963438,963573898,367728595,528066677,972095457,178022002,763551394,276816030,728052091,586222249,126776553,18910287,990020444,619303912,73496132,545170750,22080957,133395406,513452967,287746440,221809417,682065038,719910420,756336529,452440814,790985430,354871261,662577835,534554872,781799264,399980254,236736223,237405588,967592628,31031922,17630677,639551849,24633995,258422004,269789489,713775373,610826063,764947244,167886178,447975765,173344017,30828866,652155623,435768851,379972778,791213212,590026665,320980507,416052943,573291359,238671225,876392349,355058088,650105649,63197517,749042445,161751131,4960803,54604944,426560007,258673829,853380962,782398406,931473487,522689869,471566478,121790172,231210452,48915222,442095901,490165325,150133485,178911724,909470954,373410836,176227391,188105586,613025267,263634632,143439940,657812829,231252822,743478216,685568475,122324357,926127125,429115067,27639137,683161094,971660166,784623773,494681272,264325095,786654916,604738273,343126768,535384786,900618524,315038066,984915344,374692762,1,Z,Z,Y,16384,16383,16369,16278,15914,14913,12911,9908,6476,3473,1471,470,106,15,1,Y,0,0,4782969,4766585,4782954,4766480,4782303,4763841,4773021,4737724,4708164,4600158,4446903,4163722,3787881,3275380,2699598,2076895,1497681,991615,606336,334595,167898,268435456,263652487,268304384,268418967,268303733,268285271,268422946,268251692,268195014,268137516,267640369,266847679,265506058,262797178,258566745,252169367,242689895,229932394,213664160,193771451,171057138,103515583,835080134,76412092,98245190,103383860,93848611,102512052,98077915,103150625,97920059,101602621,96194318,99439298,89946818,86404410,68875574,51275358,10586025,960181411,876472962,768962747,364163550,260647967,156204005,25046441,335081691,354496578,332719667,326257971,358221885,352991319,361202772,346864739,353935074,343745520,337458916,320788332,289683503,231822211,147712086,5227255,801320806,223068103,858904560,29708889,653301789,783223142,663534525,191624220,381647080,23038873,848227187,156658711,887947226,208777723,857545491,110095798,894184725,77490528,752472818,959537313,463903521,449725918,46480318,823412222,832601832,375676423,806690440,706243052,343906485,205059295,270256997,976279986,393041077,36902075,922860652,496682566,877532212,503771085,635799317,362343005,634363379,134928323,45494252,792294829,745814511,123090520,632320593,64745168,340928597,381230196,981840647,16071501,832653049,649006237,490425353,795549671,240305811,762760297,917548876,178370347,133045842,208053874,102282146,135157465,999300007,207005178,371479129,949557012,160679725,548082187,581057011,22315427,628267956,39658220,556787984,158980635,235695623,985268312,316437795,1596553,323461567,182935974,670683903,10995422,55992742,830924998,831624998,917282672,984950418,338659082,494171100,680079559,58944909,752667126,890450825,388412975,573574253,989647554,343212809,61413964,593981803,51524971,516687589,561553972,231724779,696251317,455561438,624636447,457241438,247274070,807391352,919292209,257443369,384691658,511226326,489109312,933496735,198210693,143902818,922132406,422347798,202771033,13307549,452742495,93418644,548003359,865277688,358137657,902576226,560580858,528829666,269932846,853230672,994403855,585071158,504155751,94090181,343818340,775331076,46479037,300199822,490646414,31027673,180727292,830440082,335187871,313219230,219702445,747773974,389636317,427390863,345298296,953362975,729652562,391311807,785912779,647049532,209878462,152056714,991620724,827607334,689836139,633517648,347085152,334827553,491931132,478070153,318252762,508488087,821040150,73266176,292708,462969079,145802502,777210734,738677594,625169818,676643834,655600108,242951917,341778394,265400249,551440810,706783824,878414619,10652552,530264943,249412705,367284537,882941892,533524785,712484642,37976844,591836144,397583207,315796362,41162970,399596561,911570529,718664566,310460390,946037247,809638525,657428029,263869293,590899254,281242316,476846192,104597917,104697104,446691607,380756154,847231376,793411878,821904130,849820722,914097517,184629708,220095259,871279362,378130821,121063719,122059556,218250623,299781129,464060709,205165263,128473685,952029345,36745885,768038908,78380096,958387476,577631322,83028505,993160102,941716082,257565462,602834461,32196995,121759960,356910600,541763333,337183154,757237227,327505115,125257607,350463318,587409795,529660660,868889140,452445362,310605875,189837361,231449892,319046733,765876893,441205966,454048283,85421748,271098657,169227309,859251402,757582688,908829947,168006679,581569646,6128982,629308834,730205201,209668929,100339025,492156049,441773735,531200084,341362723,494066805,866000251,539122326,485116279,426021141,167801567,66529015,477842819,83726615,279900411,504319669,958441465,318341394,834278342,81275593,220358827,303705199,833518772,554045696,814069318,282869234,273825479,572605716,467914273,850836007,833002253,561385705,310477634,727576766,220878973,246501770,218935414,619184143,822864397,524385419,584382276,103093199,72154231,253038208,836914930,1,Z,Z,Y,32768,32767,32752,32647,32192,30827,27824,22819,16384,9949,4944,1941,576,121,16,1,Y,0,14348907,14316139,14348891,14316019,14348106,14312624,14335443,14274586,14234823,14046046,13770138,13210783,12411417,11226983,9772767,8051873,6280650,4566191,3099105,1932546,1110300,73741817,59392910,73463289,73708929,73462504,73427022,73725188,73379219,73301236,73270521,72373816,70943981,68428077,62938711,53891910,39352023,16452633,983601931,938855524,880397526,808791735,517577915,443836098,431484473,502123088,517298602,488663609,515316919,501793378,516878869,501624410,513781062,498550015,510423795,486803505,484250036,443059862,407944716,309646433,189045098,970869490,681074338,184981286,667403378,84707657,872091026,94197924,156066980,88489791,67378353,170899008,155644549,178871388,139336197,163568759,138721889,131007145,94520678,31314515,898537149,706530279,358028019,845689571,561476714,376495428,491165068,970936323,645441157,343766732,464985219,223074299,900203812,141858350,361978127,286576318,530476472,199895928,240648507,359232381,201094939,6147143,989182182,335240908,725194345,371842544,810365837,724408050,460300298,502073849,672656720,527373367,33440129,927286419,32881464,138944630,629846090,49672366,443709355,880782104,536120329,193393070,179882214,411444389,770798879,977129156,130653412,758810875,223155181,733861414,325019902,326485183,567604426,147387489,686097287,190827794,644708656,436581631,40438747,101871452,781979163,271217379,302999970,382413663,232349030,924253953,763741579,993000007,862346595,923952700,929114422,68506369,84768422,868388527,261742933,483184395,53174382,90787361,699234886,795996540,902857567,363610370,211071441,8143103,620872492,570024474,66335568,682017275,140174915,147174915,125099152,952262575,901409157,531557021,196151898,617413273,113686968,658426540,237962276,721428828,857205074,818969130,677902000,840100664,198858354,304958173,213638466,111274505,437917964,466737221,326562306,484237221,679208597,312598175,648488828,470681317,946321982,885486040,501389981,786422647,47991127,971929117,30691723,419711252,174811397,411182580,551793084,536291030,658391035,868283587,655789513,189052292,51739712,533464598,620349023,128438023,938463762,11953202,361912338,967677836,154074595,263599542,160981402,445643582,585912787,79054740,819660912,939450485,985242985,985944792,361951024,468835566,813046060,168676824,788484906,900520772,562803211,405384033,963596973,905757269,244671701,66449241,876364821,454517693,258689635,721096658,968245917,259290502,550942483,510381376,331231260,358319412,315602166,846766607,287747840,340228581,400940698,94173260,122730275,199623089,575777066,881388094,202804992,582648990,768795672,319642178,567863258,696860739,65534782,993347334,653737505,960961641,26793719,536396504,220794338,850951412,725922762,541074292,575610993,914446420,557505395,234372557,718028890,981323074,876452225,610731284,536183742,78666746,917655077,819058497,110490143,314822515,317250416,102882198,472854576,936458079,841650251,332338114,850100123,239296000,833510160,68065431,550000540,725893283,852001840,511000948,116925737,584096619,58639285,40661154,755516569,633003808,318611024,103689823,582972630,250974449,778119880,711706233,651694778,628056725,416441834,851973396,408611099,198746977,51104922,451860478,921893223,716184872,855490612,475278582,586782484,254400260,411123681,610981278,24701360,311913565,606909838,355935389,422712994,567427169,183204131,490546493,524622587,802031069,45060665,452484286,51111019,582393711,331962183,903147191,83107649,907323839,944340525,383141863,966916667,45232444,907010666,624001610,17091772,997215126,486426310,238813229,996606594,597035807,344185078,263559985,235128588,551570925,607430154,212648031,381658899,19328880,332014499,123190590,577710444,283911844,62324216,811212347,95455559,471453956,640985334,522140118,147661615,853812596,616497995,254286310,476587444,256789633,932999277,123279648,682290297,725240695,245712640,865979075,115513014,898723080,704609262,891541470,282666296,1,Z,Z,Y,65536,65535,65519,65399,64839,63019,58651,50643,39203,26333,14893,6885,2517,697,137,17,1,Y,43046721,42981185,43046704,42981049,43045768,42976749,43028820,42922653,42877044,42555455,42081834,41026967,39420162,36849183,33433986,29051623,24121674,18898714,13955895,9597842,6146895,294967268,251920547,294377444,294901596,294376508,294307489,294945511,294240833,294142584,294235258,292638806,290148739,285643877,274983355,256562102,225264910,173101950,93798890,979130385,820041805,612480878,587889561,292922293,315260328,542352472,587298801,501332947,582821805,541691709,586524429,541604694,580252892,536230975,575693266,514937543,524897716,427873530,366583763,136984078,867173407,327735585,596060494,109887709,521998155,635051383,11381656,826248435,23331095,812597519,744802885,76740626,31820891,97132880,986394433,64613047,1735020,2030185,921210309,802266671,506253378,91662820,276521101,57296249,930336977,820449268,61200832,950323862,611228433,122163610,633046780,666918930,752128321,510158793,326517323,22716701,862482379,766334064,993646097,363712711,9120739,466666645,727890536,967606329,682945035,974740338,44403361,905152074,161736169,708008073,653684488,394502279,711322291,755868568,265179337,365435222,20128148,143905629,63018129,515903554,525377441,513659198,593176493,748940027,90199611,344933140,175880701,201140370,261916370,586217484,965691027,767597566,882874514,899094668,957008938,126885733,912641538,996091019,81828740,353040595,271577580,424348561,631375934,516857447,749248753,390980649,558816687,930000007,754119306,5779007,203460137,968860276,242988346,967550042,699809748,792803198,881005039,477863883,732755490,372648197,537993820,642394048,636783905,362533231,531217052,929594979,759336485,566589163,541924058,611924058,275588779,838924577,484111070,742061088,80654633,7689586,731132998,834567041,89787934,28120826,858114426,10458366,122831015,996084464,297455115,218734932,691646745,918397624,434605749,600846617,58922559,782846617,505013224,398494076,445506425,930662538,157573789,596257942,42995633,933834791,87043385,585119240,303115285,158010786,749372591,21469197,301380795,424083858,404904948,197641404,525263613,924417003,740540936,179339555,536772465,556502389,276111649,954768190,640272304,55795795,912090727,871944100,509536236,117039193,323877639,453953671,907178478,924091935,10710366,590690681,759579157,563697882,38434269,495055785,9053579,182175198,127315555,289102159,118964056,317474918,866535724,496724325,165058676,67466481,155473462,545129707,897859269,926323323,438642524,364653128,414861455,601951676,734032462,170334580,716136718,73601187,624322225,253004660,714373131,612908223,819518155,379477033,868657360,30741111,431628711,53996821,715464287,445385678,737101750,212000717,813715454,234671270,456704086,582344008,848311553,517277126,549495456,501669290,265132770,188049957,439172985,223217747,299388118,130001238,76233487,19906405,648914332,420318874,293697224,922522231,366069984,936897706,214471917,920951382,38527736,456183735,254860660,70250024,46881832,867944296,787110418,843846763,23155828,354766091,38727263,770937411,406770866,396362242,818511732,391777923,378705959,308198894,327114518,822710664,985594370,517540054,479012318,352852045,360744118,122916464,538585498,89035317,100521473,465728871,262731697,292278811,829121931,319146393,723746341,783122183,218817760,819710420,787211212,223672293,759350353,209740456,531286845,13746791,927085949,887441356,90346897,407774633,697310320,170869328,917552285,903498029,877681241,437803589,313633015,112763251,495597838,669341979,256325102,794835308,237419084,968871550,592010272,480032116,948745278,946900913,706080744,551198614,911894008,786211644,916633240,967427846,507389308,631374726,225884370,356896032,341181672,920249414,802923297,828394053,200167735,839324604,917616821,268591074,4566725,524534616,762722549,451192416,232168774,652547827,135480341,827229040,728377652,271713190,604696948,303619297,822485677,991851631,715575287,678216898,802505604,151451710,426081420,982834464,793125690,1,Z,Z,Y,131072,131071,131054,130918,130238,127858,121670,109294,89846,65536,41226,21778,9402,3214,834,154,18,1,0,0,0,129140163,129009091,129140145,129008938,129139040,129003566,129116736,128928222,128893356,128355152,127577352,125664256,122587614,117296312,109753974,99334792,86646486,72072011,57002616,42452451,29715525,179869065,50728902,178623881,179737840,178622776,178487302,179840997,178396046,178290120,178746961,175916784,171709572,163987477,144021570,108074544,43806979,930844315,749724444,473117224,67582120,507239654,939447791,759578726,78513371,804737068,938201502,680178917,928147838,803395274,936734470,803638137,923858397,794355813,919189366,757000812,823329628,590022937,507953483,982142791,418976023,140845597,399147316,659326254,719878470,465013668,796211601,772767265,400057380,740432721,525793864,581839945,448743612,632412565,317989743,562418041,396586404,444721378,258723750,58828961,409685428,563888346,726032162,964930691,512358797,853032550,578788546,529580450,479479048,472535796,593465264,755091840,362503228,672594218,673384742,453743907,362505580,675168088,717094679,757599566,62713156,400580467,57880923,162098235,844830585,797922655,285563858,270505362,753877991,227138951,425934309,377896790,40655691,840902485,116179112,941358066,442380021,677322946,545332459,391283879,417278692,416995494,853226052,618557182,180028332,660745582,582926302,785003654,254839008,45021745,499002756,259407582,228163951,315826722,625906132,361228448,613283955,249956830,94699090,899350497,66483378,569155505,494718431,719497512,244359878,621706448,85708877,300000007,717073712,931491732,325516290,245247,58928834,798933170,357805989,907740915,78302153,969614136,203831503,920010088,294142357,252929501,646431966,969570012,425728314,861626690,344606465,219881424,961164603,661164596,388266405,237067040,8121132,613195882,28974771,593773087,314151436,462008913,630778725,521367516,264269505,383007649,243743426,831113076,442837938,637846650,769711271,748096131,32953793,210159355,248994759,100159341,151323546,748302626,600755671,375914150,723462065,160360882,667815303,787203709,770362275,597588848,986614526,311474748,856728195,525313168,87950353,558102246,291505795,230330998,828426927,618267572,654553408,9262310,661383345,855265846,395621089,529800925,967270143,221423447,855187797,77388009,215856413,647973563,133618509,602442813,463433604,12717440,65449785,12715481,419210675,891770299,63343372,467218525,405113714,239896745,481854047,639611774,983380201,773053364,883201142,648218325,150891180,135526039,711316935,307613356,873579075,535715919,418270302,651915859,866256780,73970544,10486853,118716561,252578575,491405906,152866557,265223788,388333680,780767333,801248966,691420913,377644918,411404958,828957431,690498466,426329917,978418297,255499408,877275466,149208579,960447800,638455472,317504065,307017212,842869849,308879270,134642860,21666098,553924806,960330677,624452173,973800896,143219572,566687401,633456667,985491884,100754381,285435502,900649209,237172761,328548365,398181575,415075969,654971512,337467447,165932889,299984200,155131444,194804394,964089175,470127735,682850470,324975733,719267325,577358855,187503422,862183282,962972742,59332980,238116649,859133976,782622283,467545174,435240828,315720909,660749404,98368778,597770806,472610014,263451017,911880364,555309247,960612954,553621837,232392247,643865229,242460880,639941844,866916188,973225313,865525686,519883373,545585541,707329847,464499276,94449985,778729083,784506975,589706381,325565172,639697628,327387522,635105229,396242918,53657709,813028675,739125003,811275790,223792116,609434120,616931682,197867456,255461020,324314617,847599895,342779403,600642257,506192272,486740493,321727955,744227816,441777155,816472140,188844959,53599055,582748044,223391795,406459084,871265448,935342627,593404281,764124168,264559685,603828898,353629018,353792160,354994655,95901225,495258975,969574945,70745559,488179392,315471058,401814778,427085379,728121942,728323316,709087137,570938559,407972357,24208948,630376554,981775778,2436774,97367703,717034287,108618089,850253630,1,Z,Z,Y,262144,262143,262125,261972,261156,258096,249528,230964,199140,155382,106762,63004,31180,12616,4048,988,172,19,1,0,0,387420489,387158345,387420470,387158174,387419177,387151544,387390260,387048524,387068552,386176730,384953718,381596760,375950892,365548182,349747194,326385078,295825098,258053289,215786649,171527078,129211818,719476260,332055771,716854820,719213945,716853527,716585894,719440505,716462984,716388764,717769046,712731690,705806160,693131016,656873802,589299654,462672588,228592464,834396758,201222854,224253714,801319814,697238927,977762674,985295525,297432134,694616194,920294021,672168763,294681173,691767043,295846169,664960250,279884151,664368674,216283701,487446062,906432242,881742109,682902754,599986634,668989907,745617196,955957503,258718576,998838101,325810059,184835086,179012590,108911911,437127875,776033024,380112150,898666026,995790262,745972149,291627316,528087747,73621891,807335444,386804309,770016098,743259829,777147283,586511558,630554062,979212519,521637800,837716409,23285798,739465973,526026968,196354087,973357694,957280599,78260348,253066184,674288363,112490543,642670315,806342135,191524916,700432944,385710010,669088784,383381198,796869647,559551214,570261380,975141698,241574502,102018378,322896608,18474479,781449451,786449218,768230368,24699522,611100395,915193805,511578330,705164583,98082673,169630341,607276819,614675900,246336683,862955492,437366849,979133286,327564285,625846818,308716497,987293162,881429971,189473402,294296682,784417736,454482494,872469543,614670547,55796861,932314550,909483794,615475795,252965777,621941586,49,753663373,254011166,52604088,939971334,941770848,415423410,677625810,289908586,943136775,574386805,206802913,955182403,955203217,511384194,461672660,778180430,257731109,773753394,151534768,301008837,572810563,572810514,833800521,828595524,414698525,612274890,80039945,453023878,260608288,424313847,147197312,676830204,481924425,525074273,686891655,620323473,989387385,102194791,677862597,837346988,84164532,521912246,949101690,121912106,119491767,590968723,776970868,514675095,640306335,111492646,753038661,598352817,625931887,908287500,122505302,405916944,130847607,110584315,614450208,190000527,704158048,142706025,769549981,247637735,895776690,506739257,534451840,193573983,706498075,481478757,143219925,742267063,363080931,885078730,155925228,946234184,644435767,596339422,178487579,499621649,175910079,582771919,926708119,484784102,715234128,180003494,747528835,53010454,335028198,140921115,934072927,404842457,377850151,561426747,724860400,101481364,661468305,933220942,753141400,682721878,522373498,110766707,12231915,781608094,157302795,672518700,476068240,675352702,425688738,505325739,932982413,869241604,740326350,634335443,801839876,763752401,849327011,884835371,605739635,210088056,515581163,199561628,9820818,706822218,195314638,80065005,922762217,543415640,318264100,969797148,375472615,13027243,158634298,915495090,120106242,41321367,84515353,762280551,845229384,788026016,132850266,362023563,43382546,394602776,73078677,924764002,134515627,54450622,788449485,679572225,465946138,785948354,365690226,532282272,556244149,468217569,381399033,357360359,864625516,560171128,922020795,141650931,416474185,149657714,32509508,655475006,963445673,682976327,548460700,887838194,107182066,977899708,307114689,398471038,79432676,795484876,891262597,782175994,613369654,249087688,368275552,975468886,634464563,101630829,698118414,24110941,163621539,546136196,794549708,111573381,870546949,846328352,358384865,398011976,444733292,966149123,495248178,235406579,746645862,845426074,914655663,924950520,194968326,774987131,851719893,696537026,135684322,940764857,66221296,12845056,218295355,646892416,645638038,378327168,679603957,696344957,898124328,416761698,87414551,963649640,541239218,956635563,552604876,558806829,43206905,460283753,297972551,187868430,159060205,252309819,13925711,1080655,519276294,352771981,324923920,313096288,941089400,380656587,108949287,563547344,293893623,989339113,301019923,920724056,653166636,267976618,47933910,721417288,408253254,104329344,253390474,1,Z,Z,Y,524288,524287,524268,524097,523128,519252,507624,480492,430104,354522,262144,169766,94184,43796,16664,5036,1160,191,20,1,0,162261460,161737172,162261440,161736982,162259939,161728888,162222946,161590321,161768485,160293799,158457089,152727201,142750891,123095827,91477225,41680447,972156510,880263465,769820418,645367016,516632307,877905026,715643566,872400002,877380548,872398501,871867450,877859995,871704316,871759417,875310517,866243546,855095010,835233514,771084002,648195290,407690174,941084989,118726798,734413661,494212175,68410090,486194614,608289595,962943919,296539106,480688089,157206981,430837580,290862874,475037546,294287530,418548303,266759265,433983050,161449352,112826827,603263921,987742583,221550816,373081435,798256274,432434864,735744983,249550369,187791115,413883003,76769225,406757350,899911893,816628405,320628971,139878955,613000173,996492370,275864801,992470843,876422049,687511440,572177469,419022057,590472111,938773874,638723972,105580878,369835902,371846749,191727524,235462263,702776825,269747788,11980171,832333426,629931191,804155483,334177558,359531557,842302073,143857745,593948643,669580395,217637922,584613989,208018572,895586512,67049563,961468692,168112156,438193931,567156201,588160795,717620804,973448863,951325181,945533841,228632255,738290394,654886521,72936772,581797506,222516866,110544756,902024471,638866481,485823299,883070153,217030133,149980570,967729737,203468181,468859176,594962115,815501164,954872228,101305744,178088667,84591050,318665511,212701364,351725781,94347255,863830026,397895651,814729342,675419369,138875801,328959132,490,782970364,648708221,175877731,871952455,632770896,393685912,904204410,908121887,961059031,946967405,623072666,67568959,190488051,264475987,747594772,706000861,872219238,215084982,175035034,137990742,300916151,300915661,403489076,354870259,469318931,982095830,632087035,400735086,895337157,514587098,247883059,122756971,715449087,185470562,199534290,918252519,751616515,613978625,419342634,245950341,504517802,262946910,962030766,262945489,902152536,223577063,501806639,590587980,811647909,658653301,817643842,703358501,84787730,283461398,439406884,252068661,69260740,131292742,278213743,446604648,179716511,601849574,4149683,741202780,819832919,403231768,854162415,851248650,684399486,511892918,381537311,826713553,56207189,666284632,24664171,74426732,244192900,101519755,394542057,949664604,242147775,792413344,961444986,786977386,782827703,607697872,281483891,532656695,17740138,389288675,755882275,8234990,693314086,910617520,108496476,75984148,857254435,978919769,496127013,751782436,980856354,570112891,845028157,890777171,359541911,572564532,733942694,501810171,95015362,803159023,972732119,430200284,315366833,967599042,846263217,868592207,317445397,119047382,551484294,982521433,154571661,748069316,67985798,864472937,96398486,281040073,921498169,283164819,211609630,706992094,726316285,365595660,26041369,155922971,949287462,836275892,138763168,57115721,144081005,45638487,904019595,16728828,618836515,822224674,795248945,748837559,286765645,5725572,938470657,223605801,703992847,328835548,573984616,170335459,429711217,586344310,701473172,302365252,44485048,874446459,347404616,884077501,22454400,274883048,269040627,558890372,733191558,293573802,6808157,491298648,230528796,32976915,405674585,155399564,16997784,466211410,719446186,314065695,685414950,138426563,525624166,296765490,764728568,875229351,281691205,64202296,21701815,523151031,96444347,802870552,253881810,995248891,648209861,327376413,780317463,671605940,980375392,88978348,329060448,453063143,380560135,534775831,736944257,339651004,189639799,391800785,867072848,208582440,883822865,256901120,160456773,986777203,407402658,722179494,679629623,818995638,191435596,409407445,578392329,621166893,820567747,98149720,346329247,411848977,993547708,473325790,148821816,465657730,369039213,625271489,292439931,35538811,99551237,231170401,132759886,318482716,488419967,23588294,141281252,625367783,642685748,774492948,902005483,92526051,411497798,180100926,665229649,339229479,245502711,786168985,660810300,1,Z,Z,Y,1048576,1048575,1048555,1048365,1047225,1042380,1026876,988116,910596,784626,616666,431910,263950,137980,60460,21700,6196,1351,211,21,1,486784380,485735804,486784359,485735594,486782629,485725809,486735870,485542155,486104880,483652605,481038625,471478089,454442805,418573919,357804435,256253499,105744279,894100415,622594901,295450885,932081878,511620083,24835703,500085747,510571297,500084017,499027197,511563953,498813523,499217788,507652858,491057003,473444077,443984278,332897087,115937723,673944474,775283601,122969297,217001840,299300783,429644385,430973056,919352980,698959504,883895563,419436990,447957144,309282531,872137789,408047761,880746464,287882581,832793063,349631961,663005283,772945328,684114710,747075781,184974147,705280090,101196676,297722561,414469870,983496821,344749393,47728216,373126398,431453958,964130066,550853818,462512007,935210710,150397215,511721870,399010287,693216009,669378194,363968114,380257757,160535180,925237887,496820611,399756550,739066146,324596276,584200880,49504248,374654516,892748875,288726335,548156907,778512997,183320764,396357247,803171785,64297403,350556241,671341401,495274405,481633869,387006962,510595967,897234560,677576451,536396504,797330365,407027079,922639225,671232849,357791952,528113805,345487265,921076416,199702570,580961076,139455238,270669502,568942823,127249395,387507162,705240325,322419834,641847142,210436006,797283053,953271190,416874686,102587498,867381193,703349701,410612849,727778345,46492387,337951095,133332396,333505504,348014254,490400117,200976017,47469754,35746303,475052926,319999518,365000854,104728486,66777607,4900,46733717,122617150,914795621,906724469,588457245,650520292,290031287,815951460,180066113,596382720,281891923,976431649,962859955,609042769,568879713,580772711,690592017,314349052,444382348,96172787,310077640,310072740,16203825,173388095,920462137,35316765,690818892,514036762,285031720,579362237,906455460,613585258,848276929,366197501,137147378,435648256,120628471,669195853,206453046,363197194,949162464,155362899,845285266,155348199,10785926,361396174,293920085,407104545,836675434,66216247,858632042,333446834,458870517,837871496,536187828,420258923,231739594,178205898,14448951,604299794,649958374,951257191,53945879,898582987,725545268,743849136,765440599,995137427,220639401,243014003,639349504,996106935,110711156,314309173,736454476,51375854,222006374,273246158,976424249,669388516,383574918,743540880,831153731,17683327,963737455,603382270,9991243,689239400,699705936,731908041,589513850,74010428,350366459,203625041,769959557,665312795,15113302,868028472,696560971,135415624,425285300,12724762,463175577,756921685,393128630,375445303,256189091,916918546,730846219,524104847,932503132,486348410,444257896,409905790,982694349,87822289,376708800,881011193,243473768,721412179,909073561,218538402,560268289,431830649,2387328,496641140,103512510,739410205,181468785,29122275,250553861,970647416,50305111,176121484,486532093,265835471,660270045,944047117,264382766,617172557,824924689,161045806,346958859,577204617,68861178,87534599,875015937,378374797,291049136,633360963,984615073,892132286,498084548,572183767,928485666,217450484,194669717,538746745,996657098,735930672,547774372,565876914,539420603,489851912,602809012,157134448,574124898,284328401,409312471,166885843,709318257,15744043,603772919,958935777,17356292,234257551,126776962,620485900,560061809,174960010,825401369,939412453,481650389,588701564,899164383,858980570,409600088,355597716,832442586,548114185,222113791,124274386,906557001,125760413,788223637,163834769,718629228,377544090,451223254,675383514,796766957,961255123,832999352,410192727,311496545,657824516,407094748,84078133,289209402,138022365,305579786,982217973,560412158,315208058,393934858,420278372,417731844,582863010,738381044,717747642,317179923,30282299,342913458,425751215,337322128,335838651,711211136,843208944,389657919,401170567,141238509,3216144,379909004,671818712,908695950,800006981,118727186,266315197,943514601,461354312,900125403,575194862,691717199,558965854,550629400,718944400,932193712,785228682,210726701,961525355,404386711};
int main(){
scanf("%d",&T);
while(T--){
scanf("%I64d%I64d%I64d",&n,&k,&l);
if (l <= k) printf("%d\n",f[n][k][l]%INF);
else{LL res = 0;for (int i = 0;i < n;i++){
res = (res+(C(n,i)*Pow(l-k,i)%INF)*f[n-i][k][k]%INF)%INF;
}
printf("%d\n",res);
}
}
return 0;
}