granar = [671, 13302, 323550232, 3651148477325, 3252535203032, 342341201, 61355611350, 13311322002, 33121543422, 264, 444550111, 42245612442, 2222212100000, 63432754341, 297, 512451340, 21211211010, 4342147365343, 11100, 221330211, 2261236345044, 1121212101011, 111110000, 231, 2331113222001, 143, 6159483, 7199082, 59371982604, 221330211, 473, 5335220, 11322, 442341200, 231, 1111111000000, 2344334110012, 34633633023, 641264520, 12212201001, 544451110, 5215430, 1122333001122, 1111000, 165, 43410, 286, 253, 431341310, 4416522, 131297868, 2123121, 110, 2425313, 21213302121, 2526414, 57813, 43632, 21143521443, 2122010, 254352103, 77565832311, 495, 1122112110011, 165, 4225331, 2133333000021, 21210, 616484272, 41874, 352, 671, 54152530410, 224660244, 15414514104, 495, 4241214323020, 23301, 5535335220200, 21543, 7814649535812, 2576577021025, 122121001, 31224402231, 14433411003, 96930, 121220101, 1111111000000, 32310, 11211, 3455012, 75720, 3216349563876, 5332345123220, 44400, 2279277, 11211, 12221210001, 32643, 11111100000, 1221133022112, 48851873004, 451, 66822, 363, 1333002, 11100, 275, 72972, 22200, 983594610, 35415504102, 565385323, 297, 1111111000000, 561, 111110000, 231, 34512, 1111111000000, 1111000, 12212201001, 2743417634305, 7852289177412, 23412423012, 25614, 3341434103011, 3233234121121, 2315423, 75574841331, 198297108, 5225545100330, 3244021, 231, 1125545100344, 220, 3443255032112, 5115446221551, 3212113221210, 2236344, 2314312, 11211, 2133113220021, 21654, 51553631151, 4311324213310, 23122533423, 550, 12423, 65752974243, 111121111, 121, 111110000, 22313302011, 11100, 3431244023101, 1111111000000, 11322, 332143211, 41430, 220, 415473263, 165, 11211, 45632643012, 4417633, 111110000, 264, 1111111000000, 375385315, 312330120, 13141652535, 211220110, 121, 45945, 1321123122102, 114341033, 222121000, 220, 331341311, 1111000, 792, 11111100000, 3144144030031, 242, 1111000, 3333000, 1313133020202, 45501, 122165445, 65943, 22223412222, 660, 222121000, 22200, 3444001, 231132201, 1111111000000, 111110000, 63411655230, 5776637411002, 9699030, 23232643434, 113132022, 75511766220, 77922, 44400, 110, 6768212, 6388052, 9464219875350, 231440312, 22143410322, 2133021, 14403, 682, 51651, 232253323, 122220001, 175374206, 33411, 231, 52530, 3321113222100, 341, 880, 4251316535142, 341, 241143302, 634990563, 51214514340, 6168272, 17587810317, 6721228667612, 73181870751, 425484364, 4422314312200, 956297340, 33411, 2235233, 25514514003, 1111111000000, 6123617614561, 4122244022230, 714880471, 2224222, 165, 1334113, 23131320201, 111110000, 21210, 4355021, 31222311120, 47703, 3487728611045, 111110000, 2558336, 11111100000, 187, 14514, 110, 22755, 252253303, 3133323100020, 62535613140, 143, 8748659431521, 11100, 682, 672396723, 14514, 244550113, 17551984428, 1221113222112, 121, 770, 143, 13332421113, 5247352, 4121455014341, 78912, 96225947730, 121, 594, 21210, 1112111, 2222000, 1525415410304, 335451022, 253, 11111100000, 211220110, 122143223, 781, 110, 25245501303, 143, 2155043, 26663630004, 2468246, 44646602022, 22200, 4114330, 792, 12144400323, 44400, 3425312, 222220000, 6177061, 8936569343601, 3236343, 660, 3456123, 15515615115, 25543965447, 156396348, 110, 5163577024162, 671176601, 4146626400252, 54722, 11100, 12132310212, 41541, 77542753200, 671, 111451444, 335385355, 1111111000000, 346583245, 7314668224751, 3229776, 63630, 110, 7325517622540, 512451340, 11111100000, 55500, 11111100000, 5156151, 11111100000, 5636301, 36454954536, 4145141, 6257517620251, 286, 63236603430, 253, 792, 74511766230, 21210, 332231100, 1111000, 4767377040103, 12201, 990, 440, 3737404, 14255500314, 4424415411311, 232341212, 4242535203131, 111220111, 179495028, 23121321201, 11111100000, 53624624031, 110, 385, 111110000, 21222200010, 41263741563, 75720, 23301, 5226441, 22211211000, 7819812, 110, 224440022, 4434100, 26937, 2122212100010, 242, 561, 11100, 11111100000, 651275621, 31253853675, 34231875645, 42864, 330, 13302, 657891243, 143, 58725947214, 31313413131, 1111000, 111682777, 1221122011001, 3466023]