#include <bits/stdc++.h>
using namespace std;
int n, h, hh, h1, h2, h3, h4, i, j, ans;
int q1[1000000], q2[1000000], q3[1000000], q4[1000000], size, co[1000000];
int nq1[1000000], nq2[1000000], nq3[1000000], nq4[1000000], nsize, nco[1000000];
int md = 1000000009;
int la[33][33][33][33];
int dp[33][33][33][33];
void add(int v1, int v2, int v3, int v4, int vv) {
  if (v1 > hh) v1 = hh;
  if (v2 > hh) v2 = hh;
  if (v3 > hh) v3 = hh;
  if (v4 > hh) v4 = hh;
  if (la[v1][v2][v3][v4] != i) {
    la[v1][v2][v3][v4] = i;
    dp[v1][v2][v3][v4] = vv;
    nsize++;
    nq1[nsize] = v1;
    nq2[nsize] = v2;
    nq3[nsize] = v3;
    nq4[nsize] = v4;
  } else {
    dp[v1][v2][v3][v4] += vv;
    if (dp[v1][v2][v3][v4] >= md) dp[v1][v2][v3][v4] -= md;
  }
}
int answers[5][1000] = {
    {4,         16,        64,        256,       1024,      4096,
     16384,     65536,     262144,    1048576,   4194304,   16777216,
     67108864,  268435456, 73741815,  294967260, 179869031, 719476124,
     877904478, 511617885, 46471522,  185886088, 743544352, 974177390,
     896709533, 586838105, 347352402, 389409599, 557638387, 230553530,
     922214120, 688856453, 755425794, 21703149,  86812596,  347250384,
     389001527, 556006099, 224024378, 896097512, 584390021, 337560066,
     350240255, 400961011, 603844035, 415376122, 661504479, 646017898,
     584071574, 336286278, 345145103, 888274656, 180841172, 764267207,
     793045804, 664483403, 122741630, 991173839, 684691590, 589073811,
     715104,    813705529, 840127848, 381376675, 477677347, 15886515,
     179137919, 790526080, 719553987, 145974032, 646765338, 421218284,
     813853517, 746894635, 536474223, 11792506,  577650145, 773382959,
     334765001, 486031311, 918649689, 517979318, 468831935, 508505406,
     927714043, 781876177, 918293222, 58604900,  939955270, 855250318,
     127170219, 896969265, 141655742, 904041434, 34991602,  730856273,
     283846787, 810097855, 108207475, 665250588, 225171240, 182432227,
     43473661,  177896870, 972307176, 703973065, 714526184, 545917081,
     173501295, 732295669, 826289908, 777044743, 427825921, 738031172,
     639073142, 599711080, 877439116, 329243617, 525183343, 159002891,
     731024173, 427771103, 205219291, 192844448, 130667250, 357127119,
     226600981, 772159603, 831346269, 476560857, 768229438, 653418401,
     145658533, 65681405,  199064156, 495656141, 50130365,  114181303,
     88225353,  311138357, 87800123,  243094309, 80767574,  577235336,
     782288372, 824467011, 726775516, 809168029, 420376801, 668905702,
     117766243, 740045317, 901259022, 446157420, 306054630, 656703824,
     983887565, 169902729, 239025149, 864491404, 262479782, 660739063,
     660473277, 678093235, 927743428, 65393671,  424825721, 302631095,
     66256883,  588064281, 765429107, 662980970, 429685572, 635460078,
     79849411,  138071062, 459068160, 553464467, 466318596, 143517878,
     126494342, 12561496,  143909497, 523001433, 407832238, 369042295,
     55721652,  693734788, 658860469, 368974520, 641107716, 920462769,
     128901328, 873367860, 270345930, 831029793, 860722113, 660908835,
     115162282, 853996002, 544011514, 156599537, 54920114,  103189058,
     108484327, 19226159,  983823059, 116091568, 153345937, 153501052,
     869195680, 73250416,  65637303,  350571939, 88763600,  898724125,
     841496803, 482677728, 604320207, 362154750, 801358090, 220874513,
     737147282, 439430637, 403059112, 507982760, 653313908, 960112056,
     659772154, 216323079, 587966059, 841220394, 983552268, 528480822,
     301469902, 352870219, 19358038,  503707959, 154586978, 101129259,
     974292924, 646006900, 97614556,  441732366, 339020388, 664160973,
     179075658, 883332109, 561633880, 115140054, 614135430, 5332371,
     263537966, 71229689,  136701583, 338679728, 632400381, 128677867,
     196488567, 890333400, 512733361, 148856980, 332139625, 639458458,
     778876571, 283445766, 20482687,  358289526, 641052808, 361484740,
     841381650, 719982421, 220987845, 341547901, 630346844, 108944255,
     36038868,  955754169, 210843373, 724877734, 462315335, 124986668,
     430635814, 717684735, 171316423, 636594074, 493574478, 430987664,
     927563465, 557678113, 104934616, 191679805, 126634959, 854145442,
     536672775, 534824353, 461755452, 124776009, 421124822, 914322271,
     237098854, 72480971,  505455427, 399361214, 318743035, 440134018,
     65740231,  53610409,  662323116, 988884111, 903577257, 19873026,
     535434622, 153407032, 228849319, 729775781, 447730226, 207288491,
     350000093, 634578170, 375063268, 359860062, 274217575, 800423815,
     988693999, 940675813, 614721998, 637143080, 265167994, 210732354,
     503546998, 173571913, 47671532,  476467992, 890827455, 607517497,
     849490336, 930291747, 256822706, 202142500, 718586531, 633427069,
     190673714, 212824658, 795537558, 349721262, 470283491, 441617136,
     171384371, 491272845, 54459441,  370092877, 237616646, 501734797,
     855635688, 978365714, 276772843, 556467133, 467945020, 220093248,
     615247310, 733580788, 320411679, 205275288, 913040544, 588612760,
     501463312, 146018823, 350688363, 821220094, 887020429, 72732427,
     668927499, 483611262, 351839210, 708630934, 363855832, 325036823,
     894302424, 468242884, 763594837, 581352890, 229442438, 177395909,
     787609778, 851428103, 612951261, 272247371, 159978211, 954172226,
     170659199, 540533705, 640026336, 473660728, 365378557, 399814999,
     684420388, 806706765, 62940594,  407293730, 286790071, 570572222,
     456510897, 487857572, 109849347, 841050928, 442456500, 477421955,
     809625616, 454631522, 843634789, 578822176, 618462885, 613431278,
     84885747,  510132969, 55122147,  599679724, 435962628, 272630224,
     39275469,  765441085, 391708905, 738988876, 622333177, 830847280,
     18958399,  546239261, 464115640, 314411813, 108061352, 938034917,
     413502150, 670245265, 603582403, 323831691, 316202977, 66196631,
     174750015, 855196575, 138862552, 866817689, 634889122, 358292147,
     993529431, 408394846, 919697578, 903559100, 659315009, 731651143,
     842950503, 369901689, 202916772, 127261267, 623155941, 94637946,
     254980041, 327945166, 311400080, 391983977, 874813897, 814301018,
     564297955, 803818787, 22047678,  451991557, 879146683, 240239817,
     9705193,   951408353, 697559046, 814203682, 476352219, 560126230,
     332171603, 104596791, 933447865, 967079458, 923992495, 669882054,
     583085151, 972119900, 590193394, 263251954, 69546243,  377870093,
     399996722, 124129199, 241895002, 591780078, 351307534, 322103206,
     491906864, 247430087, 267734505, 739234583, 236054324, 197593181,
     321212272, 164253206, 289409314, 587084055, 303096055, 62926100,
     562638441, 670290456, 81883210,  300992159, 554728044, 889265920,
     390326034, 581745777, 306214406, 861208716, 358635756, 591921449,
     817713731, 737303190, 504570220, 920769888, 763074545, 482032885,
     295389490, 512137793, 229619534, 197635672, 971259290, 398895557,
     907860096, 485453748, 684940647, 507662461, 269554376, 48696625,
     801049146, 140129267, 593955604, 81959812,  147953466, 837340145,
     389665132, 618834439, 957230492, 845523657, 883204838, 672953181,
     657267462, 385076358, 416045240, 961038547, 932592463, 900597758,
     123104667, 726103385, 341413241, 257474449, 547356042, 286974571,
     607508609, 370156155, 929253459, 141206824, 503446127, 901742324,
     152054188, 153484222, 935442886, 593719885, 632909554, 340258333,
     752706101, 767270804, 228227829, 688762945, 101991779, 187507813,
     85500513,  897148634, 753229929, 521856261, 103553293, 996628013,
     9840939,   102680515, 359053632, 500107037, 135926996, 542941736,
     635968669, 17751888,  595281808, 924336783, 699962448, 313142936,
     401787889, 240514794, 223812091, 41273681,  352402584, 192234025,
     9656777,   290803179, 631455075, 28328479,  92127730,  664081696,
     210248250, 420026003, 46228675,  141574169, 224714735, 61519721,
     795404219, 742705308, 677157409, 592386757, 832648001, 91101460,
     183587885, 449895139, 878081783, 409294197, 214156173, 363092291,
     941121994, 158905718, 97685740,  325782019, 530800432, 594137206,
     568725653, 925008832, 785025990, 975949950, 520897202, 571701436,
     171658313, 933807452, 750302240, 430030701, 65305997,  664487277,
     369101817, 955135778, 979735013, 806319327, 69104681,  873953649,
     692489771, 859084482, 480457461, 970092470, 378411103, 62767314,
     404083871, 262215730, 109586423, 20601231,  439396608, 171630236,
     965333519, 344901536, 161027125, 857415935, 148791980, 566192287,
     812190910, 421715101, 853216306, 818889204, 925303355, 401297991,
     716822618, 554311705, 830012365, 168636408, 839463000, 858676477,
     415123497, 385312074, 662676548, 376012543, 501106347, 285092138,
     278552025, 844653298, 518647736, 757690933, 237641635, 19726162,
     223310372, 180004450, 583830271, 160714819, 118456886, 815085192,
     991134564, 933727661, 601718716, 450803827, 764703165, 684400644,
     476958326, 432134605, 873086495, 964522748, 104043665, 13971084,
     935216400, 90474524,  309667414, 967085741, 140322894, 372037687,
     60277474,  159283871, 987639722, 722288520, 258018118, 84973727,
     91103006,  611721732, 461889308, 86347341,  684780800, 976624863,
     781858675, 734015916, 951680637, 122465376, 755721779, 766976235,
     676285228, 929936547, 560913800, 566570114, 710588230, 537591552,
     769557405, 293236800, 527253329, 425585928, 776952984, 108809668,
     895629986, 476045612, 319088257, 15396304,  229411864, 100883731,
     726723382, 967735793, 315746931, 210505320, 298505642, 52124942,
     115000780, 786133062, 724237298, 216879168, 251797315, 147331785,
     386383908, 789125381, 482307090, 128950595, 278019655, 577474020,
     395852752, 515003233, 380447696, 656310092, 884887902, 768477144,
     815384366, 344543851, 637019766, 723384100, 315474653, 944801664,
     849218151, 905599151, 921647948, 313255301, 847627108, 485319670,
     67225461,  472679491, 135834548, 775242522, 141922218, 264741447,
     23732109,  857668718, 555703385, 525188059, 294858038, 141833175,
     988718316, 135169406, 519914332, 795937116, 534323213, 202277337,
     371364653, 546189267, 217765929, 384700359, 156540038, 386473056,
     676745984, 988669925, 811343680, 180044242, 519462234, 634307863,
     750725934, 90621331,  190108336, 269260016, 286188381, 358482198,
     598466601, 240663242, 104121829, 254002718, 29152619,  227963516,
     773927274, 146149762, 738309754, 363105723, 195217296, 398269774,
     261031175, 183624030, 750451376, 893705499, 985799624, 262622108,
     129725641, 967623831, 525383662, 821560632, 472876524, 973841833,
     200540886, 469418829, 884202873, 123161741, 382647985, 555132254,
     830604720, 279276341, 875637238, 295663649, 957433935, 505656362,
     356401451, 874147756, 733069111, 451826244, 232362468, 178628605,
     237686066, 540306504, 295929230, 246597165, 16175440,  844052262,
     707866015, 602371835, 57229205,  614563565, 190502563, 497488314,
     506077784, 355846095, 411321074, 308444405, 509569369, 19390766,
     487435174, 355732752, 684278619, 210744295, 638787948, 359233870,
     278097289, 881806026, 691708510, 883605367, 288384949, 620109855,
     688978457, 704827855, 376173617, 336347102, 283317936, 457903945,
     279991156, 232896893, 370127053, 229651181, 35598027,  882810625,
     125983061, 278635086, 659969865, 21482903,  864848729, 667877237,
     908803332, 38128973,  41172858,  398488490, 249516183, 814079057,
     929199130, 247708033, 152396125, 614411782, 156164641, 537226358,
     698645072, 152892644, 410721267, 577967286, 506134956, 176007122,
     650820991, 168362693, 53585041,  109562538, 57757738,  465395798,
     583377600, 291659354, 118221270, 896981254, 69400915,  520412726,
     548724816, 73647706,  455912351, 802760666, 143756736, 1001722,
     988842268, 657927330, 305731804, 813878824, 291032649, 66003083,
     55377448,  945905186, 521271656, 802716248, 542070705, 625783435,
     614733084, 881888853, 61830327,  114261360, 778969539, 326610278,
     887550492, 243873395, 702082773, 775186487, 641262476, 116975984,
     786896107, 617119749, 581788252, 905439988, 324792488, 435913955,
     436613045, 193118431, 136276575, 589343006, 550886452, 768079099,
     278404905, 697756923, 813063678, 318534875, 703789648, 527104746,
     328362731, 535322050, 477706506, 440771872, 360504056, 805840860,
     165807471, 982987126, 864306365, 323732253},
    {4,         16,        64,        256,       1024,      4096,
     16384,     65536,     262144,    1048576,   4194304,   16777216,
     67108864,  268435456, 73741815,  294967260, 179869031, 719476124,
     877904478, 511617885, 46471522,  185886088, 743544352, 974177390,
     896709533, 586838105, 347352402, 389409599, 557638387, 230553530,
     922214120, 688856453, 755425794, 21703149,  86812596,  347250384,
     389001527, 556006099, 224024378, 896097512, 584390021, 337560066,
     350240255, 400961011, 603844035, 415376122, 661504479, 646017898,
     584071574, 336286278, 345145103, 380580403, 522321603, 481773464,
     938730529, 356672305, 533022126, 647015527, 635467608, 361828235,
     618518913, 103460002, 991495883, 25292647,  155867892, 498467444,
     824794948, 879064991, 130681935, 887199534, 317883822, 393422584,
     182551494, 861902989, 637599517, 987486642, 735574558, 504148394,
     179887014, 949753076, 218705695, 944626726, 871698528, 67475144,
     548894434, 101901878, 861764835, 180152331, 261385742, 420373101,
     655751919, 131241672, 999970470, 231826333, 122884273, 106406445,
     136140903, 915366093, 18976018,  141634271, 504976967, 686557996,
     636796435, 249345120, 849898238, 260017335, 261880347, 370171717,
     123847861, 107385075, 908198344, 586778735, 671521894, 791531643,
     728335536, 716490394, 272454022, 252074509, 831205319, 152262343,
     534499023, 215776407, 885547991, 808501739, 338662883, 76177999,
     682246569, 919161292, 774068737, 713215267, 79890414,  250755150,
     476673537, 338128483, 771254502, 348399406, 527534812, 693444800,
     101903274, 847047904, 628912038, 473521036, 613423660, 855988580,
     266643739, 924741552, 298037102, 873277099, 278272294, 283024321,
     533898200, 306672381, 525225929, 705332604, 646701887, 471799664,
     612829760, 238079461, 751775053, 769846982, 716081409, 973301589,
     380278462, 662905731, 492843369, 816646525, 915435148, 820494890,
     622190176, 728435887, 422995707, 178415415, 717987496, 660261737,
     962861767, 951788547, 476235197, 414442055, 467733884, 802042727,
     345992625, 166382075, 595261264, 403599697, 428161150, 260985751,
     877156396, 278156482, 699583010, 734240839, 194251200, 737229331,
     366065372, 76837714,  217968592, 328414453, 318777867, 952883309,
     388944305, 436831806, 434610486, 965663498, 956016468, 586726935,
     617618803, 544046339, 70420520,  875406519, 706536742, 409276084,
     713460533, 531426206, 405493819, 482341449, 448623450, 151412625,
     39916377,  251813321, 952345004, 619186255, 490252137, 679240041,
     853680367, 528491595, 193441393, 664056250, 44594231,  35136855,
     965655562, 541834456, 875334013, 394707404, 931167589, 19129149,
     128951614, 923204060, 323128498, 665097361, 261831353, 468177966,
     723318368, 792304915, 634832197, 548874543, 306510296, 615794614,
     601402794, 384956505, 947167807, 610765170, 89114388,  589020183,
     512202722, 666233178, 276037937, 662192809, 593036088, 791358821,
     587370702, 392383573, 467606721, 854346248, 684568864, 85077780,
     783676447, 441368314, 72972050,  323196170, 436429506, 887758507,
     474492353, 910351056, 76648102,  467286964, 83693313,  909007564,
     351169268, 205269855, 348493651, 86598288,  572297449, 150935755,
     758906438, 139762500, 643738239, 291444222, 188261970, 287160748,
     493467972, 457573031, 770888112, 751296750, 129159987, 802136425,
     945676173, 462443566, 884615461, 125241946, 315913436, 153284559,
     362918004, 600999015, 251468610, 835022,    319736829, 749935431,
     619707064, 635329540, 509433588, 73035130,  714808704, 231619932,
     23229211,  113911404, 388802130, 364002709, 462589061, 370437754,
     168248727, 771150303, 833461484, 579898269, 173717893, 81739885,
     2272894,   730673636, 524938367, 616405956, 324662764, 147944619,
     590278680, 19160429,  590995297, 22195602,  979989287, 941678129,
     112423459, 293512804, 877878513, 349502957, 643835465, 760668701,
     699976954, 601628669, 988757138, 354702111, 936669173, 619729808,
     502818265, 687859945, 402455624, 233187752, 594913256, 593464745,
     359851945, 646889783, 445731998, 461313394, 690708871, 381060132,
     463757966, 124671729, 624651561, 703387668, 584422716, 495586302,
     130456706, 338917307, 8297677,   354010778, 632409201, 927803910,
     207672926, 235506664, 235594959, 154849539, 305734385, 882296078,
     986185814, 161071304, 780832306, 492291001, 326383873, 132432912,
     366573808, 804963710, 883881264, 465445059, 735339458, 716727891,
     421500747, 489850301, 845199343, 355848905, 980326331, 493730297,
     328495357, 37695635,  194673306, 409025940, 654344624, 779846308,
     312161926, 969883976, 376556915, 254376928, 919698691, 147929923,
     465079934, 950790651, 625714299, 462425252, 48974019,  270745406,
     803848049, 437226149, 708991935, 749677526, 753318329, 888128470,
     228746406, 717328123, 428412212, 818121922, 641949860, 10460935,
     429735778, 980022112, 596854035, 164474932, 484004208, 735666585,
     957738350, 140424368, 405096419, 235066089, 110753533, 885925883,
     424014690, 600713548, 807220756, 621895155, 351374135, 276120286,
     768519169, 757469470, 878725516, 937741002, 650007303, 987354343,
     560287928, 775639865, 247856829, 955047336, 464476175, 197913991,
     291048016, 231021830, 994061203, 560709099, 967185900, 474098005,
     486913298, 749583668, 763236914, 841300884, 728997175, 288240639,
     49732538,  252432036, 457262181, 353416373, 749850431, 182026569,
     800052632, 381549676, 649127817, 313349714, 264927250, 431744676,
     541453282, 550689720, 397857456, 812409813, 912390809, 257847924,
     891232943, 348087358, 155324707, 323266912, 742991030, 233927998,
     214643997, 337684506, 173501509, 263577611, 649069717, 492509368,
     468591139, 423094679, 641642635, 37226096,  824525336, 28070164,
     340191455, 287467224, 527971347, 787703624, 52492728,  870332353,
     993856465, 883414794, 635638072, 693808470, 406184985, 282972408,
     723767220, 887612854, 6419378,   283570834, 310224227, 472083967,
     657549369, 193484260, 168005360, 140087407, 311750720, 86150827,
     928161050, 290824785, 843989084, 838356906, 597327559, 178020114,
     349439746, 115792246, 169887616, 678075745, 802637660, 889094716,
     244690135, 604828653, 896467359, 561331357, 662249002, 296280913,
     465376139, 944702491, 234929681, 48636921,  429474904, 319231766,
     50903406,  446664444, 857705038, 957387941, 431222925, 476223905,
     393463429, 496564554, 817765428, 734526021, 356215832, 523906695,
     55427855,  15917932,  975322955, 248696579, 456744298, 396543439,
     320816136, 127700868, 656623855, 512503483, 343740239, 325340687,
     947392868, 589830624, 208485169, 906564666, 904989276, 156575389,
     449174191, 495878813, 737828978, 648216356, 626160435, 497497174,
     877198940, 558780916, 122509940, 573633697, 553040657, 687654281,
     132322194, 664151201, 91749873,  539204134, 685923184, 563130830,
     766916401, 764698746, 36346705,  658194351, 245235734, 277848677,
     759488920, 821090037, 238266420, 778415529, 61247499,  845447597,
     566772577, 273404178, 391393427, 113477573, 412390244, 431624602,
     180605173, 871865168, 653906347, 159149988, 164557009, 419869546,
     936808148, 841534420, 573112245, 779024796, 428648968, 772771199,
     472226831, 751848946, 275632414, 37489724,  419818682, 91745532,
     235685654, 39520058,  987948228, 66922401,  718882144, 136861569,
     907163855, 348527749, 720288051, 821764806, 497466741, 305067989,
     558801065, 576267986, 578180278, 942285083, 502688180, 82842590,
     450239640, 124868541, 857527465, 939676663, 755426941, 892351213,
     434881458, 535217025, 394401494, 907534923, 584032565, 543556112,
     529920425, 646559098, 981824368, 575591230, 808624628, 363926855,
     404893668, 461102943, 296856740, 334022397, 425694872, 620840221,
     384390925, 232012950, 693047282, 179132515, 477807866, 395385401,
     720354470, 214151321, 582945507, 887765303, 173901280, 846473589,
     503637927, 31467285,  497616017, 952929924, 889219556, 460525926,
     848093849, 998030665, 8532308,   107579814, 14245841,  339203950,
     750857082, 199802782, 509822906, 901127429, 577599222, 59773965,
     747243229, 147453091, 677758380, 781507078, 54625114,  601386725,
     986056483, 820641635, 559529912, 827906170, 314188965, 577827851,
     190577024, 565060854, 621318514, 219689579, 860736082, 487978195,
     883880985, 29379068,  49701041,  918761790, 690638406, 951283268,
     550232235, 280373046, 957749094, 894113872, 676787707, 201333681,
     845756337, 576918620, 973852509, 681054841, 400888303, 827764238,
     283570580, 49063900,  534735446, 198713722, 554337556, 191854601,
     117028506, 997361841, 212827959, 587451118, 343231238, 869073526,
     911385679, 10450254,  553354423, 87161690,  351643067, 44055160,
     158392396, 111245506, 636597435, 337876127, 460292742, 302858379,
     310541848, 463802775, 989978573, 81516967,  257768617, 598280952,
     666200836, 362673582, 703491441, 745722892, 745611756, 566791793,
     608480544, 971841603, 278983667, 796927587, 569788323, 303597885,
     583666047, 762439430, 597257816, 526427540, 288038950, 454113355,
     465404567, 970814906, 346361747, 501681060, 449816238, 912186659,
     407022892, 276054145, 392087454, 22955365,  413810428, 249601969,
     319915413, 946254155, 937142643, 671860952, 774960802, 460025879,
     359148369, 411007839, 249122910, 519496895, 18443994,  749244508,
     757964667, 893488971, 496741790, 695391900, 938716919, 867788028,
     562883419, 113304835, 497347907, 408694370, 66044497,  115341679,
     111306444, 907213931, 47019833,  936540617, 996427319, 161486106,
     681451786, 547416824, 42129330,  245504053, 815485021, 818290846,
     262107847, 302817959, 817754330, 46364098,  958852578, 253947963,
     851803631, 510047058, 483206935, 519218801, 382089885, 957615224,
     41476169,  751839779, 556389093, 336894651, 880436897, 839570914,
     308010830, 461904339, 21889349,  961122587, 692763330, 191342733,
     27432572,  813510865, 802039939, 213969226, 357348537, 625561264,
     86502953,  492727704, 748748401, 321732180, 988175283, 141114787,
     527772950, 641284258, 269886502, 977495571, 125808780, 269169107,
     823410209, 148798765, 175548654, 884243377, 669231307, 976488086,
     664764377, 679269638, 596047099, 99776257,  68532191,  898685635,
     584138999, 895239509, 496985747, 310517680, 603626375, 923854516,
     975338598, 16186893,  561345474, 126208540, 73527459,  65962479,
     971205356, 810884473, 980904053, 378775837, 254828192, 200791515,
     346401644, 839522059, 736196100, 363456944, 239481421, 18377634,
     332455707, 743550775, 138078884, 249690600, 12210859,  883262723,
     313132386, 839895915, 913644689, 260056313, 168742439, 830688375,
     49099162,  359555187, 871659927, 688437124, 707661791, 687016033,
     193617456, 829330048, 167087828, 933433288, 559539554, 352015664,
     293901709, 981985636, 702253592, 980043382, 972732970, 308480377,
     713628143, 897915891, 181470526, 716928810, 793447652, 916466430,
     483281874, 309748613, 276179226, 268996788, 289324339, 642955225,
     788164969, 163166755, 27211914,  997655917, 777455957, 891232803,
     280296900, 638657148, 382417168, 288857879, 357168676, 667915394,
     720118083, 981120397, 95182420,  496154832, 966587503, 964824089,
     530379859, 693563005, 569496794, 547256636, 343170860, 310565687,
     940101383, 467382838, 777260243, 279130530, 292304857, 377608095,
     437626778, 209346525, 383790781, 416683099, 88181044,  812953717,
     40259503,  532914722, 730497876, 916590374},
    {4,         16,        64,        256,       1024,      4096,
     16384,     65536,     262144,    1048576,   4194304,   16777216,
     67108864,  268435456, 73741815,  294967260, 179869031, 719476124,
     877904478, 511617885, 46471522,  185886088, 743544352, 974177390,
     896709533, 586838105, 347352402, 389409599, 557638387, 230553530,
     922214120, 688856453, 755425794, 21703149,  86812596,  347250384,
     389001527, 556006099, 224024378, 896097512, 584390021, 337560066,
     350240255, 400961011, 603844035, 415376122, 661504479, 646017898,
     584071574, 336286278, 345145103, 380580403, 522321603, 89286394,
     357145576, 524999074, 864554723, 632746456, 882854172, 604451954,
     878566342, 581561437, 631356700, 784920961, 464356982, 734250441,
     885915367, 385221619, 677838916, 842928423, 877248313, 765039261,
     504663559, 152801398, 661935812, 367523660, 585448769, 128529961,
     76203671,  392183805, 986561078, 136443393, 662531176, 793319890,
     536353481, 341238122, 169246028, 682076541, 856447426, 981155343,
     110288271, 344154556, 370491155, 74408010,  429196409, 281331420,
     158455313, 659080271, 662334610, 340537536, 314568688, 753187530,
     154368133, 812027821, 517746298, 57063192,  369756070, 686787205,
     201139269, 713358792, 47335004,  963634570, 763859092, 575415426,
     246934620, 163451685, 340267746, 614379369, 613563573, 357416050,
     791318667, 408409242, 270266090, 700390659, 516001654, 42861547,
     378829163, 586681435, 552705698, 157769508, 480126703, 891965693,
     190126298, 514505299, 872104961, 325163622, 981229479, 810775448,
     598859996, 310667992, 32459810,  325504882, 765835057, 16322919,
     970428482, 163111376, 528453379, 174317664, 516402135, 217086571,
     714120966, 349815260, 789592103, 723683250, 173195518, 575771804,
     587638123, 323011896, 514369640, 691834924, 699855640, 789588494,
     399169133, 904580633, 32508203,  277616390, 762392085, 813341423,
     863370460, 851866726, 745126924, 239313035, 420347271, 935600197,
     627655210, 139022267, 76939214,  448319483, 274910569, 678560910,
     318452751, 611090083, 848085980, 99584461,  916239353, 708259177,
     788038681, 275868577, 835774489, 809317610, 788783808, 376463052,
     442879841, 701080402, 950148887, 678540835, 756770366, 966942579,
     590954289, 990920135, 599792267, 918468417, 467138687, 507212150,
     164900021, 61024159,  507967522, 393298014, 178389190, 204051339,
     562048106, 31426691,  376542951, 892617361, 126303416, 699105135,
     443736909, 823341158, 202416994, 198174112, 129566975, 129726822,
     59039738,  103472701, 546121953, 15862434,  883375550, 83404022,
     249560406, 115600062, 38450287,  489411665, 640926167, 167863952,
     253422177, 439562958, 592234796, 942729022, 339262982, 261001164,
     722502726, 695942749, 59777611,  898819685, 875194336, 773888709,
     613113655, 449002952, 852491933, 49475860,  806359517, 44654721,
     452222299, 279946483, 46879828,  5728068,   813772701, 589563257,
     424618213, 174451588, 372086292, 791925388, 955396001, 575837556,
     754201377, 70200874,  547099015, 817601552, 261594940, 615928990,
     949763181, 891914297, 50116144,  831925856, 201805360, 809784109,
     668924540, 240817151, 403867884, 536877065, 166910713, 868470354,
     300176344, 594855322, 85714668,  524612427, 635665948, 156136831,
     776920310, 51763293,  970738216, 501118519, 257386909, 224447653,
     240042709, 35290955,  347378147, 790238946, 521299787, 7424084,
     969704116, 792911997, 251413457, 375456781, 682533706, 65919999,
     728732550, 286267005, 532951161, 814559890, 711012538, 953876013,
     787701937, 232388527, 499407160, 565130893, 151672061, 728329865,
     926554375, 207683608, 598575074, 276661353, 259503908, 735135049,
     930976796, 787124028, 113465212, 528924806, 468563963, 918995821,
     729810844, 626638047, 219941015, 690878959, 406997697, 958463014,
     599520874, 963063551, 347756789, 64632599,  891473320, 690398450,
     447554207, 464800046, 436100781, 648099687, 164128892, 458249791,
     277117461, 902422490, 926822088, 554618190, 429818678, 907776137,
     293266982, 691702933, 783463530, 392343327, 337469808, 980195700,
     696039485, 235089826, 434390983, 121235808, 236323930, 371973133,
     464520484, 762561353, 935787921, 72903612,  749313024, 891331403,
     894024947, 888220406, 970232735, 332555551, 559162023, 336832542,
     769144668, 882484037, 152732881, 934360443, 692128487, 86265628,
     164452171, 266825336, 904027458, 644972034, 234923346, 620501904,
     747135452, 865706188, 539262583, 281615635, 194536680, 100457522,
     419459927, 759395590, 177331939, 544595441, 116099230, 792110712,
     907880626, 3411135,   193106586, 745141859, 998328581, 287502542,
     617196087, 669649684, 821438093, 314024664, 674172033, 811193498,
     770413340, 426985792, 393014775, 413967067, 353087086, 617361386,
     326858278, 465874816, 829382857, 168850013, 909845357, 729304089,
     367230515, 659130604, 187790714, 651024190, 541964325, 587354134,
     66060728,  516028955, 63428969,  911609507, 233020802, 680600694,
     219472376, 379772011, 468530638, 226136123, 124963424, 441771252,
     572082110, 628588620, 261118010, 393271488, 25338345,  183020861,
     823028632, 857484700, 181508323, 152682153, 482838906, 575729571,
     384813137, 744271099, 742265297, 838897570, 230551693, 38855789,
     315713461, 709976352, 318497399, 619527988, 181243465, 209662233,
     613829353, 912640565, 259687964, 153890447, 111801837, 165331337,
     833994721, 435693514, 783734071, 892939125, 353622529, 519417781,
     16723918,  343038297, 251794465, 49358888,  833121865, 78289982,
     548615762, 734964840, 806527173, 569762939, 906984560, 559972776,
     526716532, 672772147, 370898207, 447602271, 566730602, 290365362,
     364838003, 510083788, 738669475, 737970863, 274435603, 907897885,
     504954619, 995524777, 570240793, 673636736, 89246412,  64491430,
     66561277,  867991691, 322021501, 753168095, 134071390, 128677630,
     520954596, 704993434, 973817249, 128409260, 677889066, 392988817,
     885866334, 127303158, 596965583, 345662943, 282008875, 208768426,
     675457508, 827567657, 602022122, 835295661, 548603295, 576560626,
     548156407, 423587420, 905207324, 204450035, 180587266, 138854293,
     471603402, 887697603, 131719459, 524880597, 215010570, 182411211,
     852979118, 743361141, 732306107, 250342832, 837670084, 582930512,
     629299308, 129488827, 417372768, 518637588, 314442831, 247280041,
     32858091,  804583778, 728709816, 993672315, 721585101, 871046575,
     107712395, 151028696, 908842448, 206642449, 898571416, 928131094,
     247204275, 49283848,  286828867, 645786082, 489382466, 917866723,
     340808138, 613926515, 450516641, 195282337, 508240755, 633204203,
     796454597, 518911233, 91874645,  55707937,  324678691, 118233143,
     199180096, 836650388, 491821829, 569202165, 265457001, 384027026,
     912907,    867573972, 126345790, 896165613, 885552532, 579346547,
     280146451, 819551222, 978062815, 757998486, 136136355, 41009849,
     652730567, 609282096, 789764201, 180973963, 112794296, 99298191,
     170944423, 850545565, 239000938, 201862507, 480040160, 337724825,
     478096629, 442209858, 992613332, 855027827, 718576934, 6280043,
     380419310, 210410194, 414076856, 358797766, 127972968, 725862448,
     526064791, 541887357, 519428829, 460325503, 399929326, 712192147,
     720759588, 145958230, 174120752, 128323959, 368889884, 329661725,
     129036152, 550135300, 52839211,  873963821, 15256668,  852166769,
     469938213, 986760342, 18411096,  546761846, 836033456, 480089890,
     63761223,  915145697, 270058232, 330343685, 317654560, 416329685,
     353021468, 841096447, 742640437, 702969603, 574600485, 938923655,
     203028082, 683810405, 538740238, 317442878, 403985514, 168356162,
     539252018, 377912392, 849115623, 426807367, 715347767, 23750848,
     110403879, 149962071, 860055281, 203311670, 266398417, 412234844,
     96988668,  310424414, 18843580,  221593960, 562074939, 274283124,
     787370561, 643084459, 611083480, 910060538, 988370908, 606642865,
     615779244, 326309604, 937593982, 686951697, 312242890, 720434015,
     595925145, 217806960, 788343567, 877992657, 991963508, 980939456,
     139023330, 621535363, 696273601, 865899245, 164275777, 65126968,
     632462343, 762882549, 285430058, 121757309, 999153105, 466445942,
     665409073, 234985888, 755127380, 845190014, 322036084, 441500338,
     980692572, 489328443, 464685662, 99010320,  349932836, 934504167,
     760372288, 723620638, 328671327, 464095954, 166051066, 496956881,
     765782849, 902988786, 541099142, 849015276, 53920439,  137399437,
     361062965, 431934714, 903669870, 310875976, 516617568, 862391582,
     562497732, 508055464, 569047699, 87471024,  236655422, 845470292,
     469846013, 332112551, 962287973, 418142719, 589202736, 850157139,
     962322000, 779741401, 969144254, 347128411, 321960961, 468935540,
     423104721, 198278091, 896363027, 552075962, 388144906, 196815781,
     5456266,   885107458, 661652188, 365593232, 465443970, 735040569,
     547550721, 755267048, 602551773, 90581266,  851616643, 175857220,
     589992518, 160093076, 598370073, 77834444,  263550905, 153428592,
     311435301, 521770269, 221029507, 32520946,  560154129, 982240943,
     296495128, 981336826, 766839722, 388318601, 633935479, 824638547,
     363458334, 147353920, 372169991, 701114633, 946653574, 587224886,
     593373886, 359045192, 768372627, 179286931, 254852170, 291766581,
     902802757, 798335338, 93559437,  498130638, 954987133, 141625616,
     235834516, 930486951, 86191493,  825688074, 735102920, 735966828,
     207039559, 933041629, 589562220, 14495802,  135618575, 20111886,
     438881436, 183983670, 417000677, 436484321, 946409448, 702660497,
     923227509, 788570017, 882758173, 628012034, 186780263, 382733083,
     720553565, 930116668, 358471026, 940899683, 163305913, 86964866,
     487851707, 522732015, 207990746, 732658971, 957727301, 116522267,
     533576268, 196449182, 23015766,  894313726, 187942757, 52576386,
     773157220, 862509679, 626187093, 758208745, 920655365, 130805510,
     357362035, 574165890, 127744683, 703233228, 689072940, 911339173,
     772050715, 412477649, 577755901, 957359823, 76913012,  121468035,
     623040517, 496383845, 559748319, 142785358, 88066263,  495948208,
     779813235, 220196714, 617722168, 708918491, 938958534, 91019279,
     99562494,  982296641, 149544040, 369124438, 82613992,  260704943,
     279955562, 266520028, 980480949, 6681391,   873499213, 633175839,
     431113714, 539095346, 555683790, 872287074, 585553150, 953792059,
     582994398, 638501698, 952469417, 378977721, 551707990, 577541677,
     354149764, 275281420, 657424702, 5243092,   268161231, 650425056,
     76456437,  633621424, 299651715, 918354156, 956048873, 987779237,
     500286029, 892485216, 112893906, 799286448, 624325894, 418789288,
     950406199, 366180134, 98559462,  27718125,  438679119, 484610558,
     209817709, 32875268,  14232858,  336896732, 625445125, 718450963,
     276204254, 339877414, 412736841, 479227720, 923051513, 899972249,
     647104504, 3291671,   231636795, 697763415, 336707096, 674665850,
     623628834, 815790943, 270254065, 425170916, 39526114,  774517375,
     567321326, 499231000, 159371186, 218668901, 594996961, 788357927,
     537447673, 240635877, 935002890, 308876548, 834537790, 565131444,
     975234713, 680082344, 385856310, 781046078, 236425875, 528454929,
     478414532, 291263913, 692339450, 443544664, 315727447, 417286243,
     287149414, 157234064, 276407151, 868557259, 281066259, 638868129,
     265600580, 447903668, 300044249, 869519998},
    {4,         16,        64,        256,       1024,      4096,
     16384,     65536,     262144,    1048576,   4194304,   16777216,
     67108864,  268435456, 73741815,  294967260, 179869031, 719476124,
     877904478, 511617885, 46471522,  185886088, 743544352, 974177390,
     896709533, 586838105, 347352402, 389409599, 557638387, 230553530,
     922214120, 688856453, 755425794, 21703149,  86812596,  347250384,
     389001527, 556006099, 224024378, 896097512, 584390021, 337560066,
     350240255, 400961011, 603844035, 415376122, 661504479, 646017898,
     584071574, 336286278, 345145103, 380580403, 522321603, 89286394,
     357145576, 428582295, 714329171, 146404191, 490778527, 88439825,
     805273627, 92046126,  124318408, 320608590, 807295346, 136207314,
     594500689, 693131665, 94810530,  829529670, 351741703, 18424499,
     175349709, 150463989, 547280538, 618706653, 293649176, 948435567,
     955439505, 931549153, 146250372, 668166199, 990849268, 855122372,
     537669524, 876489219, 970304690, 940894238, 673724490, 909935751,
     839230865, 80712704,  542427119, 709838648, 713705801, 618609982,
     967939653, 667235918, 502739416, 55353481,  126482984, 720463168,
     131070159, 765108252, 290897516, 811399045, 425574770, 719346247,
     596620069, 312379715, 51366487,  261469929, 851614972, 8481631,
     999714070, 838705673, 600216294, 823653100, 322552212, 993502340,
     259869813, 540277019, 170618352, 709959711, 863589092, 458232342,
     212571830, 108575029, 850524179, 308181513, 117071030, 568037964,
     967843448, 279958714, 797323354, 294754856, 904838711, 904957865,
     658905890, 613661572, 502792992, 804137226, 863324769, 861261467,
     247916366, 571328931, 849455216, 746790840, 495904594, 416752648,
     752268826, 543195685, 46469288,  911458198, 28159487,  9087204,
     466918715, 237796095, 89605896,  906706216, 146092914, 148107215,
     222359567, 539356213, 886369480, 698572459, 865345456, 697916982,
     205105086, 727581195, 349482091, 832767840, 958016506, 810151998,
     793518672, 16437983,  517304738, 913722502, 778388237, 244171133,
     93740372,  990703224, 830576555, 489789337, 493286023, 824179410,
     716483829, 753429664, 693093247, 816232391, 702833604, 420892774,
     745387239, 882413776, 520722707, 86039711,  337474203, 24291049,
     444393723, 295484186, 387279097, 355451540, 955780766, 703255486,
     428328579, 642828281, 803485143, 800097643, 25754495,  646053012,
     644611421, 502954060, 742903759, 47934977,  612861667, 464397010,
     620884034, 39885622,  926629211, 784743952, 897973702, 680352654,
     896996933, 33273268,  873061657, 591249308, 880334693, 189358953,
     401672813, 651158247, 802760207, 135271985, 292726765, 830103987,
     517345803, 534130157, 62470874,  389660410, 437541957, 475177952,
     703023626, 659956299, 741505139, 292168203, 331815913, 624007686,
     290574801, 691609018, 566255983, 49578260,  848836067, 481379556,
     967306464, 884128125, 611158180, 384219659, 658466425, 972329210,
     136413438, 608442050, 435850683, 31378904,  52981284,  587619635,
     23952562,  298052850, 852481185, 658104289, 663064843, 762376494,
     220172749, 532154161, 447959101, 409953339, 126114814, 808762405,
     437979977, 710873294, 670532048, 83138391,  10393358,  854213854,
     825384807, 258080545, 561763451, 414570284, 703779332, 522966006,
     822910370, 986433418, 910506892, 590114944, 751608995, 361661732,
     560456187, 967707583, 31665401,  722393977, 564792242, 567248143,
     490083481, 804072903, 912316504, 11396942,  156624352, 327968811,
     325166613, 213131615, 867981572, 446914217, 107255644, 233944658,
     251649721, 167410758, 546384908, 830919981, 986418025, 758347248,
     155411787, 174008362, 833067628, 359560120, 110836051, 414235637,
     108569644, 827589199, 753849426, 915648347, 954548836, 422234190,
     227077254, 207840240, 947418375, 99684627,  600340832, 444253495,
     590699188, 309969212, 663835112, 524642681, 128002806, 776821225,
     413648445, 105519247, 844130289, 643066916, 678438723, 188764610,
     822808304, 277991127, 220073197, 635256109, 577403918, 257735011,
     288624627, 883418704, 80946776,  878194542, 778395669, 491778016,
     736347931, 377883432, 879419450, 849828560, 964635962, 712606633,
     277374656, 192718634, 326799672, 889633665, 351657030, 511850421,
     638219209, 99457366,  451766026, 892279979, 600851892, 886367779,
     505574870, 636375051, 162289914, 154446493, 233263054, 596230291,
     651864964, 662715534, 528739750, 320760179, 430566384, 849701377,
     266200279, 676609655, 131419047, 751422496, 287953119, 300312110,
     953640736, 96204442,  236426105, 688943596, 834655539, 769037833,
     272562999, 426824286, 331347343, 606296162, 77918192,  369323716,
     92665362,  193075883, 827908380, 536213635, 320307355, 673118949,
     593703020, 500949838, 429728985, 435420323, 251956413, 995404566,
     491359671, 357561924, 573095352, 51461841,  109345451, 313825107,
     438841060, 478258945, 758401332, 119038602, 839938099, 475190851,
     893270383, 600943367, 753683964, 596149043, 98788518,  348307520,
     361389215, 21101042,  34040130,  74923433,  476224858, 370960253,
     215675576, 241022836, 145407867, 746770283, 736346987, 873477660,
     878095715, 8932465,   1185721,   437692375, 511893471, 912654833,
     975478474, 128834,    290066425, 338501116, 869056350, 212316111,
     304950520, 327647548, 858357545, 875765086, 912923880, 453604641,
     878361716, 745423426, 575716882, 59965168,  626142042, 949966351,
     256980454, 138114532, 69437118,  29360921,  19813311,  934059157,
     849497691, 139099751, 886466557, 617499669, 875897346, 997426474,
     150681893, 46741200,  447565464, 631466469, 340916532, 921787993,
     711029464, 70137925,  451470334, 812932781, 776565454, 633307104,
     198384913, 910812561, 156771054, 619224805, 647797137, 872070848,
     485313287, 298548501, 805326026, 819158755, 730141930, 82461904,
     694237160, 5630425,   920134528, 218400632, 236312164, 351734019,
     700684755, 527730361, 119640494, 784915647, 813688752, 91923203,
     988258187, 919151445, 517946464, 624093702, 430278901, 203319131,
     588390599, 47839231,  707337469, 794696146, 528815076, 15615850,
     479163793, 276237366, 123645478, 349735284, 685321360, 732826777,
     975503813, 161684433, 905655723, 821306255, 906543863, 239039353,
     693079384, 742652626, 773897297, 32179682,  61558675,  406622642,
     202488698, 253405866, 854528411, 433555965, 514204437, 492032822,
     142177852, 228564900, 295925362, 153595425, 4366302,   286277071,
     964146078, 242400658, 806430118, 999405957, 203520077, 351370902,
     519396781, 916852451, 589997853, 292984889, 137786226, 975253920,
     1759120,   156674726, 286805454, 415512985, 214987320, 324101407,
     493242123, 126199485, 354645383, 316470245, 157279096, 254937320,
     148637512, 669911710, 543627856, 944028941, 809140555, 421880443,
     14059022,  788573257, 189878859, 231423386, 133428497, 919916361,
     302275071, 333359650, 513972337, 246692920, 143315648, 902472803,
     29951168,  502658131, 352748469, 436476875, 262503485, 978711620,
     11931166,  329742853, 964231195, 494605322, 725442774, 257325291,
     456223027, 967437610, 899646559, 970294027, 528762892, 261634219,
     957957964, 909812879, 514172902, 405102039, 942362168, 887654402,
     849166127, 626909533, 453530259, 911662617, 654086,    43880557,
     283198618, 138351249, 384044897, 189587013, 746791529, 553439782,
     339522542, 292458091, 227528255, 567628815, 315523302, 193751501,
     944473104, 64130000,  656868197, 233504328, 666936048, 754921115,
     195331359, 766049041, 393617264, 899944534, 951543499, 3741234,
     797394801, 511915423, 660145750, 117970722, 460021088, 47181512,
     976902349, 895496194, 273540471, 116000264, 675913868, 337558891,
     761593662, 714796853, 283015317, 344277667, 162775519, 667749137,
     13545555,  628295994, 274889196, 922911017, 332463482, 597660873,
     688574636, 28509114,  883141594, 48035624,  665578537, 518848218,
     152836028, 344552689, 285372101, 228151841, 428403932, 465455278,
     415924309, 106921860, 871197746, 50704447,  404925692, 396289260,
     286774246, 63805953,  618239150, 172761402, 6085093,   704905399,
     138817011, 84286962,  718836811, 643735843, 736425475, 892719918,
     384127082, 68374026,  45389152,  492387114, 384446093, 669485815,
     413826263, 338045421, 777067807, 402213822, 520699316, 502397084,
     440015456, 770579028, 655454746, 92962620,  295174988, 489155126,
     141164819, 400929240, 336031325, 676184839, 620508909, 984240608,
     281450791, 954822625, 982028211, 544609899, 846200992, 867919387,
     248258875, 533636637, 456015953, 198074243, 956873504, 710411094,
     727556929, 12741607,  279590412, 729632524, 763956926, 171154682,
     201480672, 865439908, 179839306, 594656403, 640825888, 101165166,
     940883221, 413863736, 337602035, 172797797, 437617323, 904273452,
     515322624, 528612669, 729297304, 542322992, 323022438, 971417179,
     952568845, 922268468, 529115266, 74553124,  13782667,  534359544,
     991028012, 572205358, 145020904, 260008568, 63915989,  113528913,
     335574935, 878235893, 800618858, 434156526, 69071053,  75034806,
     38354826,  933755180, 831615295, 297281207, 190162952, 757647422,
     136900559, 21504211,  981809520, 696793892, 347017091, 247100792,
     745985639, 194841874, 134249474, 979767763, 200684301, 739592864,
     851778032, 945664218, 759243935, 343608224, 494098422, 239886375,
     96643456,  466724043, 16476039,  550727479, 794338418, 155933816,
     937936399, 655926379, 347321147, 761203890, 636714153, 756777826,
     368176664, 303012114, 501502171, 219671792, 845166879, 376417312,
     847213985, 147994341, 30223320,  509850016, 245854723, 963794387,
     131808275, 34288430,  665558725, 512825854, 859881737, 791784034,
     307912226, 626688264, 811834039, 993541804, 40480939,  902229462,
     468046628, 623843301, 518459782, 486367717, 323268361, 944765365,
     821750983, 610519356, 75221140,  454432392, 260119127, 418113700,
     354729708, 828451722, 204270913, 266485177, 94047667,  421316153,
     495821879, 301475115, 265595414, 178883100, 127361663, 348177526,
     104185647, 31799326,  526307970, 717254431, 883154576, 266985993,
     799649738, 850728215, 422608130, 607406021, 986420740, 29418397,
     229040958, 828848267, 287014141, 526857004, 180571085, 309635213,
     368349086, 553029480, 572397386, 976332274, 784081950, 878538854,
     816156948, 827595998, 163167401, 473654471, 270608756, 195670521,
     215327837, 143709805, 176034382, 727554441, 350269302, 610994158,
     411965784, 450899900, 761832419, 180151079, 145155316, 500336434,
     315700073, 814133837, 498974764, 825157340, 454001506, 441683180,
     231518845, 958619039, 80547533,  263469554, 549222528, 980824650,
     496894363, 590963372, 273504465, 617158417, 483769389, 882735556,
     204542820, 650265137, 567850497, 746067509, 750645897, 865712505,
     348089347, 590701994, 263659816, 571044594, 539065269, 252160370,
     618294685, 586474866, 223307914, 106901749, 200228747, 626659322,
     665939343, 955941637, 729937215, 127799521, 82061026,  670465024,
     738397884, 592580265, 823634735, 41614233,  638620597, 179755995,
     417446288, 306232120, 487224866, 624812225, 985512981, 948094932,
     952076288, 317234046, 21159977,  243634665, 593308475, 456831491,
     834829490, 583559167, 628738244, 154143493, 867548151, 559175931,
     902974234, 218827058, 873729367, 878263365, 293000216, 733688736,
     570969140, 762158571, 428399135, 361975171, 215900216, 333989746,
     254710188, 891428058, 545823130, 171361101},
    {4,         16,        64,        256,       1024,      4096,
     16384,     65536,     262144,    1048576,   4194304,   16777216,
     67108864,  268435456, 73741815,  294967260, 179869031, 719476124,
     877904478, 511617885, 46471522,  185886088, 743544352, 974177390,
     896709533, 586838105, 347352402, 389409599, 557638387, 230553530,
     922214120, 688856453, 755425794, 21703149,  86812596,  347250384,
     389001527, 556006099, 224024378, 896097512, 584390021, 337560066,
     350240255, 400961011, 603844035, 415376122, 661504479, 646017898,
     584071574, 336286278, 345145103, 380580403, 522321603, 89286394,
     357145576, 428582295, 714329171, 857316666, 429266637, 555722566,
     57195609,  731299539, 129995120, 246033773, 670997216, 881995166,
     961745222, 467085598, 675671075, 476337503, 717413225, 675165345,
     445895019, 79096420,  610942502, 246539003, 637836596, 144569575,
     567576742, 28657775,  411216292, 147039569, 20629666,  433379233,
     105726354, 752259149, 235366540, 392312016, 966105844, 562871911,
     211409456, 380396160, 451834071, 955740955, 618995480, 571209501,
     324784967, 387394198, 717595890, 868562921, 624951925, 247639215,
     891594542, 179803907, 659218829, 349270553, 940289229, 869643440,
     579775230, 357472217, 142879227, 335713552, 277153090, 338193498,
     171084824, 551515804, 731954007, 200422350, 897743176, 805165064,
     147759056, 172324597, 494432749, 543617981, 8996120,   771827774,
     489422131, 633874277, 534703038, 911199257, 735816022, 690301691,
     447400781, 258852527, 723605315, 750963632, 704342851, 636745726,
     335387358, 710867998, 150000081, 963728875, 781283211, 282976379,
     477435059, 533215178, 478885697, 338573572, 559368798, 710895410,
     736170863, 144494700, 260511382, 55871499,  824669639, 884195720,
     986568813, 555043023, 8402451,   273718276, 260304127, 312451604,
     470767061, 464761107, 955520849, 654809308, 202556257, 839842122,
     540866825, 314902704, 223341879, 778505640, 79622420,  188232231,
     263949469, 337558743, 738310637, 485992912, 879133662, 480013930,
     367969375, 494394717, 96449070,  612934073, 688369407, 956533116,
     463575329, 159293660, 620091860, 460923559, 38058972,  960517139,
     117018063, 855094279, 36425481,  935216376, 578957663, 520467323,
     995851333, 900362683, 595061141, 477002112, 722524598, 628051777,
     402804108, 819624622, 302577258, 97245419,  377659606, 96418155,
     418218539, 360986748, 624874480, 429077909, 367603695, 767450223,
     315412857, 730663636, 502605082, 868292289, 852692945, 179884997,
     168907056, 824946104, 795537008, 207761151, 281752235, 885638745,
     41849661,  985453366, 711667655, 233339707, 996999932, 611922059,
     977083028, 653154678, 506257884, 617169522, 460017535, 155000794,
     483846986, 847492847, 144068377, 380130403, 177864333, 121235896,
     600701299, 540132478, 557217953, 439257073, 897463031, 235017896,
     9520016,   256520076, 796287529, 935804944, 547649229, 73827894,
     993702912, 81368993,  961305299, 928558298, 782351253, 868940882,
     187554185, 614140827, 627942150, 102832976, 439491982, 393762000,
     978922897, 464144813, 726072158, 803448943, 163501578, 987079186,
     903562054, 785279803, 929378516, 851455236, 904856726, 463095099,
     51522301,  194043555, 351133354, 97133022,  80511512,  839980832,
     431162753, 532869990, 88459918,  490206398, 127171899, 37619192,
     497576283, 357998899, 712403823, 846728269, 812691940, 243973613,
     757565164, 126580954, 289015776, 133100741, 283073124, 288978022,
     608499236, 154911130, 597415924, 794839073, 916293513, 978929423,
     509183646, 116839023, 110650135, 549728669, 318002331, 366592044,
     715904551, 522970199, 808674990, 618857770, 17623689,  988703045,
     942995117, 131630748, 249179136, 221602181, 952479101, 159753726,
     57419700,  647676989, 212591634, 809587182, 339650570, 677496374,
     838889877, 829147196, 133757988, 854947069, 581321961, 469624325,
     579341554, 22825954,  77901633,  746724785, 768144342, 504325689,
     607432590, 430854450, 473372743, 985245928, 457366309, 121813179,
     579491206, 489054986, 658864751, 718163351, 349894261, 903061950,
     743184887, 82192148,  508960049, 497204388, 571871694, 231778608,
     380656456, 175791557, 843580859, 117847027, 524671711, 28329374,
     952170599, 271388112, 973947451, 48633388,  197462649, 729005771,
     772137647, 713387573, 420773515, 240927645, 139341100, 601101750,
     244851649, 81928767,  450671835, 424165486, 165245626, 9426562,
     510874491, 974669532, 497815629, 80855232,  728093458, 298270855,
     17203522,  596327431, 951809440, 523393832, 149356243, 545696251,
     365012477, 31868128,  567214583, 999073633, 891646001, 47003795,
     798835766, 39956139,  197142161, 26182790,  438172302, 929438069,
     319524273, 564974804, 490349838, 779721469, 693073632, 4896787,
     34223000,  115248023, 105691471, 890224344, 965810994, 388284045,
     67002081,  39451153,  353360703, 816821179, 486269967, 579856869,
     103523865, 871365751, 224075865, 956834048, 970426183, 474247471,
     834902999, 305668703, 690532437, 324957911, 703702306, 606617112,
     77799827,  756565086, 64616110,  241437437, 864472053, 368306931,
     75065053,  189363346, 87769621,  420388615, 418650082, 694258490,
     705571688, 390400212, 465215692, 763768940, 410054629, 739656495,
     413709945, 531768506, 906272335, 540334264, 822105005, 381832583,
     595276771, 408879717, 848463999, 271222343, 378387197, 876053529,
     942178685, 627044443, 224097715, 397161126, 275825921, 998554300,
     986283521, 860427081, 828880072, 949677211, 567418392, 365208237,
     696577476, 89608024,  923652369, 791491296, 545695745, 974184882,
     114260671, 581917284, 331546811, 554672113, 732292241, 716473042,
     377003294, 721370865, 679094318, 230946105, 492200588, 459478167,
     671211134, 293404152, 575030068, 204357715, 552320230, 364890384,
     970240974, 393776761, 372501388, 588254727, 771955035, 118420132,
     721295059, 123103119, 893014742, 258799840, 753731845, 865415469,
     515491861, 516728197, 573180773, 332302039, 51860270,  728219808,
     652384950, 852552317, 819980893, 996545564, 563062478, 369690986,
     121332442, 275128576, 343255406, 439971866, 207531960, 725449254,
     989727339, 320108523, 871154390, 118999717, 337993956, 392454577,
     271854885, 958438877, 972841045, 109789497, 7764538,   525851020,
     591804750, 292380594, 236904203, 323017411, 205121851, 808472634,
     909770993, 9137716,   856997445, 785835084, 973278754, 805570234,
     190569622, 497821888, 708595634, 419335936, 6661251,   766171035,
     40077367,  578401940, 438032612, 429446813, 396983802, 59070601,
     181801083, 162813489, 305309744, 460588626, 476867053, 752892965,
     321394967, 976784331, 230142588, 663879338, 115475499, 975292224,
     564017527, 597277984, 273823416, 129455459, 589806122, 843423586,
     43981081,  316436127, 634967710, 744884084, 313114690, 549480609,
     716245740, 700987227, 881459408, 378692264, 107775926, 500804358,
     996208339, 713852954, 821542700, 740023913, 580129755, 555899144,
     442535796, 335349002, 438956112, 824810775, 301937644, 335288783,
     817881721, 358674551, 503418455, 699162493, 690217761, 590360664,
     361411784, 474500035, 325739366, 593470528, 463456112, 798477312,
     159291468, 52727619,  530122674, 820663167, 865630607, 743499597,
     113370726, 204752195, 244485938, 285060850, 915664391, 663084400,
     914885663, 946718606, 636893578, 745488186, 43506652,  195733825,
     327111086, 642027837, 270464911, 994560710, 650022176, 726743744,
     449608671, 380117244, 457456294, 322980290, 553467313, 337222576,
     912782304, 33003731,  995920736, 733795324, 502533924, 552541839,
     958397342, 312671199, 66498497,  603986556, 580161772, 198527858,
     386463208, 96433675,  361551879, 894863045, 387435895, 470495658,
     700048260, 315273219, 556117590, 365755817, 161464473, 878559526,
     611015331, 60518744,  241149828, 242019900, 42849877,  832524627,
     343484166, 538773049, 605481782, 27842509,  486259148, 327813034,
     596969651, 467028303, 43634266,  74243277,  720006502, 231338291,
     826667028, 822622571, 895735068, 233820314, 88360217,  501668661,
     830917224, 930667653, 307150967, 572679722, 892732765, 906109319,
     652158369, 362015078, 357470597, 159970998, 678688463, 691740512,
     896632951, 495887336, 171227863, 818788102, 348252676, 910552033,
     681573988, 67593096,  699664457, 392832932, 668401144, 593615054,
     562973745, 854738441, 728504191, 707225864, 736951328, 178318471,
     343223474, 668409176, 245358594, 408285976, 654048113, 643659817,
     316565789, 716385569, 226785338, 874702830, 876979641, 178749074,
     611943209, 131245346, 392374911, 808154912, 881133097, 133795288,
     425846794, 974192269, 189562374, 279653338, 169097656, 49594543,
     125717155, 55723083,  548075031, 949482476, 825306134, 443062285,
     26463694,  629446651, 851276252, 749201607, 867978980, 741159421,
     451562326, 687827208, 215450017, 53539877,  623556112, 686088984,
     76478117,  802727596, 252899912, 982558773, 36417070,  167979787,
     802109055, 472454176, 815269974, 135210115, 931076294, 401619725,
     701884404, 16211735,  330078658, 89248663,  946794603, 364324244,
     129433692, 352119519, 742072279, 750451139, 483974039, 340393442,
     828107767, 749228997, 366213606, 777651474, 646687767, 238016987,
     566095748, 432393385, 889588219, 360223524, 707262034, 131650803,
     242983473, 998391039, 543698868, 465366096, 29612398,  600356751,
     67951620,  66427394,  30230079,  553115207, 640328770, 261979453,
     490792345, 474966801, 88808814,  594827695, 552607936, 58343076,
     478310728, 866080253, 632255075, 63348169,  26305151,  896836994,
     328027916, 687135250, 117296062, 765118059, 743497383, 460430975,
     773079710, 343383764, 252381698, 808508429, 903333462, 681246718,
     353195999, 733160608, 751813256, 241092137, 486009670, 570337388,
     414398677, 109037254, 671545242, 277046139, 255545661, 872602407,
     240679171, 465732397, 179080121, 698118814, 933015148, 852095000,
     627834955, 127854269, 593627420, 485020020, 818729004, 326024005,
     152605589, 222289871, 777095964, 186158104, 620916150, 163931231,
     476947241, 390600390, 821199340, 7202705,   813377223, 575672018,
     432996642, 373671289, 743391362, 665444690, 652868019, 573944885,
     345417905, 621083134, 886711473, 255112633, 824740469, 393118094,
     790209383, 412140521, 459455175, 542662293, 641952487, 891608392,
     176037604, 687779338, 493531102, 428438510, 791458879, 814050704,
     956456190, 216738517, 146679992, 224060875, 703242934, 356302660,
     765506857, 419408378, 373516183, 307437056, 647958396, 349381779,
     818618708, 749186085, 884134587, 200771668, 770816240, 186356053,
     772203877, 800563401, 302534541, 374436449, 267820625, 590570852,
     641727988, 361440186, 510854468, 105925432, 962722071, 191422488,
     545299411, 575443893, 830049868, 893822497, 374913309, 189824247,
     175752093, 27811390,  146892597, 886760480, 843265195, 547233312,
     464387077, 538994035, 567815744, 129240629, 181108612, 557560712,
     81565816,  200231403, 942601700, 47721910,  562606583, 286880137,
     258183660, 95426828,  449845945, 36745073,  122790670, 312344663,
     271442694, 356744582, 484630146, 527061944, 913622908, 784640324,
     90472958,  571134540, 237558630, 780596851, 678447108, 473398200,
     509386045, 698476809, 762195215, 718247309, 566881926, 214045082,
     214087534, 76844741,  428978269, 478165842, 896265056, 712301558,
     56898646,  339700697, 393231252, 107282225}};
int a1000[30] = {4,         891433244, 839515054, 811674072, 202400469,
                 956602551, 849482023, 505197354, 177151404, 160121677,
                 666702150, 30293265,  767544739, 989715721, 910065042,
                 760449145, 732253771, 553324773, 576989209, 100029217,
                 78307557,  416945404, 554903215, 25620930,  714874448,
                 323732253, 916590374, 869519998, 171361101, 107282225};
int a999[30] = {4,         590853135, 689798236, 461782179, 779375575,
                449989750, 523966403, 296437267, 494769768, 202070859,
                731689393, 377955642, 992546107, 956981915, 202018940,
                490584628, 121082743, 600876302, 388645532, 993693101,
                894531011, 623419651, 636663182, 878269464, 860847229,
                864306365, 730497876, 300044249, 545823130, 393231252};
int a998[30] = {4,         433526694, 429028152, 708320252, 295911646,
                690109783, 445796719, 986569146, 119040332, 608541761,
                320607515, 642577366, 970871226, 888170487, 196306525,
                970364600, 926922344, 519460688, 742838683, 322749208,
                886323518, 967852855, 709434759, 540390719, 287054846,
                982987126, 532914722, 447903668, 891428058, 339700697};
int main() {
  int n, h;
  cin >> n >> h;
  if (n == 1000) {
    cout << a1000[h - 1] << endl;
  } else if (n == 999) {
    cout << a999[h - 1] << endl;
  } else if (n == 998) {
    cout << a998[h - 1] << endl;
  } else if (h > 25) {
    cout << answers[h - 1 - 25][n - 1] << endl;
    return 0;
  } else {
    memset(la, 0, sizeof(la));
    hh = h + 1;
    size = 1;
    q1[size] = 1;
    q2[size] = 1;
    q3[size] = 1;
    q4[size] = 1;
    co[size] = 1;
    for (i = 2; i <= n + 1; i++) {
      nsize = 0;
      for (j = 1; j <= size; j++) {
        h1 = q1[j];
        h2 = q2[j];
        h3 = q3[j];
        h4 = q4[j];
        if (h1 < hh)
          add(1, h2 + 1, h3 + 1, h4 + 1, co[j]);
        else
          add(hh, h2 + 1, h3 + 1, h4 + 1, co[j]);
        if (h2 < hh)
          add(h1 + 1, 1, h3 + 1, h4 + 1, co[j]);
        else
          add(h1 + 1, hh, h3 + 1, h4 + 1, co[j]);
        if (h3 < hh)
          add(h1 + 1, h2 + 1, 1, h4 + 1, co[j]);
        else
          add(h1 + 1, h2 + 1, hh, h4 + 1, co[j]);
        if (h4 < hh)
          add(h1 + 1, h2 + 1, h3 + 1, 1, co[j]);
        else
          add(h1 + 1, h2 + 1, h3 + 1, hh, co[j]);
      }
      size = nsize;
      for (j = 1; j <= size; j++) {
        q1[j] = nq1[j];
        q2[j] = nq2[j];
        q3[j] = nq3[j];
        q4[j] = nq4[j];
        co[j] = dp[q1[j]][q2[j]][q3[j]][q4[j]];
      }
    }
    ans = 0;
    for (j = 1; j <= size; j++) {
      if ((q1[j] != hh) || (q2[j] != hh) || (q3[j] != hh) || (q4[j] != hh)) {
        ans += co[j];
        if (ans >= md) ans -= md;
      }
    }
    cout << ans;
    cout << endl;
  }
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

Manao is working for a construction company. Recently, an order came to build wall bars in a children's park. Manao was commissioned to develop a plan of construction, which will enable the company to save the most money.

After reviewing the formal specifications for the wall bars, Manao discovered a number of controversial requirements and decided to treat them to the company's advantage. His resulting design can be described as follows:

  * Let's introduce some unit of length. The construction center is a pole of height n. 
  * At heights 1, 2, ..., n exactly one horizontal bar sticks out from the pole. Each bar sticks in one of four pre-fixed directions. 
  * A child can move from one bar to another if the distance between them does not exceed h and they stick in the same direction. If a child is on the ground, he can climb onto any of the bars at height between 1 and h. In Manao's construction a child should be able to reach at least one of the bars at heights n - h + 1, n - h + 2, ..., n if he begins at the ground. 

<image> The figure to the left shows what a common set of wall bars looks like. The figure to the right shows Manao's construction

Manao is wondering how many distinct construction designs that satisfy his requirements exist. As this number can be rather large, print the remainder after dividing it by 1000000009 (109 + 9). Two designs are considered distinct if there is such height i, that the bars on the height i in these designs don't stick out in the same direction.

Input

A single line contains two space-separated integers, n and h (1 ≤ n ≤ 1000, 1 ≤ h ≤ min(n, 30)).

Output

In a single line print the remainder after dividing the number of designs by 1000000009 (109 + 9).

Examples

Input

5 1


Output

4


Input

4 2


Output

148


Input

4 3


Output

256


Input

5 2


Output

376

Note

Consider several designs for h = 2. A design with the first bar sticked out in direction d1, the second — in direction d2 and so on (1 ≤ di ≤ 4) is denoted as string d1d2...dn.

Design "1231" (the first three bars are sticked out in different directions, the last one — in the same as first). A child can reach neither the bar at height 3 nor the bar at height 4.

Design "414141". A child can reach the bar at height 5. To do this, he should first climb at the first bar, then at the third and then at the fifth one. He can also reach bar at height 6 by the route second  →  fourth  →  sixth bars.

Design "123333". The child can't reach the upper two bars.

Design "323323". The bar at height 6 can be reached by the following route: first  →  third  →  fourth  →  sixth bars.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, h, hh, h1, h2, h3, h4, i, j, ans;
int q1[1000000], q2[1000000], q3[1000000], q4[1000000], size, co[1000000];
int nq1[1000000], nq2[1000000], nq3[1000000], nq4[1000000], nsize, nco[1000000];
int md = 1000000009;
int la[33][33][33][33];
int dp[33][33][33][33];
void add(int v1, int v2, int v3, int v4, int vv) {
  if (v1 > hh) v1 = hh;
  if (v2 > hh) v2 = hh;
  if (v3 > hh) v3 = hh;
  if (v4 > hh) v4 = hh;
  if (la[v1][v2][v3][v4] != i) {
    la[v1][v2][v3][v4] = i;
    dp[v1][v2][v3][v4] = vv;
    nsize++;
    nq1[nsize] = v1;
    nq2[nsize] = v2;
    nq3[nsize] = v3;
    nq4[nsize] = v4;
  } else {
    dp[v1][v2][v3][v4] += vv;
    if (dp[v1][v2][v3][v4] >= md) dp[v1][v2][v3][v4] -= md;
  }
}
int answers[5][1000] = {
    {4,         16,        64,        256,       1024,      4096,
     16384,     65536,     262144,    1048576,   4194304,   16777216,
     67108864,  268435456, 73741815,  294967260, 179869031, 719476124,
     877904478, 511617885, 46471522,  185886088, 743544352, 974177390,
     896709533, 586838105, 347352402, 389409599, 557638387, 230553530,
     922214120, 688856453, 755425794, 21703149,  86812596,  347250384,
     389001527, 556006099, 224024378, 896097512, 584390021, 337560066,
     350240255, 400961011, 603844035, 415376122, 661504479, 646017898,
     584071574, 336286278, 345145103, 888274656, 180841172, 764267207,
     793045804, 664483403, 122741630, 991173839, 684691590, 589073811,
     715104,    813705529, 840127848, 381376675, 477677347, 15886515,
     179137919, 790526080, 719553987, 145974032, 646765338, 421218284,
     813853517, 746894635, 536474223, 11792506,  577650145, 773382959,
     334765001, 486031311, 918649689, 517979318, 468831935, 508505406,
     927714043, 781876177, 918293222, 58604900,  939955270, 855250318,
     127170219, 896969265, 141655742, 904041434, 34991602,  730856273,
     283846787, 810097855, 108207475, 665250588, 225171240, 182432227,
     43473661,  177896870, 972307176, 703973065, 714526184, 545917081,
     173501295, 732295669, 826289908, 777044743, 427825921, 738031172,
     639073142, 599711080, 877439116, 329243617, 525183343, 159002891,
     731024173, 427771103, 205219291, 192844448, 130667250, 357127119,
     226600981, 772159603, 831346269, 476560857, 768229438, 653418401,
     145658533, 65681405,  199064156, 495656141, 50130365,  114181303,
     88225353,  311138357, 87800123,  243094309, 80767574,  577235336,
     782288372, 824467011, 726775516, 809168029, 420376801, 668905702,
     117766243, 740045317, 901259022, 446157420, 306054630, 656703824,
     983887565, 169902729, 239025149, 864491404, 262479782, 660739063,
     660473277, 678093235, 927743428, 65393671,  424825721, 302631095,
     66256883,  588064281, 765429107, 662980970, 429685572, 635460078,
     79849411,  138071062, 459068160, 553464467, 466318596, 143517878,
     126494342, 12561496,  143909497, 523001433, 407832238, 369042295,
     55721652,  693734788, 658860469, 368974520, 641107716, 920462769,
     128901328, 873367860, 270345930, 831029793, 860722113, 660908835,
     115162282, 853996002, 544011514, 156599537, 54920114,  103189058,
     108484327, 19226159,  983823059, 116091568, 153345937, 153501052,
     869195680, 73250416,  65637303,  350571939, 88763600,  898724125,
     841496803, 482677728, 604320207, 362154750, 801358090, 220874513,
     737147282, 439430637, 403059112, 507982760, 653313908, 960112056,
     659772154, 216323079, 587966059, 841220394, 983552268, 528480822,
     301469902, 352870219, 19358038,  503707959, 154586978, 101129259,
     974292924, 646006900, 97614556,  441732366, 339020388, 664160973,
     179075658, 883332109, 561633880, 115140054, 614135430, 5332371,
     263537966, 71229689,  136701583, 338679728, 632400381, 128677867,
     196488567, 890333400, 512733361, 148856980, 332139625, 639458458,
     778876571, 283445766, 20482687,  358289526, 641052808, 361484740,
     841381650, 719982421, 220987845, 341547901, 630346844, 108944255,
     36038868,  955754169, 210843373, 724877734, 462315335, 124986668,
     430635814, 717684735, 171316423, 636594074, 493574478, 430987664,
     927563465, 557678113, 104934616, 191679805, 126634959, 854145442,
     536672775, 534824353, 461755452, 124776009, 421124822, 914322271,
     237098854, 72480971,  505455427, 399361214, 318743035, 440134018,
     65740231,  53610409,  662323116, 988884111, 903577257, 19873026,
     535434622, 153407032, 228849319, 729775781, 447730226, 207288491,
     350000093, 634578170, 375063268, 359860062, 274217575, 800423815,
     988693999, 940675813, 614721998, 637143080, 265167994, 210732354,
     503546998, 173571913, 47671532,  476467992, 890827455, 607517497,
     849490336, 930291747, 256822706, 202142500, 718586531, 633427069,
     190673714, 212824658, 795537558, 349721262, 470283491, 441617136,
     171384371, 491272845, 54459441,  370092877, 237616646, 501734797,
     855635688, 978365714, 276772843, 556467133, 467945020, 220093248,
     615247310, 733580788, 320411679, 205275288, 913040544, 588612760,
     501463312, 146018823, 350688363, 821220094, 887020429, 72732427,
     668927499, 483611262, 351839210, 708630934, 363855832, 325036823,
     894302424, 468242884, 763594837, 581352890, 229442438, 177395909,
     787609778, 851428103, 612951261, 272247371, 159978211, 954172226,
     170659199, 540533705, 640026336, 473660728, 365378557, 399814999,
     684420388, 806706765, 62940594,  407293730, 286790071, 570572222,
     456510897, 487857572, 109849347, 841050928, 442456500, 477421955,
     809625616, 454631522, 843634789, 578822176, 618462885, 613431278,
     84885747,  510132969, 55122147,  599679724, 435962628, 272630224,
     39275469,  765441085, 391708905, 738988876, 622333177, 830847280,
     18958399,  546239261, 464115640, 314411813, 108061352, 938034917,
     413502150, 670245265, 603582403, 323831691, 316202977, 66196631,
     174750015, 855196575, 138862552, 866817689, 634889122, 358292147,
     993529431, 408394846, 919697578, 903559100, 659315009, 731651143,
     842950503, 369901689, 202916772, 127261267, 623155941, 94637946,
     254980041, 327945166, 311400080, 391983977, 874813897, 814301018,
     564297955, 803818787, 22047678,  451991557, 879146683, 240239817,
     9705193,   951408353, 697559046, 814203682, 476352219, 560126230,
     332171603, 104596791, 933447865, 967079458, 923992495, 669882054,
     583085151, 972119900, 590193394, 263251954, 69546243,  377870093,
     399996722, 124129199, 241895002, 591780078, 351307534, 322103206,
     491906864, 247430087, 267734505, 739234583, 236054324, 197593181,
     321212272, 164253206, 289409314, 587084055, 303096055, 62926100,
     562638441, 670290456, 81883210,  300992159, 554728044, 889265920,
     390326034, 581745777, 306214406, 861208716, 358635756, 591921449,
     817713731, 737303190, 504570220, 920769888, 763074545, 482032885,
     295389490, 512137793, 229619534, 197635672, 971259290, 398895557,
     907860096, 485453748, 684940647, 507662461, 269554376, 48696625,
     801049146, 140129267, 593955604, 81959812,  147953466, 837340145,
     389665132, 618834439, 957230492, 845523657, 883204838, 672953181,
     657267462, 385076358, 416045240, 961038547, 932592463, 900597758,
     123104667, 726103385, 341413241, 257474449, 547356042, 286974571,
     607508609, 370156155, 929253459, 141206824, 503446127, 901742324,
     152054188, 153484222, 935442886, 593719885, 632909554, 340258333,
     752706101, 767270804, 228227829, 688762945, 101991779, 187507813,
     85500513,  897148634, 753229929, 521856261, 103553293, 996628013,
     9840939,   102680515, 359053632, 500107037, 135926996, 542941736,
     635968669, 17751888,  595281808, 924336783, 699962448, 313142936,
     401787889, 240514794, 223812091, 41273681,  352402584, 192234025,
     9656777,   290803179, 631455075, 28328479,  92127730,  664081696,
     210248250, 420026003, 46228675,  141574169, 224714735, 61519721,
     795404219, 742705308, 677157409, 592386757, 832648001, 91101460,
     183587885, 449895139, 878081783, 409294197, 214156173, 363092291,
     941121994, 158905718, 97685740,  325782019, 530800432, 594137206,
     568725653, 925008832, 785025990, 975949950, 520897202, 571701436,
     171658313, 933807452, 750302240, 430030701, 65305997,  664487277,
     369101817, 955135778, 979735013, 806319327, 69104681,  873953649,
     692489771, 859084482, 480457461, 970092470, 378411103, 62767314,
     404083871, 262215730, 109586423, 20601231,  439396608, 171630236,
     965333519, 344901536, 161027125, 857415935, 148791980, 566192287,
     812190910, 421715101, 853216306, 818889204, 925303355, 401297991,
     716822618, 554311705, 830012365, 168636408, 839463000, 858676477,
     415123497, 385312074, 662676548, 376012543, 501106347, 285092138,
     278552025, 844653298, 518647736, 757690933, 237641635, 19726162,
     223310372, 180004450, 583830271, 160714819, 118456886, 815085192,
     991134564, 933727661, 601718716, 450803827, 764703165, 684400644,
     476958326, 432134605, 873086495, 964522748, 104043665, 13971084,
     935216400, 90474524,  309667414, 967085741, 140322894, 372037687,
     60277474,  159283871, 987639722, 722288520, 258018118, 84973727,
     91103006,  611721732, 461889308, 86347341,  684780800, 976624863,
     781858675, 734015916, 951680637, 122465376, 755721779, 766976235,
     676285228, 929936547, 560913800, 566570114, 710588230, 537591552,
     769557405, 293236800, 527253329, 425585928, 776952984, 108809668,
     895629986, 476045612, 319088257, 15396304,  229411864, 100883731,
     726723382, 967735793, 315746931, 210505320, 298505642, 52124942,
     115000780, 786133062, 724237298, 216879168, 251797315, 147331785,
     386383908, 789125381, 482307090, 128950595, 278019655, 577474020,
     395852752, 515003233, 380447696, 656310092, 884887902, 768477144,
     815384366, 344543851, 637019766, 723384100, 315474653, 944801664,
     849218151, 905599151, 921647948, 313255301, 847627108, 485319670,
     67225461,  472679491, 135834548, 775242522, 141922218, 264741447,
     23732109,  857668718, 555703385, 525188059, 294858038, 141833175,
     988718316, 135169406, 519914332, 795937116, 534323213, 202277337,
     371364653, 546189267, 217765929, 384700359, 156540038, 386473056,
     676745984, 988669925, 811343680, 180044242, 519462234, 634307863,
     750725934, 90621331,  190108336, 269260016, 286188381, 358482198,
     598466601, 240663242, 104121829, 254002718, 29152619,  227963516,
     773927274, 146149762, 738309754, 363105723, 195217296, 398269774,
     261031175, 183624030, 750451376, 893705499, 985799624, 262622108,
     129725641, 967623831, 525383662, 821560632, 472876524, 973841833,
     200540886, 469418829, 884202873, 123161741, 382647985, 555132254,
     830604720, 279276341, 875637238, 295663649, 957433935, 505656362,
     356401451, 874147756, 733069111, 451826244, 232362468, 178628605,
     237686066, 540306504, 295929230, 246597165, 16175440,  844052262,
     707866015, 602371835, 57229205,  614563565, 190502563, 497488314,
     506077784, 355846095, 411321074, 308444405, 509569369, 19390766,
     487435174, 355732752, 684278619, 210744295, 638787948, 359233870,
     278097289, 881806026, 691708510, 883605367, 288384949, 620109855,
     688978457, 704827855, 376173617, 336347102, 283317936, 457903945,
     279991156, 232896893, 370127053, 229651181, 35598027,  882810625,
     125983061, 278635086, 659969865, 21482903,  864848729, 667877237,
     908803332, 38128973,  41172858,  398488490, 249516183, 814079057,
     929199130, 247708033, 152396125, 614411782, 156164641, 537226358,
     698645072, 152892644, 410721267, 577967286, 506134956, 176007122,
     650820991, 168362693, 53585041,  109562538, 57757738,  465395798,
     583377600, 291659354, 118221270, 896981254, 69400915,  520412726,
     548724816, 73647706,  455912351, 802760666, 143756736, 1001722,
     988842268, 657927330, 305731804, 813878824, 291032649, 66003083,
     55377448,  945905186, 521271656, 802716248, 542070705, 625783435,
     614733084, 881888853, 61830327,  114261360, 778969539, 326610278,
     887550492, 243873395, 702082773, 775186487, 641262476, 116975984,
     786896107, 617119749, 581788252, 905439988, 324792488, 435913955,
     436613045, 193118431, 136276575, 589343006, 550886452, 768079099,
     278404905, 697756923, 813063678, 318534875, 703789648, 527104746,
     328362731, 535322050, 477706506, 440771872, 360504056, 805840860,
     165807471, 982987126, 864306365, 323732253},
    {4,         16,        64,        256,       1024,      4096,
     16384,     65536,     262144,    1048576,   4194304,   16777216,
     67108864,  268435456, 73741815,  294967260, 179869031, 719476124,
     877904478, 511617885, 46471522,  185886088, 743544352, 974177390,
     896709533, 586838105, 347352402, 389409599, 557638387, 230553530,
     922214120, 688856453, 755425794, 21703149,  86812596,  347250384,
     389001527, 556006099, 224024378, 896097512, 584390021, 337560066,
     350240255, 400961011, 603844035, 415376122, 661504479, 646017898,
     584071574, 336286278, 345145103, 380580403, 522321603, 481773464,
     938730529, 356672305, 533022126, 647015527, 635467608, 361828235,
     618518913, 103460002, 991495883, 25292647,  155867892, 498467444,
     824794948, 879064991, 130681935, 887199534, 317883822, 393422584,
     182551494, 861902989, 637599517, 987486642, 735574558, 504148394,
     179887014, 949753076, 218705695, 944626726, 871698528, 67475144,
     548894434, 101901878, 861764835, 180152331, 261385742, 420373101,
     655751919, 131241672, 999970470, 231826333, 122884273, 106406445,
     136140903, 915366093, 18976018,  141634271, 504976967, 686557996,
     636796435, 249345120, 849898238, 260017335, 261880347, 370171717,
     123847861, 107385075, 908198344, 586778735, 671521894, 791531643,
     728335536, 716490394, 272454022, 252074509, 831205319, 152262343,
     534499023, 215776407, 885547991, 808501739, 338662883, 76177999,
     682246569, 919161292, 774068737, 713215267, 79890414,  250755150,
     476673537, 338128483, 771254502, 348399406, 527534812, 693444800,
     101903274, 847047904, 628912038, 473521036, 613423660, 855988580,
     266643739, 924741552, 298037102, 873277099, 278272294, 283024321,
     533898200, 306672381, 525225929, 705332604, 646701887, 471799664,
     612829760, 238079461, 751775053, 769846982, 716081409, 973301589,
     380278462, 662905731, 492843369, 816646525, 915435148, 820494890,
     622190176, 728435887, 422995707, 178415415, 717987496, 660261737,
     962861767, 951788547, 476235197, 414442055, 467733884, 802042727,
     345992625, 166382075, 595261264, 403599697, 428161150, 260985751,
     877156396, 278156482, 699583010, 734240839, 194251200, 737229331,
     366065372, 76837714,  217968592, 328414453, 318777867, 952883309,
     388944305, 436831806, 434610486, 965663498, 956016468, 586726935,
     617618803, 544046339, 70420520,  875406519, 706536742, 409276084,
     713460533, 531426206, 405493819, 482341449, 448623450, 151412625,
     39916377,  251813321, 952345004, 619186255, 490252137, 679240041,
     853680367, 528491595, 193441393, 664056250, 44594231,  35136855,
     965655562, 541834456, 875334013, 394707404, 931167589, 19129149,
     128951614, 923204060, 323128498, 665097361, 261831353, 468177966,
     723318368, 792304915, 634832197, 548874543, 306510296, 615794614,
     601402794, 384956505, 947167807, 610765170, 89114388,  589020183,
     512202722, 666233178, 276037937, 662192809, 593036088, 791358821,
     587370702, 392383573, 467606721, 854346248, 684568864, 85077780,
     783676447, 441368314, 72972050,  323196170, 436429506, 887758507,
     474492353, 910351056, 76648102,  467286964, 83693313,  909007564,
     351169268, 205269855, 348493651, 86598288,  572297449, 150935755,
     758906438, 139762500, 643738239, 291444222, 188261970, 287160748,
     493467972, 457573031, 770888112, 751296750, 129159987, 802136425,
     945676173, 462443566, 884615461, 125241946, 315913436, 153284559,
     362918004, 600999015, 251468610, 835022,    319736829, 749935431,
     619707064, 635329540, 509433588, 73035130,  714808704, 231619932,
     23229211,  113911404, 388802130, 364002709, 462589061, 370437754,
     168248727, 771150303, 833461484, 579898269, 173717893, 81739885,
     2272894,   730673636, 524938367, 616405956, 324662764, 147944619,
     590278680, 19160429,  590995297, 22195602,  979989287, 941678129,
     112423459, 293512804, 877878513, 349502957, 643835465, 760668701,
     699976954, 601628669, 988757138, 354702111, 936669173, 619729808,
     502818265, 687859945, 402455624, 233187752, 594913256, 593464745,
     359851945, 646889783, 445731998, 461313394, 690708871, 381060132,
     463757966, 124671729, 624651561, 703387668, 584422716, 495586302,
     130456706, 338917307, 8297677,   354010778, 632409201, 927803910,
     207672926, 235506664, 235594959, 154849539, 305734385, 882296078,
     986185814, 161071304, 780832306, 492291001, 326383873, 132432912,
     366573808, 804963710, 883881264, 465445059, 735339458, 716727891,
     421500747, 489850301, 845199343, 355848905, 980326331, 493730297,
     328495357, 37695635,  194673306, 409025940, 654344624, 779846308,
     312161926, 969883976, 376556915, 254376928, 919698691, 147929923,
     465079934, 950790651, 625714299, 462425252, 48974019,  270745406,
     803848049, 437226149, 708991935, 749677526, 753318329, 888128470,
     228746406, 717328123, 428412212, 818121922, 641949860, 10460935,
     429735778, 980022112, 596854035, 164474932, 484004208, 735666585,
     957738350, 140424368, 405096419, 235066089, 110753533, 885925883,
     424014690, 600713548, 807220756, 621895155, 351374135, 276120286,
     768519169, 757469470, 878725516, 937741002, 650007303, 987354343,
     560287928, 775639865, 247856829, 955047336, 464476175, 197913991,
     291048016, 231021830, 994061203, 560709099, 967185900, 474098005,
     486913298, 749583668, 763236914, 841300884, 728997175, 288240639,
     49732538,  252432036, 457262181, 353416373, 749850431, 182026569,
     800052632, 381549676, 649127817, 313349714, 264927250, 431744676,
     541453282, 550689720, 397857456, 812409813, 912390809, 257847924,
     891232943, 348087358, 155324707, 323266912, 742991030, 233927998,
     214643997, 337684506, 173501509, 263577611, 649069717, 492509368,
     468591139, 423094679, 641642635, 37226096,  824525336, 28070164,
     340191455, 287467224, 527971347, 787703624, 52492728,  870332353,
     993856465, 883414794, 635638072, 693808470, 406184985, 282972408,
     723767220, 887612854, 6419378,   283570834, 310224227, 472083967,
     657549369, 193484260, 168005360, 140087407, 311750720, 86150827,
     928161050, 290824785, 843989084, 838356906, 597327559, 178020114,
     349439746, 115792246, 169887616, 678075745, 802637660, 889094716,
     244690135, 604828653, 896467359, 561331357, 662249002, 296280913,
     465376139, 944702491, 234929681, 48636921,  429474904, 319231766,
     50903406,  446664444, 857705038, 957387941, 431222925, 476223905,
     393463429, 496564554, 817765428, 734526021, 356215832, 523906695,
     55427855,  15917932,  975322955, 248696579, 456744298, 396543439,
     320816136, 127700868, 656623855, 512503483, 343740239, 325340687,
     947392868, 589830624, 208485169, 906564666, 904989276, 156575389,
     449174191, 495878813, 737828978, 648216356, 626160435, 497497174,
     877198940, 558780916, 122509940, 573633697, 553040657, 687654281,
     132322194, 664151201, 91749873,  539204134, 685923184, 563130830,
     766916401, 764698746, 36346705,  658194351, 245235734, 277848677,
     759488920, 821090037, 238266420, 778415529, 61247499,  845447597,
     566772577, 273404178, 391393427, 113477573, 412390244, 431624602,
     180605173, 871865168, 653906347, 159149988, 164557009, 419869546,
     936808148, 841534420, 573112245, 779024796, 428648968, 772771199,
     472226831, 751848946, 275632414, 37489724,  419818682, 91745532,
     235685654, 39520058,  987948228, 66922401,  718882144, 136861569,
     907163855, 348527749, 720288051, 821764806, 497466741, 305067989,
     558801065, 576267986, 578180278, 942285083, 502688180, 82842590,
     450239640, 124868541, 857527465, 939676663, 755426941, 892351213,
     434881458, 535217025, 394401494, 907534923, 584032565, 543556112,
     529920425, 646559098, 981824368, 575591230, 808624628, 363926855,
     404893668, 461102943, 296856740, 334022397, 425694872, 620840221,
     384390925, 232012950, 693047282, 179132515, 477807866, 395385401,
     720354470, 214151321, 582945507, 887765303, 173901280, 846473589,
     503637927, 31467285,  497616017, 952929924, 889219556, 460525926,
     848093849, 998030665, 8532308,   107579814, 14245841,  339203950,
     750857082, 199802782, 509822906, 901127429, 577599222, 59773965,
     747243229, 147453091, 677758380, 781507078, 54625114,  601386725,
     986056483, 820641635, 559529912, 827906170, 314188965, 577827851,
     190577024, 565060854, 621318514, 219689579, 860736082, 487978195,
     883880985, 29379068,  49701041,  918761790, 690638406, 951283268,
     550232235, 280373046, 957749094, 894113872, 676787707, 201333681,
     845756337, 576918620, 973852509, 681054841, 400888303, 827764238,
     283570580, 49063900,  534735446, 198713722, 554337556, 191854601,
     117028506, 997361841, 212827959, 587451118, 343231238, 869073526,
     911385679, 10450254,  553354423, 87161690,  351643067, 44055160,
     158392396, 111245506, 636597435, 337876127, 460292742, 302858379,
     310541848, 463802775, 989978573, 81516967,  257768617, 598280952,
     666200836, 362673582, 703491441, 745722892, 745611756, 566791793,
     608480544, 971841603, 278983667, 796927587, 569788323, 303597885,
     583666047, 762439430, 597257816, 526427540, 288038950, 454113355,
     465404567, 970814906, 346361747, 501681060, 449816238, 912186659,
     407022892, 276054145, 392087454, 22955365,  413810428, 249601969,
     319915413, 946254155, 937142643, 671860952, 774960802, 460025879,
     359148369, 411007839, 249122910, 519496895, 18443994,  749244508,
     757964667, 893488971, 496741790, 695391900, 938716919, 867788028,
     562883419, 113304835, 497347907, 408694370, 66044497,  115341679,
     111306444, 907213931, 47019833,  936540617, 996427319, 161486106,
     681451786, 547416824, 42129330,  245504053, 815485021, 818290846,
     262107847, 302817959, 817754330, 46364098,  958852578, 253947963,
     851803631, 510047058, 483206935, 519218801, 382089885, 957615224,
     41476169,  751839779, 556389093, 336894651, 880436897, 839570914,
     308010830, 461904339, 21889349,  961122587, 692763330, 191342733,
     27432572,  813510865, 802039939, 213969226, 357348537, 625561264,
     86502953,  492727704, 748748401, 321732180, 988175283, 141114787,
     527772950, 641284258, 269886502, 977495571, 125808780, 269169107,
     823410209, 148798765, 175548654, 884243377, 669231307, 976488086,
     664764377, 679269638, 596047099, 99776257,  68532191,  898685635,
     584138999, 895239509, 496985747, 310517680, 603626375, 923854516,
     975338598, 16186893,  561345474, 126208540, 73527459,  65962479,
     971205356, 810884473, 980904053, 378775837, 254828192, 200791515,
     346401644, 839522059, 736196100, 363456944, 239481421, 18377634,
     332455707, 743550775, 138078884, 249690600, 12210859,  883262723,
     313132386, 839895915, 913644689, 260056313, 168742439, 830688375,
     49099162,  359555187, 871659927, 688437124, 707661791, 687016033,
     193617456, 829330048, 167087828, 933433288, 559539554, 352015664,
     293901709, 981985636, 702253592, 980043382, 972732970, 308480377,
     713628143, 897915891, 181470526, 716928810, 793447652, 916466430,
     483281874, 309748613, 276179226, 268996788, 289324339, 642955225,
     788164969, 163166755, 27211914,  997655917, 777455957, 891232803,
     280296900, 638657148, 382417168, 288857879, 357168676, 667915394,
     720118083, 981120397, 95182420,  496154832, 966587503, 964824089,
     530379859, 693563005, 569496794, 547256636, 343170860, 310565687,
     940101383, 467382838, 777260243, 279130530, 292304857, 377608095,
     437626778, 209346525, 383790781, 416683099, 88181044,  812953717,
     40259503,  532914722, 730497876, 916590374},
    {4,         16,        64,        256,       1024,      4096,
     16384,     65536,     262144,    1048576,   4194304,   16777216,
     67108864,  268435456, 73741815,  294967260, 179869031, 719476124,
     877904478, 511617885, 46471522,  185886088, 743544352, 974177390,
     896709533, 586838105, 347352402, 389409599, 557638387, 230553530,
     922214120, 688856453, 755425794, 21703149,  86812596,  347250384,
     389001527, 556006099, 224024378, 896097512, 584390021, 337560066,
     350240255, 400961011, 603844035, 415376122, 661504479, 646017898,
     584071574, 336286278, 345145103, 380580403, 522321603, 89286394,
     357145576, 524999074, 864554723, 632746456, 882854172, 604451954,
     878566342, 581561437, 631356700, 784920961, 464356982, 734250441,
     885915367, 385221619, 677838916, 842928423, 877248313, 765039261,
     504663559, 152801398, 661935812, 367523660, 585448769, 128529961,
     76203671,  392183805, 986561078, 136443393, 662531176, 793319890,
     536353481, 341238122, 169246028, 682076541, 856447426, 981155343,
     110288271, 344154556, 370491155, 74408010,  429196409, 281331420,
     158455313, 659080271, 662334610, 340537536, 314568688, 753187530,
     154368133, 812027821, 517746298, 57063192,  369756070, 686787205,
     201139269, 713358792, 47335004,  963634570, 763859092, 575415426,
     246934620, 163451685, 340267746, 614379369, 613563573, 357416050,
     791318667, 408409242, 270266090, 700390659, 516001654, 42861547,
     378829163, 586681435, 552705698, 157769508, 480126703, 891965693,
     190126298, 514505299, 872104961, 325163622, 981229479, 810775448,
     598859996, 310667992, 32459810,  325504882, 765835057, 16322919,
     970428482, 163111376, 528453379, 174317664, 516402135, 217086571,
     714120966, 349815260, 789592103, 723683250, 173195518, 575771804,
     587638123, 323011896, 514369640, 691834924, 699855640, 789588494,
     399169133, 904580633, 32508203,  277616390, 762392085, 813341423,
     863370460, 851866726, 745126924, 239313035, 420347271, 935600197,
     627655210, 139022267, 76939214,  448319483, 274910569, 678560910,
     318452751, 611090083, 848085980, 99584461,  916239353, 708259177,
     788038681, 275868577, 835774489, 809317610, 788783808, 376463052,
     442879841, 701080402, 950148887, 678540835, 756770366, 966942579,
     590954289, 990920135, 599792267, 918468417, 467138687, 507212150,
     164900021, 61024159,  507967522, 393298014, 178389190, 204051339,
     562048106, 31426691,  376542951, 892617361, 126303416, 699105135,
     443736909, 823341158, 202416994, 198174112, 129566975, 129726822,
     59039738,  103472701, 546121953, 15862434,  883375550, 83404022,
     249560406, 115600062, 38450287,  489411665, 640926167, 167863952,
     253422177, 439562958, 592234796, 942729022, 339262982, 261001164,
     722502726, 695942749, 59777611,  898819685, 875194336, 773888709,
     613113655, 449002952, 852491933, 49475860,  806359517, 44654721,
     452222299, 279946483, 46879828,  5728068,   813772701, 589563257,
     424618213, 174451588, 372086292, 791925388, 955396001, 575837556,
     754201377, 70200874,  547099015, 817601552, 261594940, 615928990,
     949763181, 891914297, 50116144,  831925856, 201805360, 809784109,
     668924540, 240817151, 403867884, 536877065, 166910713, 868470354,
     300176344, 594855322, 85714668,  524612427, 635665948, 156136831,
     776920310, 51763293,  970738216, 501118519, 257386909, 224447653,
     240042709, 35290955,  347378147, 790238946, 521299787, 7424084,
     969704116, 792911997, 251413457, 375456781, 682533706, 65919999,
     728732550, 286267005, 532951161, 814559890, 711012538, 953876013,
     787701937, 232388527, 499407160, 565130893, 151672061, 728329865,
     926554375, 207683608, 598575074, 276661353, 259503908, 735135049,
     930976796, 787124028, 113465212, 528924806, 468563963, 918995821,
     729810844, 626638047, 219941015, 690878959, 406997697, 958463014,
     599520874, 963063551, 347756789, 64632599,  891473320, 690398450,
     447554207, 464800046, 436100781, 648099687, 164128892, 458249791,
     277117461, 902422490, 926822088, 554618190, 429818678, 907776137,
     293266982, 691702933, 783463530, 392343327, 337469808, 980195700,
     696039485, 235089826, 434390983, 121235808, 236323930, 371973133,
     464520484, 762561353, 935787921, 72903612,  749313024, 891331403,
     894024947, 888220406, 970232735, 332555551, 559162023, 336832542,
     769144668, 882484037, 152732881, 934360443, 692128487, 86265628,
     164452171, 266825336, 904027458, 644972034, 234923346, 620501904,
     747135452, 865706188, 539262583, 281615635, 194536680, 100457522,
     419459927, 759395590, 177331939, 544595441, 116099230, 792110712,
     907880626, 3411135,   193106586, 745141859, 998328581, 287502542,
     617196087, 669649684, 821438093, 314024664, 674172033, 811193498,
     770413340, 426985792, 393014775, 413967067, 353087086, 617361386,
     326858278, 465874816, 829382857, 168850013, 909845357, 729304089,
     367230515, 659130604, 187790714, 651024190, 541964325, 587354134,
     66060728,  516028955, 63428969,  911609507, 233020802, 680600694,
     219472376, 379772011, 468530638, 226136123, 124963424, 441771252,
     572082110, 628588620, 261118010, 393271488, 25338345,  183020861,
     823028632, 857484700, 181508323, 152682153, 482838906, 575729571,
     384813137, 744271099, 742265297, 838897570, 230551693, 38855789,
     315713461, 709976352, 318497399, 619527988, 181243465, 209662233,
     613829353, 912640565, 259687964, 153890447, 111801837, 165331337,
     833994721, 435693514, 783734071, 892939125, 353622529, 519417781,
     16723918,  343038297, 251794465, 49358888,  833121865, 78289982,
     548615762, 734964840, 806527173, 569762939, 906984560, 559972776,
     526716532, 672772147, 370898207, 447602271, 566730602, 290365362,
     364838003, 510083788, 738669475, 737970863, 274435603, 907897885,
     504954619, 995524777, 570240793, 673636736, 89246412,  64491430,
     66561277,  867991691, 322021501, 753168095, 134071390, 128677630,
     520954596, 704993434, 973817249, 128409260, 677889066, 392988817,
     885866334, 127303158, 596965583, 345662943, 282008875, 208768426,
     675457508, 827567657, 602022122, 835295661, 548603295, 576560626,
     548156407, 423587420, 905207324, 204450035, 180587266, 138854293,
     471603402, 887697603, 131719459, 524880597, 215010570, 182411211,
     852979118, 743361141, 732306107, 250342832, 837670084, 582930512,
     629299308, 129488827, 417372768, 518637588, 314442831, 247280041,
     32858091,  804583778, 728709816, 993672315, 721585101, 871046575,
     107712395, 151028696, 908842448, 206642449, 898571416, 928131094,
     247204275, 49283848,  286828867, 645786082, 489382466, 917866723,
     340808138, 613926515, 450516641, 195282337, 508240755, 633204203,
     796454597, 518911233, 91874645,  55707937,  324678691, 118233143,
     199180096, 836650388, 491821829, 569202165, 265457001, 384027026,
     912907,    867573972, 126345790, 896165613, 885552532, 579346547,
     280146451, 819551222, 978062815, 757998486, 136136355, 41009849,
     652730567, 609282096, 789764201, 180973963, 112794296, 99298191,
     170944423, 850545565, 239000938, 201862507, 480040160, 337724825,
     478096629, 442209858, 992613332, 855027827, 718576934, 6280043,
     380419310, 210410194, 414076856, 358797766, 127972968, 725862448,
     526064791, 541887357, 519428829, 460325503, 399929326, 712192147,
     720759588, 145958230, 174120752, 128323959, 368889884, 329661725,
     129036152, 550135300, 52839211,  873963821, 15256668,  852166769,
     469938213, 986760342, 18411096,  546761846, 836033456, 480089890,
     63761223,  915145697, 270058232, 330343685, 317654560, 416329685,
     353021468, 841096447, 742640437, 702969603, 574600485, 938923655,
     203028082, 683810405, 538740238, 317442878, 403985514, 168356162,
     539252018, 377912392, 849115623, 426807367, 715347767, 23750848,
     110403879, 149962071, 860055281, 203311670, 266398417, 412234844,
     96988668,  310424414, 18843580,  221593960, 562074939, 274283124,
     787370561, 643084459, 611083480, 910060538, 988370908, 606642865,
     615779244, 326309604, 937593982, 686951697, 312242890, 720434015,
     595925145, 217806960, 788343567, 877992657, 991963508, 980939456,
     139023330, 621535363, 696273601, 865899245, 164275777, 65126968,
     632462343, 762882549, 285430058, 121757309, 999153105, 466445942,
     665409073, 234985888, 755127380, 845190014, 322036084, 441500338,
     980692572, 489328443, 464685662, 99010320,  349932836, 934504167,
     760372288, 723620638, 328671327, 464095954, 166051066, 496956881,
     765782849, 902988786, 541099142, 849015276, 53920439,  137399437,
     361062965, 431934714, 903669870, 310875976, 516617568, 862391582,
     562497732, 508055464, 569047699, 87471024,  236655422, 845470292,
     469846013, 332112551, 962287973, 418142719, 589202736, 850157139,
     962322000, 779741401, 969144254, 347128411, 321960961, 468935540,
     423104721, 198278091, 896363027, 552075962, 388144906, 196815781,
     5456266,   885107458, 661652188, 365593232, 465443970, 735040569,
     547550721, 755267048, 602551773, 90581266,  851616643, 175857220,
     589992518, 160093076, 598370073, 77834444,  263550905, 153428592,
     311435301, 521770269, 221029507, 32520946,  560154129, 982240943,
     296495128, 981336826, 766839722, 388318601, 633935479, 824638547,
     363458334, 147353920, 372169991, 701114633, 946653574, 587224886,
     593373886, 359045192, 768372627, 179286931, 254852170, 291766581,
     902802757, 798335338, 93559437,  498130638, 954987133, 141625616,
     235834516, 930486951, 86191493,  825688074, 735102920, 735966828,
     207039559, 933041629, 589562220, 14495802,  135618575, 20111886,
     438881436, 183983670, 417000677, 436484321, 946409448, 702660497,
     923227509, 788570017, 882758173, 628012034, 186780263, 382733083,
     720553565, 930116668, 358471026, 940899683, 163305913, 86964866,
     487851707, 522732015, 207990746, 732658971, 957727301, 116522267,
     533576268, 196449182, 23015766,  894313726, 187942757, 52576386,
     773157220, 862509679, 626187093, 758208745, 920655365, 130805510,
     357362035, 574165890, 127744683, 703233228, 689072940, 911339173,
     772050715, 412477649, 577755901, 957359823, 76913012,  121468035,
     623040517, 496383845, 559748319, 142785358, 88066263,  495948208,
     779813235, 220196714, 617722168, 708918491, 938958534, 91019279,
     99562494,  982296641, 149544040, 369124438, 82613992,  260704943,
     279955562, 266520028, 980480949, 6681391,   873499213, 633175839,
     431113714, 539095346, 555683790, 872287074, 585553150, 953792059,
     582994398, 638501698, 952469417, 378977721, 551707990, 577541677,
     354149764, 275281420, 657424702, 5243092,   268161231, 650425056,
     76456437,  633621424, 299651715, 918354156, 956048873, 987779237,
     500286029, 892485216, 112893906, 799286448, 624325894, 418789288,
     950406199, 366180134, 98559462,  27718125,  438679119, 484610558,
     209817709, 32875268,  14232858,  336896732, 625445125, 718450963,
     276204254, 339877414, 412736841, 479227720, 923051513, 899972249,
     647104504, 3291671,   231636795, 697763415, 336707096, 674665850,
     623628834, 815790943, 270254065, 425170916, 39526114,  774517375,
     567321326, 499231000, 159371186, 218668901, 594996961, 788357927,
     537447673, 240635877, 935002890, 308876548, 834537790, 565131444,
     975234713, 680082344, 385856310, 781046078, 236425875, 528454929,
     478414532, 291263913, 692339450, 443544664, 315727447, 417286243,
     287149414, 157234064, 276407151, 868557259, 281066259, 638868129,
     265600580, 447903668, 300044249, 869519998},
    {4,         16,        64,        256,       1024,      4096,
     16384,     65536,     262144,    1048576,   4194304,   16777216,
     67108864,  268435456, 73741815,  294967260, 179869031, 719476124,
     877904478, 511617885, 46471522,  185886088, 743544352, 974177390,
     896709533, 586838105, 347352402, 389409599, 557638387, 230553530,
     922214120, 688856453, 755425794, 21703149,  86812596,  347250384,
     389001527, 556006099, 224024378, 896097512, 584390021, 337560066,
     350240255, 400961011, 603844035, 415376122, 661504479, 646017898,
     584071574, 336286278, 345145103, 380580403, 522321603, 89286394,
     357145576, 428582295, 714329171, 146404191, 490778527, 88439825,
     805273627, 92046126,  124318408, 320608590, 807295346, 136207314,
     594500689, 693131665, 94810530,  829529670, 351741703, 18424499,
     175349709, 150463989, 547280538, 618706653, 293649176, 948435567,
     955439505, 931549153, 146250372, 668166199, 990849268, 855122372,
     537669524, 876489219, 970304690, 940894238, 673724490, 909935751,
     839230865, 80712704,  542427119, 709838648, 713705801, 618609982,
     967939653, 667235918, 502739416, 55353481,  126482984, 720463168,
     131070159, 765108252, 290897516, 811399045, 425574770, 719346247,
     596620069, 312379715, 51366487,  261469929, 851614972, 8481631,
     999714070, 838705673, 600216294, 823653100, 322552212, 993502340,
     259869813, 540277019, 170618352, 709959711, 863589092, 458232342,
     212571830, 108575029, 850524179, 308181513, 117071030, 568037964,
     967843448, 279958714, 797323354, 294754856, 904838711, 904957865,
     658905890, 613661572, 502792992, 804137226, 863324769, 861261467,
     247916366, 571328931, 849455216, 746790840, 495904594, 416752648,
     752268826, 543195685, 46469288,  911458198, 28159487,  9087204,
     466918715, 237796095, 89605896,  906706216, 146092914, 148107215,
     222359567, 539356213, 886369480, 698572459, 865345456, 697916982,
     205105086, 727581195, 349482091, 832767840, 958016506, 810151998,
     793518672, 16437983,  517304738, 913722502, 778388237, 244171133,
     93740372,  990703224, 830576555, 489789337, 493286023, 824179410,
     716483829, 753429664, 693093247, 816232391, 702833604, 420892774,
     745387239, 882413776, 520722707, 86039711,  337474203, 24291049,
     444393723, 295484186, 387279097, 355451540, 955780766, 703255486,
     428328579, 642828281, 803485143, 800097643, 25754495,  646053012,
     644611421, 502954060, 742903759, 47934977,  612861667, 464397010,
     620884034, 39885622,  926629211, 784743952, 897973702, 680352654,
     896996933, 33273268,  873061657, 591249308, 880334693, 189358953,
     401672813, 651158247, 802760207, 135271985, 292726765, 830103987,
     517345803, 534130157, 62470874,  389660410, 437541957, 475177952,
     703023626, 659956299, 741505139, 292168203, 331815913, 624007686,
     290574801, 691609018, 566255983, 49578260,  848836067, 481379556,
     967306464, 884128125, 611158180, 384219659, 658466425, 972329210,
     136413438, 608442050, 435850683, 31378904,  52981284,  587619635,
     23952562,  298052850, 852481185, 658104289, 663064843, 762376494,
     220172749, 532154161, 447959101, 409953339, 126114814, 808762405,
     437979977, 710873294, 670532048, 83138391,  10393358,  854213854,
     825384807, 258080545, 561763451, 414570284, 703779332, 522966006,
     822910370, 986433418, 910506892, 590114944, 751608995, 361661732,
     560456187, 967707583, 31665401,  722393977, 564792242, 567248143,
     490083481, 804072903, 912316504, 11396942,  156624352, 327968811,
     325166613, 213131615, 867981572, 446914217, 107255644, 233944658,
     251649721, 167410758, 546384908, 830919981, 986418025, 758347248,
     155411787, 174008362, 833067628, 359560120, 110836051, 414235637,
     108569644, 827589199, 753849426, 915648347, 954548836, 422234190,
     227077254, 207840240, 947418375, 99684627,  600340832, 444253495,
     590699188, 309969212, 663835112, 524642681, 128002806, 776821225,
     413648445, 105519247, 844130289, 643066916, 678438723, 188764610,
     822808304, 277991127, 220073197, 635256109, 577403918, 257735011,
     288624627, 883418704, 80946776,  878194542, 778395669, 491778016,
     736347931, 377883432, 879419450, 849828560, 964635962, 712606633,
     277374656, 192718634, 326799672, 889633665, 351657030, 511850421,
     638219209, 99457366,  451766026, 892279979, 600851892, 886367779,
     505574870, 636375051, 162289914, 154446493, 233263054, 596230291,
     651864964, 662715534, 528739750, 320760179, 430566384, 849701377,
     266200279, 676609655, 131419047, 751422496, 287953119, 300312110,
     953640736, 96204442,  236426105, 688943596, 834655539, 769037833,
     272562999, 426824286, 331347343, 606296162, 77918192,  369323716,
     92665362,  193075883, 827908380, 536213635, 320307355, 673118949,
     593703020, 500949838, 429728985, 435420323, 251956413, 995404566,
     491359671, 357561924, 573095352, 51461841,  109345451, 313825107,
     438841060, 478258945, 758401332, 119038602, 839938099, 475190851,
     893270383, 600943367, 753683964, 596149043, 98788518,  348307520,
     361389215, 21101042,  34040130,  74923433,  476224858, 370960253,
     215675576, 241022836, 145407867, 746770283, 736346987, 873477660,
     878095715, 8932465,   1185721,   437692375, 511893471, 912654833,
     975478474, 128834,    290066425, 338501116, 869056350, 212316111,
     304950520, 327647548, 858357545, 875765086, 912923880, 453604641,
     878361716, 745423426, 575716882, 59965168,  626142042, 949966351,
     256980454, 138114532, 69437118,  29360921,  19813311,  934059157,
     849497691, 139099751, 886466557, 617499669, 875897346, 997426474,
     150681893, 46741200,  447565464, 631466469, 340916532, 921787993,
     711029464, 70137925,  451470334, 812932781, 776565454, 633307104,
     198384913, 910812561, 156771054, 619224805, 647797137, 872070848,
     485313287, 298548501, 805326026, 819158755, 730141930, 82461904,
     694237160, 5630425,   920134528, 218400632, 236312164, 351734019,
     700684755, 527730361, 119640494, 784915647, 813688752, 91923203,
     988258187, 919151445, 517946464, 624093702, 430278901, 203319131,
     588390599, 47839231,  707337469, 794696146, 528815076, 15615850,
     479163793, 276237366, 123645478, 349735284, 685321360, 732826777,
     975503813, 161684433, 905655723, 821306255, 906543863, 239039353,
     693079384, 742652626, 773897297, 32179682,  61558675,  406622642,
     202488698, 253405866, 854528411, 433555965, 514204437, 492032822,
     142177852, 228564900, 295925362, 153595425, 4366302,   286277071,
     964146078, 242400658, 806430118, 999405957, 203520077, 351370902,
     519396781, 916852451, 589997853, 292984889, 137786226, 975253920,
     1759120,   156674726, 286805454, 415512985, 214987320, 324101407,
     493242123, 126199485, 354645383, 316470245, 157279096, 254937320,
     148637512, 669911710, 543627856, 944028941, 809140555, 421880443,
     14059022,  788573257, 189878859, 231423386, 133428497, 919916361,
     302275071, 333359650, 513972337, 246692920, 143315648, 902472803,
     29951168,  502658131, 352748469, 436476875, 262503485, 978711620,
     11931166,  329742853, 964231195, 494605322, 725442774, 257325291,
     456223027, 967437610, 899646559, 970294027, 528762892, 261634219,
     957957964, 909812879, 514172902, 405102039, 942362168, 887654402,
     849166127, 626909533, 453530259, 911662617, 654086,    43880557,
     283198618, 138351249, 384044897, 189587013, 746791529, 553439782,
     339522542, 292458091, 227528255, 567628815, 315523302, 193751501,
     944473104, 64130000,  656868197, 233504328, 666936048, 754921115,
     195331359, 766049041, 393617264, 899944534, 951543499, 3741234,
     797394801, 511915423, 660145750, 117970722, 460021088, 47181512,
     976902349, 895496194, 273540471, 116000264, 675913868, 337558891,
     761593662, 714796853, 283015317, 344277667, 162775519, 667749137,
     13545555,  628295994, 274889196, 922911017, 332463482, 597660873,
     688574636, 28509114,  883141594, 48035624,  665578537, 518848218,
     152836028, 344552689, 285372101, 228151841, 428403932, 465455278,
     415924309, 106921860, 871197746, 50704447,  404925692, 396289260,
     286774246, 63805953,  618239150, 172761402, 6085093,   704905399,
     138817011, 84286962,  718836811, 643735843, 736425475, 892719918,
     384127082, 68374026,  45389152,  492387114, 384446093, 669485815,
     413826263, 338045421, 777067807, 402213822, 520699316, 502397084,
     440015456, 770579028, 655454746, 92962620,  295174988, 489155126,
     141164819, 400929240, 336031325, 676184839, 620508909, 984240608,
     281450791, 954822625, 982028211, 544609899, 846200992, 867919387,
     248258875, 533636637, 456015953, 198074243, 956873504, 710411094,
     727556929, 12741607,  279590412, 729632524, 763956926, 171154682,
     201480672, 865439908, 179839306, 594656403, 640825888, 101165166,
     940883221, 413863736, 337602035, 172797797, 437617323, 904273452,
     515322624, 528612669, 729297304, 542322992, 323022438, 971417179,
     952568845, 922268468, 529115266, 74553124,  13782667,  534359544,
     991028012, 572205358, 145020904, 260008568, 63915989,  113528913,
     335574935, 878235893, 800618858, 434156526, 69071053,  75034806,
     38354826,  933755180, 831615295, 297281207, 190162952, 757647422,
     136900559, 21504211,  981809520, 696793892, 347017091, 247100792,
     745985639, 194841874, 134249474, 979767763, 200684301, 739592864,
     851778032, 945664218, 759243935, 343608224, 494098422, 239886375,
     96643456,  466724043, 16476039,  550727479, 794338418, 155933816,
     937936399, 655926379, 347321147, 761203890, 636714153, 756777826,
     368176664, 303012114, 501502171, 219671792, 845166879, 376417312,
     847213985, 147994341, 30223320,  509850016, 245854723, 963794387,
     131808275, 34288430,  665558725, 512825854, 859881737, 791784034,
     307912226, 626688264, 811834039, 993541804, 40480939,  902229462,
     468046628, 623843301, 518459782, 486367717, 323268361, 944765365,
     821750983, 610519356, 75221140,  454432392, 260119127, 418113700,
     354729708, 828451722, 204270913, 266485177, 94047667,  421316153,
     495821879, 301475115, 265595414, 178883100, 127361663, 348177526,
     104185647, 31799326,  526307970, 717254431, 883154576, 266985993,
     799649738, 850728215, 422608130, 607406021, 986420740, 29418397,
     229040958, 828848267, 287014141, 526857004, 180571085, 309635213,
     368349086, 553029480, 572397386, 976332274, 784081950, 878538854,
     816156948, 827595998, 163167401, 473654471, 270608756, 195670521,
     215327837, 143709805, 176034382, 727554441, 350269302, 610994158,
     411965784, 450899900, 761832419, 180151079, 145155316, 500336434,
     315700073, 814133837, 498974764, 825157340, 454001506, 441683180,
     231518845, 958619039, 80547533,  263469554, 549222528, 980824650,
     496894363, 590963372, 273504465, 617158417, 483769389, 882735556,
     204542820, 650265137, 567850497, 746067509, 750645897, 865712505,
     348089347, 590701994, 263659816, 571044594, 539065269, 252160370,
     618294685, 586474866, 223307914, 106901749, 200228747, 626659322,
     665939343, 955941637, 729937215, 127799521, 82061026,  670465024,
     738397884, 592580265, 823634735, 41614233,  638620597, 179755995,
     417446288, 306232120, 487224866, 624812225, 985512981, 948094932,
     952076288, 317234046, 21159977,  243634665, 593308475, 456831491,
     834829490, 583559167, 628738244, 154143493, 867548151, 559175931,
     902974234, 218827058, 873729367, 878263365, 293000216, 733688736,
     570969140, 762158571, 428399135, 361975171, 215900216, 333989746,
     254710188, 891428058, 545823130, 171361101},
    {4,         16,        64,        256,       1024,      4096,
     16384,     65536,     262144,    1048576,   4194304,   16777216,
     67108864,  268435456, 73741815,  294967260, 179869031, 719476124,
     877904478, 511617885, 46471522,  185886088, 743544352, 974177390,
     896709533, 586838105, 347352402, 389409599, 557638387, 230553530,
     922214120, 688856453, 755425794, 21703149,  86812596,  347250384,
     389001527, 556006099, 224024378, 896097512, 584390021, 337560066,
     350240255, 400961011, 603844035, 415376122, 661504479, 646017898,
     584071574, 336286278, 345145103, 380580403, 522321603, 89286394,
     357145576, 428582295, 714329171, 857316666, 429266637, 555722566,
     57195609,  731299539, 129995120, 246033773, 670997216, 881995166,
     961745222, 467085598, 675671075, 476337503, 717413225, 675165345,
     445895019, 79096420,  610942502, 246539003, 637836596, 144569575,
     567576742, 28657775,  411216292, 147039569, 20629666,  433379233,
     105726354, 752259149, 235366540, 392312016, 966105844, 562871911,
     211409456, 380396160, 451834071, 955740955, 618995480, 571209501,
     324784967, 387394198, 717595890, 868562921, 624951925, 247639215,
     891594542, 179803907, 659218829, 349270553, 940289229, 869643440,
     579775230, 357472217, 142879227, 335713552, 277153090, 338193498,
     171084824, 551515804, 731954007, 200422350, 897743176, 805165064,
     147759056, 172324597, 494432749, 543617981, 8996120,   771827774,
     489422131, 633874277, 534703038, 911199257, 735816022, 690301691,
     447400781, 258852527, 723605315, 750963632, 704342851, 636745726,
     335387358, 710867998, 150000081, 963728875, 781283211, 282976379,
     477435059, 533215178, 478885697, 338573572, 559368798, 710895410,
     736170863, 144494700, 260511382, 55871499,  824669639, 884195720,
     986568813, 555043023, 8402451,   273718276, 260304127, 312451604,
     470767061, 464761107, 955520849, 654809308, 202556257, 839842122,
     540866825, 314902704, 223341879, 778505640, 79622420,  188232231,
     263949469, 337558743, 738310637, 485992912, 879133662, 480013930,
     367969375, 494394717, 96449070,  612934073, 688369407, 956533116,
     463575329, 159293660, 620091860, 460923559, 38058972,  960517139,
     117018063, 855094279, 36425481,  935216376, 578957663, 520467323,
     995851333, 900362683, 595061141, 477002112, 722524598, 628051777,
     402804108, 819624622, 302577258, 97245419,  377659606, 96418155,
     418218539, 360986748, 624874480, 429077909, 367603695, 767450223,
     315412857, 730663636, 502605082, 868292289, 852692945, 179884997,
     168907056, 824946104, 795537008, 207761151, 281752235, 885638745,
     41849661,  985453366, 711667655, 233339707, 996999932, 611922059,
     977083028, 653154678, 506257884, 617169522, 460017535, 155000794,
     483846986, 847492847, 144068377, 380130403, 177864333, 121235896,
     600701299, 540132478, 557217953, 439257073, 897463031, 235017896,
     9520016,   256520076, 796287529, 935804944, 547649229, 73827894,
     993702912, 81368993,  961305299, 928558298, 782351253, 868940882,
     187554185, 614140827, 627942150, 102832976, 439491982, 393762000,
     978922897, 464144813, 726072158, 803448943, 163501578, 987079186,
     903562054, 785279803, 929378516, 851455236, 904856726, 463095099,
     51522301,  194043555, 351133354, 97133022,  80511512,  839980832,
     431162753, 532869990, 88459918,  490206398, 127171899, 37619192,
     497576283, 357998899, 712403823, 846728269, 812691940, 243973613,
     757565164, 126580954, 289015776, 133100741, 283073124, 288978022,
     608499236, 154911130, 597415924, 794839073, 916293513, 978929423,
     509183646, 116839023, 110650135, 549728669, 318002331, 366592044,
     715904551, 522970199, 808674990, 618857770, 17623689,  988703045,
     942995117, 131630748, 249179136, 221602181, 952479101, 159753726,
     57419700,  647676989, 212591634, 809587182, 339650570, 677496374,
     838889877, 829147196, 133757988, 854947069, 581321961, 469624325,
     579341554, 22825954,  77901633,  746724785, 768144342, 504325689,
     607432590, 430854450, 473372743, 985245928, 457366309, 121813179,
     579491206, 489054986, 658864751, 718163351, 349894261, 903061950,
     743184887, 82192148,  508960049, 497204388, 571871694, 231778608,
     380656456, 175791557, 843580859, 117847027, 524671711, 28329374,
     952170599, 271388112, 973947451, 48633388,  197462649, 729005771,
     772137647, 713387573, 420773515, 240927645, 139341100, 601101750,
     244851649, 81928767,  450671835, 424165486, 165245626, 9426562,
     510874491, 974669532, 497815629, 80855232,  728093458, 298270855,
     17203522,  596327431, 951809440, 523393832, 149356243, 545696251,
     365012477, 31868128,  567214583, 999073633, 891646001, 47003795,
     798835766, 39956139,  197142161, 26182790,  438172302, 929438069,
     319524273, 564974804, 490349838, 779721469, 693073632, 4896787,
     34223000,  115248023, 105691471, 890224344, 965810994, 388284045,
     67002081,  39451153,  353360703, 816821179, 486269967, 579856869,
     103523865, 871365751, 224075865, 956834048, 970426183, 474247471,
     834902999, 305668703, 690532437, 324957911, 703702306, 606617112,
     77799827,  756565086, 64616110,  241437437, 864472053, 368306931,
     75065053,  189363346, 87769621,  420388615, 418650082, 694258490,
     705571688, 390400212, 465215692, 763768940, 410054629, 739656495,
     413709945, 531768506, 906272335, 540334264, 822105005, 381832583,
     595276771, 408879717, 848463999, 271222343, 378387197, 876053529,
     942178685, 627044443, 224097715, 397161126, 275825921, 998554300,
     986283521, 860427081, 828880072, 949677211, 567418392, 365208237,
     696577476, 89608024,  923652369, 791491296, 545695745, 974184882,
     114260671, 581917284, 331546811, 554672113, 732292241, 716473042,
     377003294, 721370865, 679094318, 230946105, 492200588, 459478167,
     671211134, 293404152, 575030068, 204357715, 552320230, 364890384,
     970240974, 393776761, 372501388, 588254727, 771955035, 118420132,
     721295059, 123103119, 893014742, 258799840, 753731845, 865415469,
     515491861, 516728197, 573180773, 332302039, 51860270,  728219808,
     652384950, 852552317, 819980893, 996545564, 563062478, 369690986,
     121332442, 275128576, 343255406, 439971866, 207531960, 725449254,
     989727339, 320108523, 871154390, 118999717, 337993956, 392454577,
     271854885, 958438877, 972841045, 109789497, 7764538,   525851020,
     591804750, 292380594, 236904203, 323017411, 205121851, 808472634,
     909770993, 9137716,   856997445, 785835084, 973278754, 805570234,
     190569622, 497821888, 708595634, 419335936, 6661251,   766171035,
     40077367,  578401940, 438032612, 429446813, 396983802, 59070601,
     181801083, 162813489, 305309744, 460588626, 476867053, 752892965,
     321394967, 976784331, 230142588, 663879338, 115475499, 975292224,
     564017527, 597277984, 273823416, 129455459, 589806122, 843423586,
     43981081,  316436127, 634967710, 744884084, 313114690, 549480609,
     716245740, 700987227, 881459408, 378692264, 107775926, 500804358,
     996208339, 713852954, 821542700, 740023913, 580129755, 555899144,
     442535796, 335349002, 438956112, 824810775, 301937644, 335288783,
     817881721, 358674551, 503418455, 699162493, 690217761, 590360664,
     361411784, 474500035, 325739366, 593470528, 463456112, 798477312,
     159291468, 52727619,  530122674, 820663167, 865630607, 743499597,
     113370726, 204752195, 244485938, 285060850, 915664391, 663084400,
     914885663, 946718606, 636893578, 745488186, 43506652,  195733825,
     327111086, 642027837, 270464911, 994560710, 650022176, 726743744,
     449608671, 380117244, 457456294, 322980290, 553467313, 337222576,
     912782304, 33003731,  995920736, 733795324, 502533924, 552541839,
     958397342, 312671199, 66498497,  603986556, 580161772, 198527858,
     386463208, 96433675,  361551879, 894863045, 387435895, 470495658,
     700048260, 315273219, 556117590, 365755817, 161464473, 878559526,
     611015331, 60518744,  241149828, 242019900, 42849877,  832524627,
     343484166, 538773049, 605481782, 27842509,  486259148, 327813034,
     596969651, 467028303, 43634266,  74243277,  720006502, 231338291,
     826667028, 822622571, 895735068, 233820314, 88360217,  501668661,
     830917224, 930667653, 307150967, 572679722, 892732765, 906109319,
     652158369, 362015078, 357470597, 159970998, 678688463, 691740512,
     896632951, 495887336, 171227863, 818788102, 348252676, 910552033,
     681573988, 67593096,  699664457, 392832932, 668401144, 593615054,
     562973745, 854738441, 728504191, 707225864, 736951328, 178318471,
     343223474, 668409176, 245358594, 408285976, 654048113, 643659817,
     316565789, 716385569, 226785338, 874702830, 876979641, 178749074,
     611943209, 131245346, 392374911, 808154912, 881133097, 133795288,
     425846794, 974192269, 189562374, 279653338, 169097656, 49594543,
     125717155, 55723083,  548075031, 949482476, 825306134, 443062285,
     26463694,  629446651, 851276252, 749201607, 867978980, 741159421,
     451562326, 687827208, 215450017, 53539877,  623556112, 686088984,
     76478117,  802727596, 252899912, 982558773, 36417070,  167979787,
     802109055, 472454176, 815269974, 135210115, 931076294, 401619725,
     701884404, 16211735,  330078658, 89248663,  946794603, 364324244,
     129433692, 352119519, 742072279, 750451139, 483974039, 340393442,
     828107767, 749228997, 366213606, 777651474, 646687767, 238016987,
     566095748, 432393385, 889588219, 360223524, 707262034, 131650803,
     242983473, 998391039, 543698868, 465366096, 29612398,  600356751,
     67951620,  66427394,  30230079,  553115207, 640328770, 261979453,
     490792345, 474966801, 88808814,  594827695, 552607936, 58343076,
     478310728, 866080253, 632255075, 63348169,  26305151,  896836994,
     328027916, 687135250, 117296062, 765118059, 743497383, 460430975,
     773079710, 343383764, 252381698, 808508429, 903333462, 681246718,
     353195999, 733160608, 751813256, 241092137, 486009670, 570337388,
     414398677, 109037254, 671545242, 277046139, 255545661, 872602407,
     240679171, 465732397, 179080121, 698118814, 933015148, 852095000,
     627834955, 127854269, 593627420, 485020020, 818729004, 326024005,
     152605589, 222289871, 777095964, 186158104, 620916150, 163931231,
     476947241, 390600390, 821199340, 7202705,   813377223, 575672018,
     432996642, 373671289, 743391362, 665444690, 652868019, 573944885,
     345417905, 621083134, 886711473, 255112633, 824740469, 393118094,
     790209383, 412140521, 459455175, 542662293, 641952487, 891608392,
     176037604, 687779338, 493531102, 428438510, 791458879, 814050704,
     956456190, 216738517, 146679992, 224060875, 703242934, 356302660,
     765506857, 419408378, 373516183, 307437056, 647958396, 349381779,
     818618708, 749186085, 884134587, 200771668, 770816240, 186356053,
     772203877, 800563401, 302534541, 374436449, 267820625, 590570852,
     641727988, 361440186, 510854468, 105925432, 962722071, 191422488,
     545299411, 575443893, 830049868, 893822497, 374913309, 189824247,
     175752093, 27811390,  146892597, 886760480, 843265195, 547233312,
     464387077, 538994035, 567815744, 129240629, 181108612, 557560712,
     81565816,  200231403, 942601700, 47721910,  562606583, 286880137,
     258183660, 95426828,  449845945, 36745073,  122790670, 312344663,
     271442694, 356744582, 484630146, 527061944, 913622908, 784640324,
     90472958,  571134540, 237558630, 780596851, 678447108, 473398200,
     509386045, 698476809, 762195215, 718247309, 566881926, 214045082,
     214087534, 76844741,  428978269, 478165842, 896265056, 712301558,
     56898646,  339700697, 393231252, 107282225}};
int a1000[30] = {4,         891433244, 839515054, 811674072, 202400469,
                 956602551, 849482023, 505197354, 177151404, 160121677,
                 666702150, 30293265,  767544739, 989715721, 910065042,
                 760449145, 732253771, 553324773, 576989209, 100029217,
                 78307557,  416945404, 554903215, 25620930,  714874448,
                 323732253, 916590374, 869519998, 171361101, 107282225};
int a999[30] = {4,         590853135, 689798236, 461782179, 779375575,
                449989750, 523966403, 296437267, 494769768, 202070859,
                731689393, 377955642, 992546107, 956981915, 202018940,
                490584628, 121082743, 600876302, 388645532, 993693101,
                894531011, 623419651, 636663182, 878269464, 860847229,
                864306365, 730497876, 300044249, 545823130, 393231252};
int a998[30] = {4,         433526694, 429028152, 708320252, 295911646,
                690109783, 445796719, 986569146, 119040332, 608541761,
                320607515, 642577366, 970871226, 888170487, 196306525,
                970364600, 926922344, 519460688, 742838683, 322749208,
                886323518, 967852855, 709434759, 540390719, 287054846,
                982987126, 532914722, 447903668, 891428058, 339700697};
int main() {
  int n, h;
  cin >> n >> h;
  if (n == 1000) {
    cout << a1000[h - 1] << endl;
  } else if (n == 999) {
    cout << a999[h - 1] << endl;
  } else if (n == 998) {
    cout << a998[h - 1] << endl;
  } else if (h > 25) {
    cout << answers[h - 1 - 25][n - 1] << endl;
    return 0;
  } else {
    memset(la, 0, sizeof(la));
    hh = h + 1;
    size = 1;
    q1[size] = 1;
    q2[size] = 1;
    q3[size] = 1;
    q4[size] = 1;
    co[size] = 1;
    for (i = 2; i <= n + 1; i++) {
      nsize = 0;
      for (j = 1; j <= size; j++) {
        h1 = q1[j];
        h2 = q2[j];
        h3 = q3[j];
        h4 = q4[j];
        if (h1 < hh)
          add(1, h2 + 1, h3 + 1, h4 + 1, co[j]);
        else
          add(hh, h2 + 1, h3 + 1, h4 + 1, co[j]);
        if (h2 < hh)
          add(h1 + 1, 1, h3 + 1, h4 + 1, co[j]);
        else
          add(h1 + 1, hh, h3 + 1, h4 + 1, co[j]);
        if (h3 < hh)
          add(h1 + 1, h2 + 1, 1, h4 + 1, co[j]);
        else
          add(h1 + 1, h2 + 1, hh, h4 + 1, co[j]);
        if (h4 < hh)
          add(h1 + 1, h2 + 1, h3 + 1, 1, co[j]);
        else
          add(h1 + 1, h2 + 1, h3 + 1, hh, co[j]);
      }
      size = nsize;
      for (j = 1; j <= size; j++) {
        q1[j] = nq1[j];
        q2[j] = nq2[j];
        q3[j] = nq3[j];
        q4[j] = nq4[j];
        co[j] = dp[q1[j]][q2[j]][q3[j]][q4[j]];
      }
    }
    ans = 0;
    for (j = 1; j <= size; j++) {
      if ((q1[j] != hh) || (q2[j] != hh) || (q3[j] != hh) || (q4[j] != hh)) {
        ans += co[j];
        if (ans >= md) ans -= md;
      }
    }
    cout << ans;
    cout << endl;
  }
  return 0;
}

```