#include <iostream>
#include <algorithm>
using namespace std;
#include <math.h>
#include <memory.h>

int ans[2000][2000] = {
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,


1,3,4,6,7,9,10,12,13,15,16,18,19,21,22,24,
25,27,28,30,31,33,34,36,37,39,40,42,43,45,46,48,
49,51,52,54,55,57,58,60,61,63,64,66,67,69,70,72,
73,75,76,78,79,81,82,84,85,87,88,90,91,93,94,96,
97,99,100,102,103,105,106,108,109,111,112,114,115,117,118,120,
121,123,124,126,127,129,130,132,133,135,136,138,139,141,142,144,
145,147,148,150,151,153,154,156,157,159,160,162,163,165,166,168,
169,171,172,174,175,177,178,180,181,183,184,186,187,189,190,192,
193,195,196,198,199,201,202,204,205,207,208,210,211,213,214,216,
217,219,220,222,223,225,226,228,229,231,232,234,235,237,238,240,
241,243,244,246,247,249,250,252,253,255,256,258,259,261,262,264,
265,267,268,270,271,273,274,276,277,279,280,282,283,285,286,288,
289,291,292,294,295,297,298,300,301,303,304,306,307,309,310,312,
313,315,316,318,319,321,322,324,325,327,328,330,331,333,334,336,
337,339,340,342,343,345,346,348,349,351,352,354,355,357,358,360,
361,363,364,366,367,369,370,372,373,375,376,378,379,381,382,384,
385,387,388,390,391,393,394,396,397,399,400,402,403,405,406,408,
409,411,412,414,415,417,418,420,421,423,424,426,427,429,430,432,
433,435,436,438,439,441,442,444,445,447,448,450,451,453,454,456,
457,459,460,462,463,465,466,468,469,471,472,474,475,477,478,480,
481,483,484,486,487,489,490,492,493,495,496,498,499,501,502,504,
505,507,508,510,511,513,514,516,517,519,520,522,523,525,526,528,
529,531,532,534,535,537,538,540,541,543,544,546,547,549,550,552,
553,555,556,558,559,561,562,564,565,567,568,570,571,573,574,576,
577,579,580,582,583,585,586,588,589,591,592,594,595,597,598,600,
601,603,604,606,607,609,610,612,613,615,616,618,619,621,622,624,
625,627,628,630,631,633,634,636,637,639,640,642,643,645,646,648,
649,651,652,654,655,657,658,660,661,663,664,666,667,669,670,672,
673,675,676,678,679,681,682,684,685,687,688,690,691,693,694,696,
697,699,700,702,703,705,706,708,709,711,712,714,715,717,718,720,
721,723,724,726,727,729,730,732,733,735,736,738,739,741,742,744,
745,747,748,750,751,753,754,756,757,759,760,762,763,765,766,768,
769,771,772,774,775,777,778,780,781,783,784,786,787,789,790,792,
793,795,796,798,799,801,802,804,805,807,808,810,811,813,814,816,
817,819,820,822,823,825,826,828,829,831,832,834,835,837,838,840,
841,843,844,846,847,849,850,852,853,855,856,858,859,861,862,864,
865,867,868,870,871,873,874,876,877,879,880,882,883,885,886,888,
889,891,892,894,895,897,898,900,901,903,904,906,907,909,910,912,
913,915,916,918,919,921,922,924,925,927,928,930,931,933,934,936,
937,939,940,942,943,945,946,948,949,951,952,954,955,957,958,960,
961,963,964,966,967,969,970,972,973,975,976,978,979,981,982,984,
985,987,988,990,991,993,994,996,997,999,1000,1002,1003,1005,1006,1008,
1009,1011,1012,1014,1015,1017,1018,1020,1021,1023,1024,1026,1027,1029,1030,1032,
1033,1035,1036,1038,1039,1041,1042,1044,1045,1047,1048,1050,1051,1053,1054,1056,
1057,1059,1060,1062,1063,1065,1066,1068,1069,1071,1072,1074,1075,1077,1078,1080,
1081,1083,1084,1086,1087,1089,1090,1092,1093,1095,1096,1098,1099,1101,1102,1104,
1105,1107,1108,1110,1111,1113,1114,1116,1117,1119,1120,1122,1123,1125,1126,1128,
1129,1131,1132,1134,1135,1137,1138,1140,1141,1143,1144,1146,1147,1149,1150,1152,
1153,1155,1156,1158,1159,1161,1162,1164,1165,1167,1168,1170,1171,1173,1174,1176,
1177,1179,1180,1182,1183,1185,1186,1188,1189,1191,1192,1194,1195,1197,1198,1200,
1201,1203,1204,1206,1207,1209,1210,1212,1213,1215,1216,1218,1219,1221,1222,1224,
1225,1227,1228,1230,1231,1233,1234,1236,1237,1239,1240,1242,1243,1245,1246,1248,
1249,1251,1252,1254,1255,1257,1258,1260,1261,1263,1264,1266,1267,1269,1270,1272,
1273,1275,1276,1278,1279,1281,1282,1284,1285,1287,1288,1290,1291,1293,1294,1296,
1297,1299,1300,1302,1303,1305,1306,1308,1309,1311,1312,1314,1315,1317,1318,1320,
1321,1323,1324,1326,1327,1329,1330,1332,1333,1335,1336,1338,1339,1341,1342,1344,
1345,1347,1348,1350,1351,1353,1354,1356,1357,1359,1360,1362,1363,1365,1366,1368,
1369,1371,1372,1374,1375,1377,1378,1380,1381,1383,1384,1386,1387,1389,1390,1392,
1393,1395,1396,1398,1399,1401,1402,1404,1405,1407,1408,1410,1411,1413,1414,1416,
1417,1419,1420,1422,1423,1425,1426,1428,1429,1431,1432,1434,1435,1437,1438,1440,
1441,1443,1444,1446,1447,1449,1450,1452,1453,1455,1456,1458,1459,1461,1462,1464,
1465,1467,1468,1470,1471,1473,1474,1476,1477,1479,1480,1482,1483,1485,1486,1488,
1489,1491,1492,1494,1495,1497,1498,1500,1501,1503,1504,1506,1507,1509,1510,1512,
1513,1515,1516,1518,1519,1521,1522,1524,1525,1527,1528,1530,1531,1533,1534,1536,
1537,1539,1540,1542,1543,1545,1546,1548,1549,1551,1552,1554,1555,1557,1558,1560,
1561,1563,1564,1566,1567,1569,1570,1572,1573,1575,1576,1578,1579,1581,1582,1584,
1585,1587,1588,1590,1591,1593,1594,1596,1597,1599,1600,1602,1603,1605,1606,1608,
1609,1611,1612,1614,1615,1617,1618,1620,1621,1623,1624,1626,1627,1629,1630,1632,
1633,1635,1636,1638,1639,1641,1642,1644,1645,1647,1648,1650,1651,1653,1654,1656,
1657,1659,1660,1662,1663,1665,1666,1668,1669,1671,1672,1674,1675,1677,1678,1680,
1681,1683,1684,1686,1687,1689,1690,1692,1693,1695,1696,1698,1699,1701,1702,1704,
1705,1707,1708,1710,1711,1713,1714,1716,1717,1719,1720,1722,1723,1725,1726,1728,
1729,1731,1732,1734,1735,1737,1738,1740,1741,1743,1744,1746,1747,1749,1750,1752,
1753,1755,1756,1758,1759,1761,1762,1764,1765,1767,1768,1770,1771,1773,1774,1776,
1777,1779,1780,1782,1783,1785,1786,1788,1789,1791,1792,1794,1795,1797,1798,1800,
1801,1803,1804,1806,1807,1809,1810,1812,1813,1815,1816,1818,1819,1821,1822,1824,
1825,1827,1828,1830,1831,1833,1834,1836,1837,1839,1840,1842,1843,1845,1846,1848,
1849,1851,1852,1854,1855,1857,1858,1860,1861,1863,1864,1866,1867,1869,1870,1872,
1873,1875,1876,1878,1879,1881,1882,1884,1885,1887,1888,1890,1891,1893,1894,1896,
1897,1899,1900,1902,1903,1905,1906,1908,1909,1911,1912,1914,1915,1917,1918,1920,
1921,1923,1924,1926,1927,1929,1930,1932,1933,1935,1936,1938,1939,1941,1942,1944,
1945,1947,1948,1950,1951,1953,1954,1956,1957,1959,1960,1962,1963,1965,1966,1968,
1969,1971,1972,1974,1975,1977,1978,1980,1981,1983,1984,1986,1987,1989,1990,1992,
1993,1995,1996,1998,1999,2001,2002,2004,2005,2007,2008,2010,2011,2013,2014,2016,
2017,2019,2020,2022,2023,2025,2026,2028,2029,2031,2032,2034,2035,2037,2038,2040,
2041,2043,2044,2046,2047,2049,2050,2052,2053,2055,2056,2058,2059,2061,2062,2064,
2065,2067,2068,2070,2071,2073,2074,2076,2077,2079,2080,2082,2083,2085,2086,2088,
2089,2091,2092,2094,2095,2097,2098,2100,2101,2103,2104,2106,2107,2109,2110,2112,
2113,2115,2116,2118,2119,2121,2122,2124,2125,2127,2128,2130,2131,2133,2134,2136,
2137,2139,2140,2142,2143,2145,2146,2148,2149,2151,2152,2154,2155,2157,2158,2160,
2161,2163,2164,2166,2167,2169,2170,2172,2173,2175,2176,2178,2179,2181,2182,2184,
2185,2187,2188,2190,2191,2193,2194,2196,2197,2199,2200,2202,2203,2205,2206,2208,
2209,2211,2212,2214,2215,2217,2218,2220,2221,2223,2224,2226,2227,2229,2230,2232,
2233,2235,2236,2238,2239,2241,2242,2244,2245,2247,2248,2250,2251,2253,2254,2256,
2257,2259,2260,2262,2263,2265,2266,2268,2269,2271,2272,2274,2275,2277,2278,2280,
2281,2283,2284,2286,2287,2289,2290,2292,2293,2295,2296,2298,2299,2301,2302,2304,
2305,2307,2308,2310,2311,2313,2314,2316,2317,2319,2320,2322,2323,2325,2326,2328,
2329,2331,2332,2334,2335,2337,2338,2340,2341,2343,2344,2346,2347,2349,2350,2352,
2353,2355,2356,2358,2359,2361,2362,2364,2365,2367,2368,2370,2371,2373,2374,2376,
2377,2379,2380,2382,2383,2385,2386,2388,2389,2391,2392,2394,2395,2397,2398,2400,
2401,2403,2404,2406,2407,2409,2410,2412,2413,2415,2416,2418,2419,2421,2422,2424,
2425,2427,2428,2430,2431,2433,2434,2436,2437,2439,2440,2442,2443,2445,2446,2448,
2449,2451,2452,2454,2455,2457,2458,2460,2461,2463,2464,2466,2467,2469,2470,2472,
2473,2475,2476,2478,2479,2481,2482,2484,2485,2487,2488,2490,2491,2493,2494,2496,
2497,2499,2500,2502,2503,2505,2506,2508,2509,2511,2512,2514,2515,2517,2518,2520,
2521,2523,2524,2526,2527,2529,2530,2532,2533,2535,2536,2538,2539,2541,2542,2544,
2545,2547,2548,2550,2551,2553,2554,2556,2557,2559,2560,2562,2563,2565,2566,2568,
2569,2571,2572,2574,2575,2577,2578,2580,2581,2583,2584,2586,2587,2589,2590,2592,
2593,2595,2596,2598,2599,2601,2602,2604,2605,2607,2608,2610,2611,2613,2614,2616,
2617,2619,2620,2622,2623,2625,2626,2628,2629,2631,2632,2634,2635,2637,2638,2640,
2641,2643,2644,2646,2647,2649,2650,2652,2653,2655,2656,2658,2659,2661,2662,2664,
2665,2667,2668,2670,2671,2673,2674,2676,2677,2679,2680,2682,2683,2685,2686,2688,
2689,2691,2692,2694,2695,2697,2698,2700,2701,2703,2704,2706,2707,2709,2710,2712,
2713,2715,2716,2718,2719,2721,2722,2724,2725,2727,2728,2730,2731,2733,2734,2736,
2737,2739,2740,2742,2743,2745,2746,2748,2749,2751,2752,2754,2755,2757,2758,2760,
2761,2763,2764,2766,2767,2769,2770,2772,2773,2775,2776,2778,2779,2781,2782,2784,
2785,2787,2788,2790,2791,2793,2794,2796,2797,2799,2800,2802,2803,2805,2806,2808,
2809,2811,2812,2814,2815,2817,2818,2820,2821,2823,2824,2826,2827,2829,2830,2832,
2833,2835,2836,2838,2839,2841,2842,2844,2845,2847,2848,2850,2851,2853,2854,2856,
2857,2859,2860,2862,2863,2865,2866,2868,2869,2871,2872,2874,2875,2877,2878,2880,
2881,2883,2884,2886,2887,2889,2890,2892,2893,2895,2896,2898,2899,2901,2902,2904,
2905,2907,2908,2910,2911,2913,2914,2916,2917,2919,2920,2922,2923,2925,2926,2928,
2929,2931,2932,2934,2935,2937,2938,2940,2941,2943,2944,2946,2947,2949,2950,2952,
2953,2955,2956,2958,2959,2961,2962,2964,2965,2967,2968,2970,2971,2973,2974,2976,
2977,2979,2980,2982,2983,2985,2986,2988,2989,2991,2992,2994,2995,2997,2998,3000,


1,5,10,18,26,39,50,67,82,103,121,147,168,198,223,257,
285,324,355,398,433,480,518,570,611,667,712,772,820,885,936,1005,
1060,1133,1191,1269,1330,1412,1477,1563,1631,1722,1793,1888,1963,2062,2140,2244,
2325,2433,2518,2630,2718,2835,2926,3047,3142,3267,3365,3495,3596,3730,3835,3973,
4081,4224,4335,4482,4597,4748,4866,5022,5143,5303,5428,5592,5720,5889,6020,6193,
6328,6505,6643,6825,6966,7152,7297,7487,7635,7830,7981,8180,8335,8538,8696,8904,
9065,9277,9442,9658,9826,10047,10218,10443,10618,10847,11025,11259,11440,11678,11863,12105,
12293,12540,12731,12982,13177,13432,13630,13890,14091,14355,14560,14828,15036,15309,15520,15797,
16012,16293,16511,16797,17018,17308,17533,17827,18055,18354,18585,18888,19123,19430,19668,19980,
20221,20537,20782,21102,21350,21675,21926,22255,22510,22843,23101,23439,23700,24042,24307,24653,
24921,25272,25543,25898,26173,26532,26810,27174,27455,27823,28108,28480,28768,29145,29436,29817,
30112,30497,30795,31185,31486,31880,32185,32583,32891,33294,33605,34012,34327,34738,35056,35472,
35793,36213,36538,36962,37290,37719,38050,38483,38818,39255,39593,40035,40376,40822,41167,41617,
41965,42420,42771,43230,43585,44048,44406,44874,45235,45707,46072,46548,46916,47397,47768,48253,
48628,49117,49495,49989,50370,50868,51253,51755,52143,52650,53041,53552,53947,54462,54860,55380,
55781,56305,56710,57238,57646,58179,58590,59127,59542,60083,60501,61047,61468,62018,62443,62997,
63425,63984,64415,64978,65413,65980,66418,66990,67431,68007,68452,69032,69480,70065,70516,71105,
71560,72153,72611,73209,73670,74272,74737,75343,75811,76422,76893,77508,77983,78602,79080,79704,
80185,80813,81298,81930,82418,83055,83546,84187,84682,85327,85825,86475,86976,87630,88135,88793,
89301,89964,90475,91142,91657,92328,92846,93522,94043,94723,95248,95932,96460,97149,97680,98373,
98908,99605,100143,100845,101386,102092,102637,103347,103895,104610,105161,105880,106435,107158,107716,108444,
109005,109737,110302,111038,111606,112347,112918,113663,114238,114987,115565,116319,116900,117658,118243,119005,
119593,120360,120951,121722,122317,123092,123690,124470,125071,125855,126460,127248,127856,128649,129260,130057,
130672,131473,132091,132897,133518,134328,134953,135767,136395,137214,137845,138668,139303,140130,140768,141600,
142241,143077,143722,144562,145210,146055,146706,147555,148210,149063,149721,150579,151240,152102,152767,153633,
154301,155172,155843,156718,157393,158272,158950,159834,160515,161403,162088,162980,163668,164565,165256,166157,
166852,167757,168455,169365,170066,170980,171685,172603,173311,174234,174945,175872,176587,177518,178236,179172,
179893,180833,181558,182502,183230,184179,184910,185863,186598,187555,188293,189255,189996,190962,191707,192677,
193425,194400,195151,196130,196885,197868,198626,199614,200375,201367,202132,203128,203896,204897,205668,206673,
207448,208457,209235,210249,211030,212048,212833,213855,214643,215670,216461,217492,218287,219322,220120,221160,
221961,223005,223810,224858,225666,226719,227530,228587,229402,230463,231281,232347,233168,234238,235063,236137,
236965,238044,238875,239958,240793,241880,242718,243810,244651,245747,246592,247692,248540,249645,250496,251605,
252460,253573,254431,255549,256410,257532,258397,259523,260391,261522,262393,263528,264403,265542,266420,267564,
268445,269593,270478,271630,272518,273675,274566,275727,276622,277787,278685,279855,280756,281930,282835,284013,
284921,286104,287015,288202,289117,290308,291226,292422,293343,294543,295468,296672,297600,298809,299740,300953,
301888,303105,304043,305265,306206,307432,308377,309607,310555,311790,312741,313980,314935,316178,317136,318384,
319345,320597,321562,322818,323786,325047,326018,327283,328258,329527,330505,331779,332760,334038,335023,336305,
337293,338580,339571,340862,341857,343152,344150,345450,346451,347755,348760,350068,351076,352389,353400,354717,
355732,357053,358071,359397,360418,361748,362773,364107,365135,366474,367505,368848,369883,371230,372268,373620,
374661,376017,377062,378422,379470,380835,381886,383255,384310,385683,386741,388119,389180,390562,391627,393013,
394081,395472,396543,397938,399013,400412,401490,402894,403975,405383,406468,407880,408968,410385,411476,412897,
413992,415417,416515,417945,419046,420480,421585,423023,424131,425574,426685,428132,429247,430698,431816,433272,
434393,435853,436978,438442,439570,441039,442170,443643,444778,446255,447393,448875,450016,451502,452647,454137,
455285,456780,457931,459430,460585,462088,463246,464754,465915,467427,468592,470108,471276,472797,473968,475493,
476668,478197,479375,480909,482090,483628,484813,486355,487543,489090,490281,491832,493027,494582,495780,497340,
498541,500105,501310,502878,504086,505659,506870,508447,509662,511243,512461,514047,515268,516858,518083,519677,
520905,522504,523735,525338,526573,528180,529418,531030,532271,533887,535132,536752,538000,539625,540876,542505,
543760,545393,546651,548289,549550,551192,552457,554103,555371,557022,558293,559948,561223,562882,564160,565824,
567105,568773,570058,571730,573018,574695,575986,577667,578962,580647,581945,583635,584936,586630,587935,589633,
590941,592644,593955,595662,596977,598688,600006,601722,603043,604763,606088,607812,609140,610869,612200,613933,
615268,617005,618343,620085,621426,623172,624517,626267,627615,629370,630721,632480,633835,635598,636956,638724,
640085,641857,643222,644998,646366,648147,649518,651303,652678,654467,655845,657639,659020,660818,662203,664005,
665393,667200,668591,670402,671797,673612,675010,676830,678231,680055,681460,683288,684696,686529,687940,689777,
691192,693033,694451,696297,697718,699568,700993,702847,704275,706134,707565,709428,710863,712730,714168,716040,
717481,719357,720802,722682,724130,726015,727466,729355,730810,732703,734161,736059,737520,739422,740887,742793,
744261,746172,747643,749558,751033,752952,754430,756354,757835,759763,761248,763180,764668,766605,768096,770037,
771532,773477,774975,776925,778426,780380,781885,783843,785351,787314,788825,790792,792307,794278,795796,797772,
799293,801273,802798,804782,806310,808299,809830,811823,813358,815355,816893,818895,820436,822442,823987,825997,
827545,829560,831111,833130,834685,836708,838266,840294,841855,843887,845452,847488,849056,851097,852668,854713,
856288,858337,859915,861969,863550,865608,867193,869255,870843,872910,874501,876572,878167,880242,881840,883920,
885521,887605,889210,891298,892906,894999,896610,898707,900322,902423,904041,906147,907768,909878,911503,913617,
915245,917364,918995,921118,922753,924880,926518,928650,930291,932427,934072,936212,937860,940005,941656,943805,
945460,947613,949271,951429,953090,955252,956917,959083,960751,962922,964593,966768,968443,970622,972300,974484,
976165,978353,980038,982230,983918,986115,987806,990007,991702,993907,995605,997815,999516,1001730,1003435,1005653,
1007361,1009584,1011295,1013522,1015237,1017468,1019186,1021422,1023143,1025383,1027108,1029352,1031080,1033329,1035060,1037313,
1039048,1041305,1043043,1045305,1047046,1049312,1051057,1053327,1055075,1057350,1059101,1061380,1063135,1065418,1067176,1069464,
1071225,1073517,1075282,1077578,1079346,1081647,1083418,1085723,1087498,1089807,1091585,1093899,1095680,1097998,1099783,1102105,
1103893,1106220,1108011,1110342,1112137,1114472,1116270,1118610,1120411,1122755,1124560,1126908,1128716,1131069,1132880,1135237,
1137052,1139413,1141231,1143597,1145418,1147788,1149613,1151987,1153815,1156194,1158025,1160408,1162243,1164630,1166468,1168860,
1170701,1173097,1174942,1177342,1179190,1181595,1183446,1185855,1187710,1190123,1191981,1194399,1196260,1198682,1200547,1202973,
1204841,1207272,1209143,1211578,1213453,1215892,1217770,1220214,1222095,1224543,1226428,1228880,1230768,1233225,1235116,1237577,
1239472,1241937,1243835,1246305,1248206,1250680,1252585,1255063,1256971,1259454,1261365,1263852,1265767,1268258,1270176,1272672,
1274593,1277093,1279018,1281522,1283450,1285959,1287890,1290403,1292338,1294855,1296793,1299315,1301256,1303782,1305727,1308257,
1310205,1312740,1314691,1317230,1319185,1321728,1323686,1326234,1328195,1330747,1332712,1335268,1337236,1339797,1341768,1344333,
1346308,1348877,1350855,1353429,1355410,1357988,1359973,1362555,1364543,1367130,1369121,1371712,1373707,1376302,1378300,1380900,
1382901,1385505,1387510,1390118,1392126,1394739,1396750,1399367,1401382,1404003,1406021,1408647,1410668,1413298,1415323,1417957,
1419985,1422624,1424655,1427298,1429333,1431980,1434018,1436670,1438711,1441367,1443412,1446072,1448120,1450785,1452836,1455505,
1457560,1460233,1462291,1464969,1467030,1469712,1471777,1474463,1476531,1479222,1481293,1483988,1486063,1488762,1490840,1493544,
1495625,1498333,1500418,1503130,1505218,1507935,1510026,1512747,1514842,1517567,1519665,1522395,1524496,1527230,1529335,1532073,
1534181,1536924,1539035,1541782,1543897,1546648,1548766,1551522,1553643,1556403,1558528,1561292,1563420,1566189,1568320,1571093,
1573228,1576005,1578143,1580925,1583066,1585852,1587997,1590787,1592935,1595730,1597881,1600680,1602835,1605638,1607796,1610604,
1612765,1615577,1617742,1620558,1622726,1625547,1627718,1630543,1632718,1635547,1637725,1640559,1642740,1645578,1647763,1650605,
1652793,1655640,1657831,1660682,1662877,1665732,1667930,1670790,1672991,1675855,1678060,1680928,1683136,1686009,1688220,1691097,
1693312,1696193,1698411,1701297,1703518,1706408,1708633,1711527,1713755,1716654,1718885,1721788,1724023,1726930,1729168,1732080,
1734321,1737237,1739482,1742402,1744650,1747575,1749826,1752755,1755010,1757943,1760201,1763139,1765400,1768342,1770607,1773553,
1775821,1778772,1781043,1783998,1786273,1789232,1791510,1794474,1796755,1799723,1802008,1804980,1807268,1810245,1812536,1815517,
1817812,1820797,1823095,1826085,1828386,1831380,1833685,1836683,1838991,1841994,1844305,1847312,1849627,1852638,1854956,1857972,
1860293,1863313,1865638,1868662,1870990,1874019,1876350,1879383,1881718,1884755,1887093,1890135,1892476,1895522,1897867,1900917,
1903265,1906320,1908671,1911730,1914085,1917148,1919506,1922574,1924935,1928007,1930372,1933448,1935816,1938897,1941268,1944353,
1946728,1949817,1952195,1955289,1957670,1960768,1963153,1966255,1968643,1971750,1974141,1977252,1979647,1982762,1985160,1988280,
1990681,1993805,1996210,1999338,2001746,2004879,2007290,2010427,2012842,2015983,2018401,2021547,2023968,2027118,2029543,2032697,
2035125,2038284,2040715,2043878,2046313,2049480,2051918,2055090,2057531,2060707,2063152,2066332,2068780,2071965,2074416,2077605,
2080060,2083253,2085711,2088909,2091370,2094572,2097037,2100243,2102711,2105922,2108393,2111608,2114083,2117302,2119780,2123004,
2125485,2128713,2131198,2134430,2136918,2140155,2142646,2145887,2148382,2151627,2154125,2157375,2159876,2163130,2165635,2168893,
2171401,2174664,2177175,2180442,2182957,2186228,2188746,2192022,2194543,2197823,2200348,2203632,2206160,2209449,2211980,2215273,
2217808,2221105,2223643,2226945,2229486,2232792,2235337,2238647,2241195,2244510,2247061,2250380,2252935,2256258,2258816,2262144,
2264705,2268037,2270602,2273938,2276506,2279847,2282418,2285763,2288338,2291687,2294265,2297619,2300200,2303558,2306143,2309505,
2312093,2315460,2318051,2321422,2324017,2327392,2329990,2333370,2335971,2339355,2341960,2345348,2347956,2351349,2353960,2357357,
2359972,2363373,2365991,2369397,2372018,2375428,2378053,2381467,2384095,2387514,2390145,2393568,2396203,2399630,2402268,2405700,
2408341,2411777,2414422,2417862,2420510,2423955,2426606,2430055,2432710,2436163,2438821,2442279,2444940,2448402,2451067,2454533,
2457201,2460672,2463343,2466818,2469493,2472972,2475650,2479134,2481815,2485303,2487988,2491480,2494168,2497665,2500356,2503857,
2506552,2510057,2512755,2516265,2518966,2522480,2525185,2528703,2531411,2534934,2537645,2541172,2543887,2547418,2550136,2553672,
2556393,2559933,2562658,2566202,2568930,2572479,2575210,2578763,2581498,2585055,2587793,2591355,2594096,2597662,2600407,2603977,
2606725,2610300,2613051,2616630,2619385,2622968,2625726,2629314,2632075,2635667,2638432,2642028,2644796,2648397,2651168,2654773,
2657548,2661157,2663935,2667549,2670330,2673948,2676733,2680355,2683143,2686770,2689561,2693192,2695987,2699622,2702420,2706060,
2708861,2712505,2715310,2718958,2721766,2725419,2728230,2731887,2734702,2738363,2741181,2744847,2747668,2751338,2754163,2757837,
2760665,2764344,2767175,2770858,2773693,2777380,2780218,2783910,2786751,2790447,2793292,2796992,2799840,2803545,2806396,2810105,
2812960,2816673,2819531,2823249,2826110,2829832,2832697,2836423,2839291,2843022,2845893,2849628,2852503,2856242,2859120,2862864,
2865745,2869493,2872378,2876130,2879018,2882775,2885666,2889427,2892322,2896087,2898985,2902755,2905656,2909430,2912335,2916113,
2919021,2922804,2925715,2929502,2932417,2936208,2939126,2942922,2945843,2949643,2952568,2956372,2959300,2963109,2966040,2969853,
2972788,2976605,2979543,2983365,2986306,2990132,2993077,2996907,2999855,3003690,3006641,3010480,3013435,3017278,3020236,3024084,
3027045,3030897,3033862,3037718,3040686,3044547,3047518,3051383,3054358,3058227,3061205,3065079,3068060,3071938,3074923,3078805,
3081793,3085680,3088671,3092562,3095557,3099452,3102450,3106350,3109351,3113255,3116260,3120168,3123176,3127089,3130100,3134017,
3137032,3140953,3143971,3147897,3150918,3154848,3157873,3161807,3164835,3168774,3171805,3175748,3178783,3182730,3185768,3189720,
3192761,3196717,3199762,3203722,3206770,3210735,3213786,3217755,3220810,3224783,3227841,3231819,3234880,3238862,3241927,3245913,
3248981,3252972,3256043,3260038,3263113,3267112,3270190,3274194,3277275,3281283,3284368,3288380,3291468,3295485,3298576,3302597,
3305692,3309717,3312815,3316845,3319946,3323980,3327085,3331123,3334231,3338274,3341385,3345432,3348547,3352598,3355716,3359772,
3362893,3366953,3370078,3374142,3377270,3381339,3384470,3388543,3391678,3395755,3398893,3402975,3406116,3410202,3413347,3417437,
3420585,3424680,3427831,3431930,3435085,3439188,3442346,3446454,3449615,3453727,3456892,3461008,3464176,3468297,3471468,3475593,
3478768,3482897,3486075,3490209,3493390,3497528,3500713,3504855,3508043,3512190,3515381,3519532,3522727,3526882,3530080,3534240,
3537441,3541605,3544810,3548978,3552186,3556359,3559570,3563747,3566962,3571143,3574361,3578547,3581768,3585958,3589183,3593377,
3596605,3600804,3604035,3608238,3611473,3615680,3618918,3623130,3626371,3630587,3633832,3638052,3641300,3645525,3648776,3653005,
3656260,3660493,3663751,3667989,3671250,3675492,3678757,3683003,3686271,3690522,3693793,3698048,3701323,3705582,3708860,3713124,
3716405,3720673,3723958,3728230,3731518,3735795,3739086,3743367,3746662,3750947,3754245,3758535,3761836,3766130,3769435,3773733,
3777041,3781344,3784655,3788962,3792277,3796588,3799906,3804222,3807543,3811863,3815188,3819512,3822840,3827169,3830500,3834833,


1,7,19,41,70,119,174,257,349,475,609,792,976,1220,1468,1783,
2097,2498,2887,3377,3856,4444,5014,5718,6387,7207,7993,8939,9840,10931,11956,13191,
14359,15747,17055,18618,20074,21808,23434,25349,27139,29258,31221,33539,35698,38224,40572,43332,
45877,48863,51631,54853,57834,61319,64522,68261,71713,75715,79405,83700,87636,92212,96424,101291,
105765,110954,115699,121197,126244,132060,137394,143562,149191,155695,161653,168503,174772,182003,188592,196187,
203131,211099,218379,226758,234382,243152,251158,260329,268695,278306,287041,297071,306214,316672,326200,337128,
347049,358423,368779,380609,391374,403703,414886,427689,439333,452619,464697,478512,491032,505348,518356,533183,
546649,562034,575967,591881,606328,622780,637710,654750,670171,687767,703729,721891,738360,757139,774124,793487,
811039,830995,849079,869682,888306,909520,928738,950573,970347,992858,1013197,1036347,1057306,1081104,1102644,1127148,
1149277,1174447,1197223,1223069,1246450,1273031,1297026,1324301,1348969,1376947,1402245,1430988,1456924,1486388,1513024,1543219,
1570509,1601498,1629451,1661189,1689868,1722364,1751722,1785042,1815087,1849183,1879981,1914863,1946364,1982099,2014312,2050851,
2083843,2121195,2154915,2193150,2227606,2266672,2301934,2341841,2377855,2418674,2455449,2497127,2534734,2577280,2615664,2659152,
2698321,2742695,2782723,2827993,2868822,2915063,2956702,3003857,3046381,3094459,3137809,3186888,3231072,3281092,3326188,3377159,
3423105,3475106,3521911,3574881,3622624,3676572,3725190,3780198,3829699,3885703,3936169,3993179,4044544,4102643,4154916,4214039,
4267303,4327459,4381647,4442922,4498042,4560368,4616506,4679893,4736979,4801514,4859557,4925171,4984258,5050960,5111020,5178900,
5239941,5308927,5371039,5441141,5504250,5575559,5639674,5712117,5777329,5850915,5917149,5991972,6059236,6135220,6203608,6280763,
6350197,6428618,6499107,6578717,6650356,6731164,6803874,6885978,6959767,7043087,7118053,7202599,7278660,7364531,7441696,7528811,
7607179,7695547,7775035,7864758,7945374,8036368,8118214,8210489,8293479,8387138,8471281,8566239,8651638,8747904,8834472,8932152,
9019897,9118903,9207931,9308273,9398494,9500279,9591702,9694841,9787573,9892075,9986025,10092000,10187176,10294532,10391044,10499791,
10597545,10707794,10806799,10918457,11018824,11131900,11233534,11348142,11451051,11567095,11671393,11788883,11894472,12013523,12120412,12240927,
12349231,12471219,12580839,12704418,12815362,12940432,13052818,13179389,13293115,13421306,13536381,13666091,13782634,13913872,14031780,14164668,
14283949,14418383,14539159,14675149,14797314,14934983,15058546,15197789,15322873,15463699,15590197,15732732,15860652,16004788,16134256,16280003,
16410909,16558394,16690747,16839861,16973788,17124540,17259930,17412450,17549311,17703487,17841949,17997791,18137740,18295379,18436824,18596147,
18739219,18900235,19044819,19207662,19353766,19518320,19666078,19832353,19981647,20149778,20300617,20470487,20623006,20794624,20948704,21122208,
21277857,21453127,21610483,21787529,21946470,22125431,22285966,22466721,22628989,22811547,22975425,23159928,23325424,23511748,23679004,23867159,
24036049,24226178,24396711,24588689,24761008,24954844,25128822,25324662,25500307,25698023,25875481,26075083,26254224,26455859,26636692,26840231,
27022903,27228355,27412735,27620250,27806346,28015792,28203754,28415141,28604835,28818314,29009749,29225187,29418514,29635920,29831004,30050532,
30247381,30468895,30667663,30891173,31091722,31317383,31519722,31747397,31951681,32181379,32387469,32619348,32827252,33061172,33271048,33507019,
33718725,33956906,34170451,34410701,34626244,34868572,35085970,35330538,35549799,35796463,36017749,36266519,36489684,36740723,36965776,37218939,
37446043,37701339,37930347,38187942,38418862,38678608,38911606,39173513,39408439,39672674,39909537,40175951,40414918,40683520,40924440,41195400,
41438281,41711447,41956459,42231841,42478830,42756599,43005574,43285577,43536709,43818955,44072089,44356752,44611896,44898820,45156148,45445343,
45704697,45996338,46257727,46551657,46815256,47111484,47377134,47675838,47943547,48244567,48514513,48817859,49089880,49395731,49669836,49978031,
50254399,50564947,50843415,51156498,51437074,51752528,52035394,52353229,52638219,52958618,53245741,53568539,53857978,54183184,54474772,54802572,
55096317,55426543,55722631,56055293,56353554,56688839,56989282,57327021,57629833,57970035,58275045,58617900,58925116,59270452,59580064,59927891,
60239725,60590234,60904299,61257317,61573804,61929340,62248074,62606322,62927311,63288095,63611533,63974863,64300572,64666643,64994632,65363267,
65693731,66064939,66397699,66771678,67106742,67483312,67820878,68200049,68539935,68921906,69264121,69648711,69993454,70380672,70727760,71117808,
71467249,71859943,72211939,72607289,72961654,73359863,73716606,74117489,74476813,74880379,75242097,75648552,76012672,76421828,76788556,77200423,
77569569,77984354,78355927,78773441,79147648,79567900,79944550,80367750,80746851,81172807,81554569,81983291,82367520,82799219,83185924,83620407,
84009799,84447075,84838959,85279242,85673626,86116720,86513818,86959733,87359347,87808298,88210437,88662227,89067106,89521744,89929164,90386868,
90796837,91257407,91670143,92133589,92548890,93015431,93433306,93902741,94323409,94795747,95219005,95694468,96120324,96598708,97027384,97508699,
97939989,98424458,98858371,99345789,99782548,100272924,100712322,101205882,101647927,102144463,102589381,103088903,103536484,104039219,104489472,104995211,
105448363,105957115,106412955,106924950,107383486,107898512,108359974,108878041,109342215,109863554,110330449,110854847,111324694,111852160,112324744,112855512,
113330841,113864695,114343003,114879953,115361022,115901303,116385142,116928537,117415381,117961899,118451529,119001408,119493832,120046852,120542308,121098479,
121596745,122156306,122657391,123220121,123724264,124290172,124797150,125366478,125876299,126448823,126961729,127537459,128053224,128632403,129151036,129733439,
130255183,130840819,131365447,131954562,132482082,133074448,133605106,134200733,134734299,135333434,135869917,136472331,137011978,137617680,138160260,138769500,
139315021,139927567,140476279,141092141,141643810,142263239,142817874,143440637,143998489,144624595,145185429,145815132,146378956,147012020,147579088,148215523,
148785597,149425658,149998747,150642197,151218556,151865404,152444794,153095298,153677727,154331647,154917373,155574719,156163500,156824531,157416376,158080851,
158676019,159343947,159942195,160613838,161215174,161890288,162494974,163173569,163781359,164463698,165074601,165760439,166374718,167064064,167681472,168374592,
168995137,169691783,170315731,171015913,171643014,172346999,172977262,173684801,174318493,175029595,175666465,176381400,177021456,177739972,178383484,179105591,
179752305,180478274,181128199,181857777,182511184,183244380,183901014,184638102,185297971,186038695,186702073,187446443,188113072,188861363,189531252,190283207,
190956631,191712259,192388959,193148538,193828522,194591792,195275338,196042309,196729155,197500106,198190261,198964931,199658674,200437072,201134140,201916548,
202616949,203403103,204107119,204897029,205604394,206398343,207109066,207906789,208621153,209422659,210140397,210945972,211667092,212476468,213201256,214014443,
214742629,215559914,216291507,217112621,217847908,218672860,219411570,220240650,220982791,221815727,222561589,223398391,224147700,224988659,225741424,226586267,
227342779,228191515,228951499,229804422,230567886,231424720,232191958,233052713,233823447,234688418,235462657,236331567,237109606,237982464,238764024,239641128,
240426217,241307287,242096203,242981249,243773710,244663031,245459046,246352361,247152229,248049547,248852985,249754608,250561624,251467268,252278164,253187839,
254002329,254916338,255734431,256652489,257474488,258396604,259222222,260148702,260977947,261908503,262741681,263676323,264513144,265452179,266292652,267235791,
268080223,269027475,269875575,270827250,271679026,272634832,273490594,274450541,275309995,276274394,277137549,278106107,278973274,279946000,280816884,281794092,
282668701,283650095,284528743,285514333,286396722,287386823,288272962,289267277,290157481,291156019,292049989,293053068,293950812,294958132,295859968,296871539,
297777165,298793306,299702731,300723141,301636684,302661372,303578730,304608018,305529199,306562783,307488109,308525999,309455164,310497683,311430696,312477539,
313414723,314465899,315406947,316462782,317407702,318467888,319417006,320481553,321434559,322503794,323460697,324534311,325495438,326573440,327538480,328621200,
329590161,330677287,331650499,332742041,333719190,334815479,335796574,336897297,337882669,338987835,339977169,341087112,342080416,343194820,344192428,345311303,
346312897,347436578,348442167,349570337,350580256,351712924,352726854,353864358,354882307,356024327,357046633,358193179,359219520,360370931,361401316,362557271,
363592039,364752547,365791375,366956778,367999674,369169648,370216954,371391509,372442899,373622378,374677861,375861939,376921858,378110544,379174572,380368212,
381436357,382634623,383707231,384910133,385986874,387194759,388275642,389488181,390573553,391790755,392880285,394102500,395196196,396423092,397521304,398752891,
399855285,401091914,402198499,403439837,404550964,405797020,406912354,408163482,409283031,410538895,411663013,412923623,414051972,415317683,416450272,417720747,
418857931,420133179,421274619,422554998,423700702,424985872,426136198,427426169,428580775,429875906,431034801,432334751,433498294,434803072,435970920,437280888,
438453049,439767863,440944699,442264369,443445534,444770423,445955926,447285689,448475893,449810539,451005097,452344992,453543912,454888708,456092356,457442063,
458650089,460005074,461217487,462577401,463794568,465159420,466380990,467751150,468977131,470352247,471583009,472963091,474198280,475583699,476823324,478213727,
479458159,480853555,482102439,483503202,484756546,486162320,487420498,488831293,490093947,491510138,492777277,494198507,495470506,496896784,498173284,499604988,
500885997,502322767,503608663,505050509,506340930,507788231,509083186,510535581,511835449,513292947,514597365,516060348,517369324,518837428,520151344,521624579,
522943069,524421818,525744891,527228789,528556828,530045884,531378522,532873122,534210367,535710143,537052381,538557343,539904204,541414739,542766232,544281971,
545638483,547159435,548520595,550047150,551412966,552944752,554315614,555852641,557228175,558770834,560151049,561698967,563084254,564637440,566027424,567586272,
568980961,570545095,571944883,573514313,574918822,576493943,577903182,579483617,580897981,582483739,583902849,585494328,586918192,588515012,589944028,591546199,
592979985,594587906,596026471,597639761,599083504,600702172,602150710,603775158,605228499,606858343,608316889,609952139,611415504,613056563,614524756,616171239,
617644663,619296579,620774847,622432602,623915722,625578928,627067306,628735973,630229219,631903754,633401877,635081891,636585298,638270800,639779100,641470500,
642983701,644680607,646199119,647901541,649424970,651133319,652661674,654375557,655909249,657628675,659167309,660892692,662436276,664167220,665716168,667452683,
669006597,670749098,672307987,674056077,675620356,677374044,678943314,680703018,682277287,684042607,685622293,687393239,688977940,690754931,692344656,694127291,
695722459,697510747,699110955,700905318,702510574,704310608,705921334,707727049,709342839,711154658,712775521,714593039,716219398,718042624,719674072,721503432,
723139977,724975063,726617131,728457953,730105134,731952119,733604422,735457161,737115013,738973515,740636505,742501200,744169336,746039812,747713524,749589791,
751268665,753151154,754835199,756723497,758413144,760307260,762002094,763902462,765602491,767508695,769214353,771126403,772837272,774755603,776471692,778395887,
780117631,782047699,783774679,785711058,787443282,789385552,791123458,793071629,794814795,796769306,798517741,800478171,802232314,804198672,805958100,807930828,
809695549,811674223,813444679,815429309,817205074,819196103,820977186,822974189,824761033,826764019,828556197,830565612,832363132,834378548,836181856,838203283,
840011949,842039834,843853867,845887781,847707628,849747580,851572810,853619250,855449871,857502367,859338829,861397391,863239260,865304339,867151624,869222787,
871075939,873153195,875011779,877095582,878959606,881049520,882919438,885015473,886890847,888993458,890874297,892983047,894869806,896984704,898876944,900998448,
902896177,905023847,906927523,909061369,910970550,913111031,915025726,917172401,919093069,921245947,923172145,925331688,927263424,929429188,931366924,933538919,
935482209,937660898,939609751,941794689,943749568,945940764,947901222,950099142,952065187,954269383,956241481,958451963,960429664,962646899,964630212,966853751,
968843143,971072995,973068015,975304650,977305306,979548272,981555034,983804341,985816755,988072874,990090949,992353427,994377634,996646480,432011,2707699,
4743268,7025342,9067070,11355540,13402969,15698310,17751449,20053204,22112528,24420706,26485756,28800835,30871619,33193139,35270135,37598106,
39680852,42015753,44104258,46445628,48540371,50888219,52988737,55343545,57449846,59811150,61923716,64291526,66409891,68784690,70908863,73290186,
75420650,77808506,79944794,82339669,84481789,86883215,89031653,91439640,93593926,96008961,98169104,100590718,102757205,105185407,107357767,109793047,
111971288,114413174,116597786,119046288,121236797,123692406,125888821,128351064,130553876,133022762,135231496,137707519,139922183,142404867,144625955,147115310,
149342344,151838865,154071854,156575064,158814503,161324411,163569821,166086925,168338314,170862134,173120000,175650546,177914407,180452178,182722043,185266558,
187542926,190094194,192376582,194935105,197223521,199788815,202083761,204655836,206956826,209536185,211843228,214429386,216742985,219335951,221655619,224255899,
226581644,229188750,231521078,234135020,236473441,239094726,241439249,244067388,246418520,249053522,251410772,254053147,256416523,259065779,261435791,264091938,
266468092,269131641,271513946,274184404,276573371,279250747,281645881,284330689,286731998,289423742,291831740,294530430,296944619,299650770,302071159,304784274,
307211378,309931466,312364786,315092365,317531909,320266479,322712765,325454336,327906862,330655953,333114728,335870838,338336381,341099519,343571327,346342015,
348820096,351597830,354082706,356867496,359358661,362151030,364648493,367447936,369952220,372758746,375269344,378083479,380600399,383421635,385945403,388773750,
391303856,394139841,396676294,399519408,402062735,404912987,407462677,410320597,412876658,415741734,418304696,421176938,423746287,426626226,429201971,432089094,
434671766,437566082,440155166,443057209,445652713,448561967,451164425,454080900,456689794,459614025,462229364,465160834,467783153,470721871,473350651,476297155,
478932404,481886174,484528430,487489476,490138217,493107078,495762313,498738468,501400736,504384194,507052972,510044275,512719571,515718195,518400551,521406506,
524095396,527109225,529804658,532825836,535528355,538556891,541265969,544302409,547018054,550061870,552784628,555835830,558565171,561624306,564360239,567426778,
570169850,573243802,575993482,579075397,581831693,584921039,587684501,590781288,593551382,596656161,599432896,602545134,605329061,608448767,611239351,614367079,
617164328,620299542,623104010,626246720,629057869,632208630,635026469,638184744,641009828,644175626,647007416,650181295,653019799,656201219,659046995,662235966,
665088472,668285553,671144798,674349448,677215991,680428219,683301517,686521885,689401946,692629910,695517296,698752866,701647031,704890770,707791723,711043086,
713951390,717210386,720125494,723392689,726314609,729589455,732518753,735801260,738737386,742028121,744971084,748269498,751219865,754525967,757483187,760797547,
763761628,767083694,770055206,773384988,776363377,779701446,782686721,786032524,789025256,792378802,795378436,798740299,801746843,805116467,808130495,811507890,
814528844,817914585,820942474,824336004,827371403,830772731,833815081,837224785,840274094,843691614,846748460,850173806,853237627,856671378,859742183,863183778,
866262146,869711594,872796962,876254845,879347221,882812975,885912941,889386576,892493566,895975665,899089688,902579686,905701325,909199231,912327919,915834319,
918970064,922484390,925627778,929150040,932300501,935831286,938988829,942527568,945692780,949239482,952411792,955967047,959146463,962709699,965896811,969468038,
972662272,976242081,979443446,983031264,986240351,989836187,993052421,996656869,1635905,5248389,8479527,12100057,15338366,18967537,22213026,25850261,
29103525,32748833,36009293,39663272,42930936,46593006,49868472,53538643,56821329,60500200,63790115,67477105,70774848,74469966,77774954,81478802,
84791043,88503037,91823133,95543283,98870648,102599557,105934200,109671283,113013807,116759073,120108891,123862946,127220066,130982322,134347350,138117817,
141490163,145269448,148649121,152436635,155824242,159619994,163014944,166819544,170221845,174034701,177444963,181266085,184683714,188513713,191938718,195777001,
199209993,203056569,206496953,210352436,213800220,217664014,221119812,224991927,228455141,232336192,235806831,239696221,243174900,247072638,250558758,254465462,
257959031,261874101,265375737,269299183,272808284,276740725,280257300,284198135,287722803,291672041,295204199,299162462,302702118,306668802,310216578,314191693,
317746983,321731152,325293965,329286583,332857542,336858618,340437116,344447276,348033321,352051957,355646175,359673297,363275078,367311313,370920666,374965405,
378582957,382636209,386261349,390323744,393956480,398027406,401668368,405747835,409396409,413485048,417141243,421238441,424902888,429008654,432680738,436795706,
440475435,444598989,448286997,452419147,456114816,460256197,463959536,468109531,471821175,475979793,479699123,483867002,487594026,491770546,495505902,499691073,
503434139,507628600,511379385,515582515,519341658,523553466,527320344,531541472,535316093,539545917,543328923,547567453,551358218,555606097,559404630,563661233,
567468177,571733513,575548241,579822956,583645476,587928942,591759900,596052127,599890893,604192528,608039111,612349525,616204572,620523774,624386654,628715294,
632586015,636923461,640802673,645148935,649036004,653391733,657286668,661651231,665554683,669928089,673839423,678222326,682141550,686533314,690461082,694861717,
698797391,703207552,707151141,711570191,715522350,719950298,723910388,728347892,732315921,736762341,740738967,745194313,749178894,753643825,757636370,762110245,
766111413,770594241,774603389,779095832,783112968,787614382,791640168,796150563,800184353,804704392,808746195,813275233,817325712,821863758,825922266,830469986,
834536531,839093277,843168525,847734307,851817608,856393093,860484456,865068995,869169087,873762689,877870859,882474194,886590450,891202866,895327878,899949385,
904082499,908713768,912854993,917495371,921645378,926294874,930453008,935112296,939278565,943946989,948122067,952799637,956982866,961670257,965861646,970558201,


1,9,31,79,156,295,484,781,1162,1705,2364,3275,4324,5716,7304,9330,
11585,14433,17528,21364,25513,30543,35922,42416,49249,57408,65989,76088,86624,99003,111782,126690,
142077,159839,178083,199132,220569,245179,270265,298832,327836,360868,394194,432008,470187,513226,556564,605441,
654387,709432,764619,826349,888093,957201,1026021,1102875,1179484,1264646,1349392,1443670,1537114,1640878,1743847,1857736,
1970576,2095483,2218828,2355157,2489919,2638350,2784902,2946454,3105470,3280538,3453054,3642398,3828774,4033504,4234490,4455029,
4671751,4908897,5141738,5396738,5646484,5919741,6187653,6480049,6766486,7079363,7385190,7718974,8045548,8401156,8748853,9127775,
9497493,9900125,10293367,10720712,11137819,11591467,12033420,12513785,12982187,13490304,13985508,14523127,15046144,15613637,16166227,16764718,
17347189,17978533,18591981,19256563,19902853,20601827,21281274,22016665,22730392,23502532,24252573,25062708,25849321,26699586,27523982,28414718,
29279041,30211520,31116030,32092568,33038501,34059375,35049054,36115631,37149248,38263960,39342842,40505969,41632554,42845486,44019964,45285325,
46509044,47827039,49102627,50474745,51802313,53231298,54612288,56098343,57535504,59080138,60573573,62179733,63730902,65398706,67010559,68741617,
70414167,72211551,73946356,75810177,77610312,79542197,81407662,83410898,85343266,87417867,89420425,91568122,93640770,95864980,98009391,100310116,
102529707,104908693,107203346,109664235,112035635,114578321,117030109,119656445,122188391,124902154,127516046,130317114,133016728,135906965,138692048,141675467,
144547817,147624177,150587804,153759079,156813607,160083951,163231284,166600434,169844722,173314660,176655500,180230627,183669929,187349852,190892011,194678826,
198323305,202221558,205970376,209979647,213837345,217959735,221925743,226166056,230242396,234600072,238791541,243268797,247574680,252176470,256598902,261324634,
265868562,270720455,275385126,280368404,285155953,290269872,295185513,300432411,305475236,310860492,316032751,321555584,326862646,332525394,337966308,343774630,
349351643,355304595,361023355,367123397,372982786,379235737,385238120,391642995,397794180,404353435,410652256,417372001,423820818,430699894,437304804,444345792,
451105451,458314627,465231516,472607674,479688055,487233769,494476246,502198094,509605139,517501730,525079905,533153942,540901662,549159893,557079754,565520736,
573619471,582245897,590521863,599340794,607796575,616806373,625449013,634652502,643480158,652884574,661899958,671503606,680713937,690519628,699923000,709938295,
719537405,729760402,739562791,749996435,759999987,770652019,780859561,791728017,802147270,813235080,823863860,835179100,846020216,857560704,868622211,880391014,
891670506,903675885,915176304,927416011,939145597,951622680,963578954,976302020,988487904,3210123,15634201,28847467,41507027,54975785,67873885,81595586,
94741000,108718810,122108749,136351823,149989321,164494870,178389056,193160390,207308231,222354700,236759369,252078107,266748929,282343221,297277080,313156644,
328356686,344518406,359994322,376441629,392190048,408932860,424957071,441992190,458302084,475632913,492225031,509861868,526739469,544678854,561852206,580097691,
597563070,616125158,633885968,652761112,670827826,690019548,708388349,727907542,746581801,766424645,785415224,805585393,824888198,845396795,865015345,885858459,
905803826,926985097,947253089,968784021,989378122,13010167,33941848,56167507,77432288,100018928,121620444,144563773,166513710,189817486,212111262,235787617,
258428828,282473175,305473917,329890173,353245565,378046082,401759874,426939963,451024472,476588010,501038247,526998009,551817682,578168674,603370521,630116781,
655695503,682850031,708809494,736367189,762720356,790685213,817426672,845812126,872945698,901746331,929285411,958505382,986444238,17852859,46195472,76275919,
105035914,135547948,164719475,195677206,225264198,256661768,286678294,318519984,348959862,381260017,412127343,444879989,476189067,509398436,541142961,574823854,
607007872,641153976,673792245,708407962,741493834,776594206,810131893,845710485,879714985,915776147,950240685,986799926,23484307,60534842,95943235,133489588,
169370511,207428436,243786216,282348801,319199147,358270861,395606511,435203586,473028810,513143974,551474957,592112855,630941970,672119084,711450774,753159700,
793010400,835255725,875617670,918416366,959293939,4393877,45804000,89698652,131633185,176095425,218558926,263580841,306590487,352176783,395724291,441892695,
485982560,532724776,577374674,624695590,669896851,717814454,763571751,812077604,858408873,907507800,954404223,5870369,53336554,103649794,151704186,202625176,
251258559,302806063,352023226,404188266,454007919,506795437,557208212,610637494,661648111,715709774,767337463,822036638,874271622,929627865,982475048,40234471,
93713354,150369724,204470372,261799425,316526670,374518456,429892330,488552101,544562249,603910369,660561811,720588173,777901216,838610999,896575125,957989238,
18365039,80472948,139769979,202577057,262540017,326067453,386701477,450938575,512264792,577216850,639224144,704912906,767606334,834020666,897421911,964567308,
30420459,98318950,163117963,231758248,297280738,366668233,432902469,503059769,570010921,640926277,708616877,780295905,848713769,921179355,990329849,65325719,
135231665,209252059,279901096,354725124,426122534,501737815,573906995,650319267,723247392,800480413,874172964,952214176,28450493,107305549,182561330,262254576,
338290862,418809270,495650340,576999769,654632140,736837236,815266505,898314058,977564804,63216232,143274784,228044039,308915904,394544941,476255295,562750094,
645284781,732670893,816035625,904299171,988519429,79421946,164483381,254539736,340447967,431399435,518180552,610033235,697672392,790452761,878955785,972649277,
63798215,158410838,248679352,344238198,435387667,531877669,623935112,721362493,814312358,912704526,8308403,107650094,202424023,302721363,398405237,499686266,
596285929,698534868,796078284,899301478,997772374,103753830,203158264,308370707,408736964,514942286,616253885,723481089,825743986,933976566,38975334,148219756,
252426090,362711682,467887403,579197452,685371811,797712680,904868453,20025772,128169028,242614253,351774895,467270260,577430524,694006342,805172517,922811326,
36769292,155477574,268698055,388506788,502751612,623642786,738942850,860923174,977259944,102116378,219496258,343699282,462153504,587465365,706975172,833427859,
953999545,83329920,204995391,333698990,456438926,586303726,710124647,841131641,966065793,99977346,226005182,359343017,486470943,620971130,749232077,884901568,
16031062,152903219,283396601,421451620,553097814,692342532,825121184,965589661,101262936,242934788,378025365,520907665,657150252,801277410,938678758,85785805,
224380237,370962834,510729173,658578087,799522964,948616987,92531079,242877405,386227646,537861750,682410653,835311090,981094040,137023531,284018513,439501959,
587715716,744486716,893955352,53776869,204477762,363875057,515815188,676521619,829737452,991760211,147984523,311360896,467089249,631796333,788821567,954866799,
114921073,282342105,441921222,610694904,771592069,941725711,105672831,277204827,440697576,613604151,778436474,952725187,120628362,296337977,463807922,640914412,
809745443,988256237,160179374,340133989,511645018,693018792,865912780,50469040,224720720,408988064,584604764,770313920,947335435,136249597,314650397,503298928,
683086206,873199187,56169147,247754379,430369547,623468067,807491533,3833160,189305861,385386967,572282455,769900499,958226079,159110222,348907605,549554476,
740796552,943003995,137453969,341195232,535383906,740666773,936322411,144945512,342075532,550500152,749147434,959137264,161029399,372627813,574261181,787440486,
990614004,207137749,411823084,628224146,834428828,54190128,261958222,481576632,690879121,912154854,124755174,347659580,560090898,784631998,376308,226599476,
442153126,670029022,887192926,118485484,337229647,568473347,788805674,23482188,245448346,480054519,703624225,939962298,166898954,404938603,631777399,871527032,
101748274,343254890,573355304,816588292,50126061,295093679,528526228,775276305,12122795,260624007,497420862,747681739,986152608,239977036,480130054,733975124,
975858419,233243801,476825077,734288557,979575794,240596327,487638492,748713435,997477504,262167647,512661871,777423284,31452692,298049516,552069488,820552071,
78081993,348416964,605995774,878191906,139296833,413404894,674533010,950519327,215232579,493105765,757858486,39425819,305981860,587697628,856108503,141492894,
411723480,697317256,969376035,258655765,532594676,822057797,99597051,391052141,668688761,962100338,243398429,538775508,820187580,119339169,402629466,702008477,
987230240,290356817,577473532,880890627,171666370,477093068,768070670,77271755,370169577,679688436,974515190,287826239,584636485,898237398,198749174,514451175,
815161729,134682808,437403241,757241362,63688929,385655757,692327992,18141195,326849639,653007009,963712943,293782699,606494777,936926856,253457524,586016953,
902815404,239315200,558146024,895035797,217711886,556756488,879726702,222740068,547768820,891199760,220100858,565714520,894936019,244546788,575853394,925909748,
261115719,613382628,948935681,305228460,642893121,1415083,341250890,700256010,43976806,405280854,749384519,114701765,461003939,826832531,177046714,545203362,
895827251,268025402,620875576,993613680,350402812,725498039,84479771,461889580,821369657,202859255,564550002,946670569,312336737,696800545,64748828,451565742,
819996333,210984940,581662891,973268175,348011939,741999225,119008643,515441833,892970474,293560648,673427925,76429423,458589975,862311522,248530516,654682840,
43268866,451861764,841013456,253867920,645350253,60664862,454543044,870572259,268555358,687120646,87462651,508517881,909528828,334839562,738228156,166105552,
571881234,2278294,410507729,841679035,254070058,687838542,102645257,538963559,954497464,395131265,813099827,256361760,676774532,122616359,545541480,992217905,
419361960,868697395,298314603,750260444,182419429,636985828,71637155,528893883,964291571,425944782,863914106,328218625,768709257,235735346,678757268,148455062,
594078392,66458161,514632194,988009570,440499731,916579596,371701371,850494319,308196099,789773904,250065786,734377306,197330919,684386543,149949895,639822425,
108005406,600642790,71518055,566931008,40445650,538707474,14871706,515929967,993061297,498682149,978482929,486985067,969465300,480795368,966029246,480198080,
968131383,485213830,975856886,495799203,989226709,512039522,9952512,533956071,34609013,561504289,64972929,594770880,100999668,633776701,142776080,678477128,
190323354,728959161,243596286,785244320,302682572,847286822,367603516,915175061,438313301,988930125,514900470,70261812,597386445,155747520,685724790,247164654,
780004901,344466191,880248315,447742232,986407976,557014096,100329781,672234692,218524092,793494422,342698872,920815280,472945232,55904635,609284944,195343017,
751669695,340907622,900191459,492550103,56627773,650362586,217418394,814367302,384411813,984514702,557630035,162653995,737023475,345295668,922685847,534145747,
116394921,729298099,314589175,930775192,519118847,140281836,730006176,354402055,947200289,574913507,172552302,801765282,402573279,36808651,638967342,276555024,
881830846,522707909,132941911,775364394,388737065,36302368,651069197,301958322,919960898,574185299,197114978,853006241,479118278,140123336,767749151,432124165,
64709747,730786848,366587801,37813495,675161785,349791998,990377534,668501182,314090625,993886253,642812705,327803536,978244587,666764440,322242751,14225386,
671318962,366776070,28929004,726195554,391663326,94183340,761300749,467330630,139540734,847416006,522974640,236138888,913381406,630090793,312459810,32806667,
716802128,440717703,129943062,855683880,548313764,279484010,973774369,708549203,408104051,146495401,847733270,589835198,296278734,42020993,750252791,499647674,
213107796,964494284,681438796,438257489,158780845,917532495,641563011,405854722,133403862,899652581,630815979,402545415,137250318,911045557,649303793,428603918,
170511692,951817574,697301675,484222181,233294185,24000382,775002038,569506462,325874773,124275572,882511188,684734619,448446805,254505151,21863506,830100473,
601116686,414968738,189741982,7466129,784164913,605861088,388008765,213601676,997786705,827288754,616946117,450458452,243844303,81290534,876750193,718143099,
519110446,364551760,169283322,18696188,825537870,678934808,491320017,348803986,164988989,26482024,844813950,710328951,534240094,403880611,231627614,105315210,
935245792,812993105,648539083,530450900,369868653,255865417,99259546,987598632,834888536,729186620,580384704,478806105,334017566,236575041,95718795,2518974,
863851512,774813231,641952290,557088692,428196406,347614721,222703611,146322193,25499302,951575379,834758000,766911356,654111740,590503940,481830387,422474695,
317843353,262848864,162272369,111555808,15143065,966961779,874628443,832604091,744362525,706655032,622615410,589238162,509314982,480378954,404584967,380005240,
308451230,288240916,220840883,205112238,141878658,130545599,71590535,64666569,9902853,7500852,955185704,957219088,910976480,917458479,875445094,886489872,
848718298,864238100,830822305,850830760,821681895,846293787,821424834,850551906,830077454,863733055,847563747,885863964,874012500,916867891,909450161,956874476,
953799933,7665531,8947273,65652911,71407453,132722245,142858527,208900500,223431335,294109343,313152558,388480472,411943807,492040284,519936952,604710334,
637158792,726622665,763530135,857804481,899183888,998175841,45902613,149626166,200095019,308670789,363650698,476985303,536596684,654703828,718852168,841853804,
910552141,40109315,113479399,246094931,324041026,461593157,544128707,686522314,773769709,921018614,14637238,166865382,263357091,420468121,521712297,683720449,
789619595,956649455,68972777,240927465,356288050,533181507,653236972,835195142,959958749,148639159,278236645,470142358,604474448,801487705,940568074,144345870,
288300905,495346005,644075893,856271908,11545671,228792697,387226795,609539310,772788322,2050592,170128308,402728598,575763427,813471562,991361893,236063519,
418822839,666904958,854663055,109651561,302305557,560819815,758383615,23832674,226436726,495323588,702864466,977076828,191323779,470758122,688331689,973002734,
197309507,487349970,714892676,11954138,244620926,545206507,782892121,90647233,333365385,644673383,892557975,210944996,463889483,785979021,45753186,373194985,
636422107,969230700,239314970,577626558,851070506,196533538,475228795,824346941,109940751,464606534,753601855,115463167,409752305,775312503,76542139,447695171,
752367948,130760399,440770045,822905706,139897592,527671091,848148290,243205650,569062570,967907267,300788711,705316808,43481178,453581733,795413577,212857444,
560000243,981417229,335641112,762675356,122365556,555031946,918320077,358516807,727172678,173031264,547197199,996977322,378294896,833895441,220623605,681931163,
74212931,541242508,937207584,411859522,813277827,293681730,700697733,186869051,599366759,91450882,509445008,7326610,430962319,932900878,363817241,871715262,
308171018,821911825,264053605,783652769,231362642,756967721,210260516,741754252,200777300,738174936,202809718,746260292,216521307,765906199,241942255,797277157,
278968370,840403025,327764339,895179540,388360468,961771577,460651642,41965539,544803705,132144163,640847079,234229912,748675724,348252875,868456642,474106940,
1976021,611959299,145615595,761840944,301299179,923644044,469057429,99293392,648782440,285308014,840643547,483335580,46427171,693545614,262513174,915969346,
490827711,152252712,731401671,399055911,984125270,658165141,250925837,929470543,528323086,214899638,817961932,510972598,121770885,819333464,436269775,141911739,
763102568,475226910,104198957,820922869,456078890,180929501,820385377,551767215,199049301,935078141,588590725,332794160,990651703,741434991,407164308,164398259,
834648721,598349289,276501680,46831315,729389514,506217598,196855108,978442415,675271647,465292656,168329246,963141429,672548321,475679044,191323673,1182030,
721324035,537777353,266092526,89157347,822000386,651842192,392740143,229225639,974832446,817977822,571670144,421642449,181680037,38344526,803138536,666511873,
439437510,309687489,89004973,964240575,750117455,633866283,426165837,316841616,115579354,13045252,816634652,720907454,532721623,443971451,262270725,180360115,
5314369,928504101,759974510,691947590,529949777,468811622,313517049,259284565,110552932,63398586,919490344,879274563,743873223,710612553,581821525,555690033,
433525052,414381682,299016564,286878344,178170659,173212416,71178377,73258414,976316950,985451931,896971258,913337621,831577940,855032494,780169990,810729884,
742619981,780462419,719121446,764102590,709707497,761844129,714249688,773720634,732942805,799602722,765820075,839686234,812752032,894004029,873934716,962426556,
949401473,46905704,40777456,143964013,144748672,255225692,263104230,380889105,395712607,520987341,542772367,675388793,704317090,844292227,880214217,29487361,
72419229,227329392,277454527,439774869,496942163,666857113,731083241,908442443,979911574,166487813,245048171,437516237,523184119,723147765,816108994,25341502,
125442760,340619705,447877782,670602251,785203755,17248651,139039591,377082155,506078941,751720711,888111615,143125994,286755472,547820492,698705450,967421977,
127507124,403892532,569510353,853755645,28433956,320382791,500801035,800471291,988227330,297566452,492677307,808016983,12429834,335543204,545588289,876668839,
95874086,434763228,659810562,8281942,240766967,595503577,835443430,199797294,447385994,817863429,74695892,453248531,715830210,104052848,374335106,768734569,
48310737,450839463,736215499,148467596,441595668,860077572,162550318,589216177,897539162,333981491,650108592,94589986,418356597,869320720,202499855,661538531,
2573583,469704660,816674678,293854835,648532438,133840601,496426548,988125433,360208459,860255561,240097502,748326697,136129127,652558381,48153686,572986579,
974636196,509460636,919123516,462202341,879709251,431246861,856615399,416443353,849877644,418014027,859344130,435995085,885238196,470233657,927595642,520954215,
986263503,588192156,63222108,671794421,154996081,771985904,263186988,888803044,388020861,23846387,529533733,173831809,687570407,340550586,862358265,523847425,
55689105,723949921,263895313,940894750,488961275,176280210,730923258,426824893,989623817,694320305,267048696,978608904,559722987,281676649,869243760,600049158,
197598125,935322467,541311289,289484839,901979189,659061070,281590302,47402647,676669953,451231320,90568587,872339886,520009113,312322101,966783912,767902034,
432486642,242627300,913841586,732824516,414396891,242240770,930478126,767402154,465833543,311655776,18744464,871728468,587290956,451168075,175222654,48054565,
779065351,660870849,402164899,293165844,43005382,941261759,699868355,608910792,376098514,294394079,70181333,995789274,780398485,716849010,510093503,455855500,
257753258,212639919,23415186,985690320,805154714,778555010,606727052,589309314,426414108,418197368,264045784,265257268,119867402,130317847,992160985,13625615,
884266556,913462169,794675197,833167430,723424696,771232699,670342603,727696310,635677060,702384736,619465970,695547314,621535703,707221519,642135815,737233616,
681304328,785833383,738866424,853059390,815073080,938735735,909962434,44870245,25114126,167989331,157269262,309672529,308221745,470172461,477794372,649527934,
666240973,847560655,873599919,66281309,101448458,302216539,346530556,556943487,610640349,830717636,893598235,125333677,197416558,437099615,518622629,768029011,
858791288,119915679,219936317,489067411,598585146,877498214,996311403,287003015,415130316,713887397,851569430,161923458,308956807,627638302,784042181,114359884,


1,11,46,136,306,637,1156,2023,3267,5141,7653,11253,15824,22065,29800,39949,
52166,67869,86310,109485,136352,169393,207144,253068,304731,366743,436046,518110,608933,715774,832840,969362,
1118283,1290297,1476756,1691209,1921917,2185637,2468573,2789710,3132582,3520598,3932577,4396675,4888418,5439303,6020965,6671226,
7354662,8116004,8915117,9801367,10728913,11756008,12827056,14009726,15241680,16597021,18005708,19553708,21157565,22916000,24736613,26726496,
28782804,31028324,33342749,35865351,38463829,41288474,44193613,47349515,50587798,54099954,57702448,61600537,65593442,69911774,74326341,79094173,
83966688,89218328,94579255,100355056,106240359,112573592,119025690,125956212,133009603,140583747,148279952,156535830,164923401,173906174,183024409,192787509,
202683299,213269296,223998372,235458778,247064870,259460019,271996397,285374261,298903686,313321744,327893275,343420082,359093010,375781357,392626706,410541251,
428612895,447830043,467194439,487772918,508509058,530520174,552687770,576217266,599889435,625001197,650266347,677039700,703962652,732492157,761154010,791510031,
822008125,854277257,886682734,920970055,955371334,991752667,30013293,68584098,107269303,148144498,189107158,232369508,275727437,321480308,367316845,415686895,
464107184,515182894,566316514,620211003,674146914,730997667,787850657,847753563,907664168,970740882,35560931,101961939,168303453,238130611,307902789,381288340,
454593178,531699472,608670808,689607555,770410898,855319495,940064477,30877261,119706853,213028351,306122367,403861084,501335160,603680713,705689163,812765647,
919501295,33227017,144813529,261882462,378483879,500782010,622606831,750309166,877487138,12568601,145275969,284364318,422823670,567859925,712209406,863429878,
15611734,173161816,329904351,493982653,657185810,828043802,997907257,177455028,354233567,539169391,723016097,915365553,108246641,308170564,506847948,714570088,
920958681,138520866,352845192,576906363,799455986,33762730,264705985,506053117,745625987,995945840,246213414,505756331,763381821,34226959,301216887,580039369,
856720636,147294215,433850695,733009071,31459306,341150921,648331890,968835171,288448210,620126730,948939185,293751422,633885840,988611658,342023375,708804981,
74029559,453076091,828747742,222122903,610202991,16557471,417353856,835151517,250829526,682147310,111166913,556435733,997362306,458563516,913586873,389303955,
858645606,349330526,833329063,339218109,838328734,359774820,874229229,411710530,941860959,495619808,43703210,612355710,176853854,762656073,343939688,947144776,
545717498,168467177,782821116,423888040,57919385,715806967,368291472,46916818,716352096,414511373,104813099,821020753,530988217,269176207,997317547,756311693,
506557266,286633281,57811841,857655443,650036082,473764838,287786991,133932190,968449430,837467872,696271274,588800581,470589119,386921571,292335733,232949805,
162274322,127833755,81544571,72353100,51116831,67668817,71781021,114773348,144725716,214467149,270959286,367966842,451298916,576297001,686982989,840291906,
979058870,162967670,330126788,541883564,737964984,979650358,207171600,479342691,735107871,40308531,326626699,661682268,979344176,348339949,697672045,99677437,
481249772,914850114,331245764,798795353,248588929,750943027,234728885,772240230,290875987,864160594,417987615,29695240,617569353,266300924,890873974,577271163,
240643583,963876460,664929302,428877571,168538619,970350572,748975768,593129152,411372773,296483707,155314139,82068886,980089271,949487320,890889449,903314530,
887344152,943500836,970527919,73214077,143937224,290028129,405491252,597474825,758050194,997003225,205172318,491493294,744823183,81018789,381648650,765329160,
115758944,549080766,946922088,432420726,879814481,416891821,914610555,503679284,54637556,694741098,297579669,991678063,647188384,397451717,106839314,910585149,
674247522,536229007,354986956,273874796,148971262,125613966,57457563,93146051,82576910,177738563,226048348,381562514,489160349,706356933,874113250,155187152,
384432543,726771985,19682269,426423951,780378011,253717176,671852212,210964633,693700536,300007794,848266083,522219672,139178014,879974212,564307807,376932841,
129583448,12732784,833419844,788078382,680743005,708427863,672288556,773462574,810036451,985705445,97188902,348925590,532802037,861068110,122421255,528256677,
864014156,350790979,763736597,330172483,821922356,469078590,41838002,769633228,422695627,235112585,968396016,864775492,682238235,664299819,565269940,633496567,
619692975,775202792,847083019,93411573,252080650,586196778,833433504,260002893,596261374,115355214,541776084,153885840,672294743,378597005,989458412,791842602,
498074481,397028369,198763062,195500594,93198138,189657331,184516736,381196617,475154371,773291363,966817661,370170422,664486423,171793709,568900546,181437252,
681799731,401619247,8251961,834104002,547302610,483996208,304235548,352135893,280697313,440304170,479306058,751956867,901867679,291490908,553630883,58981385,
435520887,57959305,549376469,291145562,898783371,760387135,488241163,471080976,317866292,424238624,391338323,621757661,711465264,69112184,281907810,765640067,
104685538,716765604,182670876,924565558,517802363,393691821,115707464,124353097,975812871,120461134,105357172,384996331,503043695,919937685,175387716,731070378,
122638656,819666787,348866282,189513858,857141723,841211162,651258703,781384463,733632836,12079001,109158253,534015788,776395159,353868964,743128661,471981142,
12565754,892668068,583299744,620937110,463220086,657143840,653846947,7485021,159074085,671749966,979873776,655615018,124858877,961851331,590933494,595606250,
386199832,557301333,512318565,851592503,971494075,483676591,770181449,454029904,910112825,767396074,395281080,429065490,228740497,439525531,414050615,803652863,
953482026,526788068,853711755,609473940,118372278,58432776,746255747,873834025,745908264,63253119,121035647,626526890,870463168,570898014,4607088,896975643,
521980822,611711231,428464813,717178703,727569379,217507612,424905212,116279133,521118775,417374150,23349418,124979160,932016782,242769552,254822445,774726931,
992002816,725045657,152831924,99301972,734510367,898017907,746173532,128956800,191906000,792524493,72451853,896368620,393557984,442992400,161142372,436462165,
375981653,880966485,45702402,780822771,172790147,141951625,759809113,965135907,814511996,258209798,341219059,23735964,340771313,266061418,819292909,987812529,
782940073,198675531,234341263,897838408,177994192,93198674,618380127,785822037,559915192,983727919,8983073,689606857,966635672,908138941,440831764,645698330,
434576337,903222937,952514610,689065985,881411,7899784,581059805,858967118,701289574,254237842,364325405,194985989,575197403,683967154,340473190,729806190,
661183299,337342528,546006006,507637304,998082523,249423118,23740968,565899143,624776088,461638047,809681133,942031656,581303900,15600608,945090771,679956974,
907865571,945869408,472506333,818465314,644601991,300622334,431062792,398017113,833041826,117587777,859782877,460518814,516528240,436110489,804460951,49665747,
732970582,302366184,307387462,203691610,528924745,757244640,407118943,967781434,945634058,843140647,150979516,388803569,27574235,606010755,580927221,504540420,
815821892,89929688,740338970,363482856,360078109,335094951,676340412,10428860,699114893,390782801,434092027,486240429,882602201,302520669,56543887,840986081,
956432894,113595270,590650495,122684080,964228692,871363122,86553972,371784095,955502318,626339211,585041414,639959815,977628760,421407813,139946304,974962050,
77343278,307300052,795882232,423870187,302273289,332519435,602026491,36479535,703055109,543078524,608585264,860296852,327801459,991355020,865201051,945539343,
227548872,729131605,420682485,345418533,452707252,802057041,326903216,108976329,52786132,265938935,635046759,284320304,80503212,170595762,395328048,926350110,
587821347,564843076,661315935,90933298,625666007,506190652,487514151,822331433,250219468,47783095,922052051,182427013,513265448,238110691,25488265,221647423,
467164572,136413198,846892059,990961144,169836037,795673611,442860282,552238774,674663464,271098873,868679671,957513679,37217434,618419496,183809572,262724747,
313670666,895747360,437532464,524491810,562541532,158002588,692180642,801744546,837362888,462701325,7093209,150144383,201366999,869596767,433035567,628110950,
709452307,435096740,35902433,297982497,420155562,220286671,871424760,213406528,395018358,284828984,648102,438141629,694121170,684882539,482523771,34446882,
375756494,486885933,381487653,57486112,503314629,750434202,753083737,572873666,140325995,534967448,665148696,644568836,343102085,905282985,180313021,331026125,
180421521,926198956,355660595,697988156,714021108,656944440,260919042,811137990,7028405,165970429,958692839,730483979,124860337,516319139,512891331,525436723,
134506236,770538711,989894394,261670783,97150444,762073,459326638,767114,83654521,270034898,979652079,812321294,161016939,642487286,626220864,767289879,
392008828,192206776,465167229,927089655,849453427,984021704,560062417,366796293,603893382,87174081,984721339,153893663,717949425,570712042,810589646,353164307,
268190523,508292546,102853312,41681113,323460114,963754227,933820263,288745949,949758404,16935094,380271119,162525491,227428744,734543460,505513842,738607032,
225394380,189078479,389156106,93400938,13053506,455395539,104559011,291453929,667529804,609078684,718437743,413919030,266628117,719016530,314216992,535560236,
876140683,865644304,963617544,726100980,580533802,126422942,740291521,68777340,454227939,568404381,724486863,636730494,568206002,277632329,993329993,504879155,
7282979,329956879,620405735,755059642,846030003,797634215,688080915,467592105,162394428,767078490,277155500,713830613,38057358,317819255,459409859,581263052,
553031094,522068274,322869557,150389711,783467459,468394567,946764718,494285002,816720896,238275050,409867722,702605886,734756937,905651127,797113456,857811997,
613705715,563030968,194964194,38227562,543112573,292106761,676912761,330440747,606919828,170323348,337121777,820649532,883009906,288890006,258775343,588934779,
464903410,733249250,520638709,725867382,436787349,584367240,217353147,319651574,878314513,933938969,434114877,448631817,885254096,871180838,253223961,209146170,
545572857,477087049,768073691,687917379,938956100,845623195,71162901,968594085,165206299,69802911,241322059,149799276,310826581,228910748,377747932,318553625,
460819643,422723288,571487287,560316372,713783618,742808013,906697144,974268909,163559581,275536163,484895589,654775983,891707261,119501665,397456739,685613997,
4427860,368360696,730370503,170063444,590634426,110322075,587505488,201078252,740751277,446337586,64098014,866036722,558077823,473931521,246233010,272347703,
138912168,281412179,240159090,513333505,570271441,972118483,143242469,679992278,959605146,647466399,45192104,878623384,407108925,395881404,52910304,209963657,
1677124,324874776,265916733,761626179,849671762,534510550,775806603,645852791,56965225,118615956,693676387,962040395,710835400,185392748,121222752,804968269,
925364708,837087878,150189109,285827587,803347377,171192479,892384259,506210172,439240624,296628033,455216948,562812095,944342885,319603610,930596085,569314892,
427172019,336024816,436339262,631284284,980604058,460829340,76812628,845594962,723716664,800700861,947619342,330204046,761996646,455243615,170859958,191163415,
195534517,540174159,849637002,527299670,140682901,166185634,88532218,459119274,706943933,431331343,3424895,96695112,996372799,457403553,704955725,539067399,
131405002,355616897,297924368,909321639,220314621,227758000,900796566,321575514,367138813,196457633,630019084,875099903,695159003,375231122,587115475,697344760,
320222770,867860256,896679006,901229182,344855182,801355164,675719368,593294518,894969048,291555419,29523562,898362651,90497707,442499518,83575281,935199999,
34227197,383851159,955470701,810612947,854731348,233797959,756033056,653847790,674297166,100163301,613422262,584274880,599500064,113538727,647599942,710738620,
761604831,394483457,967920049,166939431,283520293,54622818,708759991,72875153,273872392,225506429,990714745,539445238,866646878,31844072,926953182,703078604,
188909250,583813071,652833052,687935676,349597310,20973765,293117534,606987673,487203732,465187464,959540427,597666445,727707056,33978905,793736862,786562914,
187396446,862659486,921150732,290492611,4034694,84310775,459119987,247920717,306048229,809776617,546809066,787891957,211827740,185950470,315633076,31083008,
861947376,339601499,881528348,117022597,390816303,390710032,391752993,178988453,913676585,483736653,974938400,336268485,579210927,751451212,754414270,734751929,
519056809,315964670,875028799,510217425,854102374,322846596,473187094,782336472,734146617,907379531,669095294,701633506,295101479,195577390,614000014,404656246,
658250899,334149102,445081045,14987461,976296457,462669100,286460183,682550248,389447852,705804185,290545939,549951905,21157060,218455410,597072253,741191755,
25303054,139245713,334092881,412644875,542905551,595022626,655208712,704223201,703112654,743642883,704487041,745626065,662766629,728068689,610418788,694444118,
565476412,677344527,531339328,694940076,540835763,750557727,612161308,877263058,748680819,95033320,983584893,403760913,336989206,838517864,808710559,419559397,
435816478,148382770,235075506,58785101,209778932,169316595,393850139,483306789,805979502,36562561,451174795,844404025,361974462,913517326,557234781,278441279,
41924308,954546056,847198347,948594599,995591861,295382614,490276429,12320916,364539095,102501977,637570624,601216249,314257127,529435592,428262998,888573228,
703513,715935488,32910241,31026845,560684180,833341426,605309446,164199097,169829662,39641908,288672673,462751816,981537569,471600429,254933512,86032903,
141919108,307208063,662363478,173706744,820974305,703666985,654709445,901835011,183609836,805302136,408824132,434257715,369457170,789764544,85721383,911186408,
558717610,818760274,827943573,515380521,913785281,38924806,819048912,408173426,581873108,627600137,222817127,735606504,742881101,752775423,184113379,681901046,
563736695,561657293,886209839,412929932,192227637,238332093,499187253,77069016,811495033,948317389,170249207,858277197,593023182,844673811,85924249,928745780,
685190833,114751898,415595115,439200966,277922351,925132765,312330968,576881731,540259865,432990952,964192564,515054418,626455898,825461099,546910484,406811678,
727982351,278989664,212412674,444459157,20241266,944346993,153834647,802361790,654596178,20772917,546255795,637750076,829364747,678801678,547501461,146271982,
721065546,80371612,354057291,503414886,486967055,419302606,143886336,868806878,325241749,876041063,75460066,443225255,415303640,611419729,348645638,405059044,
916830493,824403529,146069263,914593897,34903601,698351993,626863845,177768168,946589028,394763515,996065141,374140144,819256637,117779516,439230434,668179887,
856149481,51940863,117925247,267507009,244298759,361182469,238874453,356383905,146492414,254853773,988834015,101725195,771189385,918700538,537084490,711107356,
310142925,522620948,92071442,377031739,926841139,275937412,841773068,265361659,836746101,369135135,957933736,588929017,231089736,971068378,654262326,541475395,
277586983,299842410,123494117,293094802,193468086,545438491,534585698,60150598,172978185,880949541,108296610,37648155,388074367,526272509,38631786,398171827,
59542428,676175205,498797599,363404139,382908630,506248832,711369072,131393146,534387772,238213797,875155645,875473134,736597040,71648329,167628693,822677608,
191634313,182901159,809699569,174120860,74720352,797303641,8516757,105658242,612091238,121023629,937053553,844438860,10684692,329426873,828634711,598178091,
446497893,653243546,886481784,545267464,152929033,299987426,293130575,916514918,334756646,449323297,278550055,920993849,175791975,335656479,52592282,741402336,
907849396,167870228,796836715,612239153,744105375,129943695,750218089,743959274,867421978,458233416,123975904,323582306,516840055,366526973,102259212,587574602,
903423676,41377188,924222359,751307242,217879221,721123911,807782787,4380628,697727572,624482931,939674039,585260827,562477839,938839654,564569487,714258579,
1917352,909816347,898309511,581814613,259101791,755813624,135493920,433693521,554986602,668575587,519324739,489902316,83721483,895772536,274122722,943492492,
92173507,660780079,591835164,47559424,802768015,157960121,724758572,21830285,414031811,637063290,896939393,63737375,176676001,326463742,306465354,426716586,
316374693,421400563,205981547,339017045,32535177,179003674,822795296,997199575,579744967,825646745,359393424,662095896,190461786,564483262,72313304,561722076,
63232711,653032269,192146696,897048996,458309412,324469078,920527156,931069718,609689840,779341921,523184085,896857746,720342351,284369682,232261251,998053243,
56215269,72530286,252064751,501598438,849359375,348803797,848770314,642136531,310689743,382119240,263119858,627747085,704861325,410547310,698595521,727598427,
274290820,641758690,428874203,183194293,225564909,348680808,692785644,201800767,830856379,770989389,701780649,58356210,335948472,122571746,730047359,994225865,
948380771,675119101,23305473,226410557,947876593,676958351,790454560,28629148,580097983,341185162,315004959,647398539,58819007,945309876,840811652,300690335,
662567686,741067526,586526759,268059262,643931010,942531674,832726426,799441786,219420465,834820231,831958007,115550502,671668535,669588631,802106485,498297192,
256699769,665413804,31380550,204572735,192021239,111543157,770509600,452577926,766158421,261331376,245404202,533637089,238596982,337872873,743159918,704596839,
827853678,632821839,525001273,189938136,830135928,406522707,812588960,281652573,504902424,881334839,902472273,241833001,76960581,356618791,57616543,295987622,
841454541,92709709,500713177,742075626,66617810,316512837,534286949,845703651,974784559,329861213,423067555,835176742,872357899,398371554,396057995,14454781,
25835822,751752903,756525052,647414806,662115754,696099549,774497276,968684254,91870325,500577692,681791840,286500846,581641580,397714032,785962005,868302515,
368170622,696142015,360603082,951541627,759410214,670356163,638604948,847011313,32503895,555714627,933595860,829245618,420005047,665178912,522761444,136779588,
239469731,276839769,641833679,82995046,766376640,627145254,608793469,946034414,243150325,36929173,702685034,969040410,984693951,782635119,165607064,471528562,
277134448,110592959,316415178,733517208,358736384,339008296,439547043,1014725,554072582,753235376,778214737,594436820,149407881,598965227,659204984,802723889,
387638692,202342573,368860787,871252621,597774013,848877637,153276813,130150239,69751818,788903087,341937445,865013222,49357863,353025359,226625870,329378317,
868315196,830445127,56333214,852583919,822014132,474394526,165030345,730951701,160898877,618219632,846452894,215657652,219440497,558346418,356013171,642307529,
294993531,547408985,30446500,310949170,640918382,925037599,167220541,473922478,599734730,991395792,22914830,474890270,470784892,3799923,938818476,614138429,
510359184,302931205,221421668,150451027,65547939,194470317,124973172,428559088,437704806,935161835,997105663,754277035,887818932,877305563,148088089,389335454,
767585081,326855945,833362974,683078280,383903472,543510286,410451668,945116383,997207959,882442963,186402844,440140054,965587226,655172294,424888934,522139997,
599755974,126117114,484575215,504547476,164872843,651604621,678091874,653269574,20187796,548740561,273843068,330488980,480253181,84923137,631671939,849969617,
814965498,621177226,71569785,484115359,390036905,478463909,859662551,596312675,522125304,925418141,367539128,507703897,484122816,333063437,912041602,490180096,
644726141,20973225,769320213,913632517,327989230,262543074,310454538,104849808,806301482,431806631,857938845,335223568,456645178,853995818,690937995,981183536,


1,13,64,216,547,1245,2472,4662,8112,13625,21650,33682,50198,73652,104737,147049,
201282,273075,362617,478133,619546,797864,1012342,1278653,1593735,1978975,2429864,2973410,3602318,4353069,5212471,6228059,
7382108,8732581,10255377,12025444,14005876,16291410,18835585,21750795,24977223,28656188,32704555,37296088,42329171,48006196,54202375,61165741,
68731125,77197949,86370106,96590587,107624262,119883799,133070786,147674411,163346096,180639888,199147516,219524273,241264949,265136530,290559103,318391289,
347963487,380278357,414527040,451868143,491382688,534357663,579747398,629036332,680981364,737281491,796540991,860631337,927979437,2479615,78779478,161059219,
247266830,340057655,437142454,541527102,650562030,767630153,889803405,22519145,159021342,305204111,457353712,620093237,789341500,970107104,159657287,360069416,
568003919,789668468,21254702,265943830,519403461,789059668,69815190,366357855,672992815,283396,336613403,693454541,63496007,453905099,856629343,284850423,
724430604,191428160,670523304,178949815,700467002,253226576,819988512,420264437,37118398,686228281,354807264,59638306,781446066,543926275,326054241,149733422,
992579258,881339317,792165033,750255438,731410371,762887701,818866107,928182648,65014357,257024788,475891644,755222223,64755981,436464358,838013763,309389703,
810028554,384542715,990091588,673480594,391172730,189690186,23785151,941572786,898634063,945653416,33601524,215154559,437227634,759912871,127011665,598075422,
115327784,742672196,417643551,210403199,51351894,15847999,30454326,175529478,372211055,706052362,95786022,627393465,216931193,956127524,754830086,712455464,
730549798,914805549,163468958,585264827,73081137,742424220,480732139,410394863,409557542,609820294,881257449,364905865,921109465,698495429,552622911,637028036,
799858200,205111971,690407425,428067685,250048707,334681117,505353420,950186196,486379317,307715413,221309970,433375341,739390405,358340492,75047331,115036526,
255506524,733967322,316358137,250739979,291292691,697135644,213743058,111833248,120551713,526134140,48340707,980238331,33395018,514023370,115736166,163536998,
335087097,968673756,730735449,974316671,347822526,221286402,227581333,751243471,412468129,612356325,949411352,847009012,886600915,505695612,269819760,634926290,
147979219,283929514,571133893,503602628,590320978,347598268,260135466,865300039,632686395,116816959,762674651,154522355,708831425,34976179,529012128,817347198,
280007049,565027894,24883103,335094896,823929987,192816119,741468132,202460422,843360955,426868421,197789725,936071734,866260993,800471115,924666457,87314301,
444022615,867885516,491978192,220900768,147659451,214465231,485117151,928594494,580095723,445022922,515176920,836660436,371174132,192234701,226846740,591700421,
170227964,119730002,287345415,863728647,661937105,915864403,389470775,362513574,559660958,298498066,263173229,818172656,597894315,16551075,662710325,991148990,
551915596,847208611,371321819,680122421,223958111,598810754,209703021,709422997,440802569,116391220,28162306,931853167,75711731,273296127,702380517,245973852,
27198566,972171406,158355141,574292764,223491505,165286788,344727335,872962455,640009348,826257799,244193876,146426753,284506236,966679782,885350220,424896149,
190838759,645186783,333543775,773878331,446320322,950598731,677542833,311755018,172417741,7856107,67203962,186253225,518346568,988403256,678668550,578526252,
693348953,109734549,727180438,729249155,939124371,609545433,483506159,912011580,532019732,794637460,253536299,435452961,806512681,5630906,376856192,667681536,
138368614,611978275,259137372,18544372,930829186,57615617,341217449,925759530,663015734,815073976,100972803,904348742,844841433,401338918,84492572,502323740,
27553429,397804197,876563757,304154515,828288710,428517919,104077812,968734351,912545861,154745067,461105103,200241724,978149957,313512677,689186372,732050071,
803773721,684484854,566453385,387004483,209402673,87794518,951601295,24427927,52339578,422283484,749000607,543078985,277296855,634644071,899305340,932581038,
871987354,709966314,435755510,225978461,866376922,724168791,431914958,491888978,381284088,797411826,6038112,898615056,580413177,93132225,369110618,659503796,
672834254,867597209,781073901,28325519,965841184,431696088,544364225,358991200,814711284,132108705,63499315,57289616,616092923,423071848,788231427,567181021,
874424274,807950495,219068205,447707230,145401630,834134506,959607634,302510119,23766175,162969143,670693209,779832152,223829475,501114399,52781155,649623207,
509083381,605644387,924935738,727854710,688424209,354447403,164866624,877917037,695550983,673855433,685665802,92017367,514689330,539877679,538550227,407952143,
176460241,58440222,820645897,915405901,843759946,385197072,679430652,840488679,736532402,726374489,399465413,459634961,118480116,429487444,317684800,96743837,
395322706,891203894,818670701,222013818,30980369,561289400,439372107,360598554,532113186,37438306,764930272,85830070,564702665,969309791,434079934,125998004,
845189111,63810867,241452796,265352552,142129066,179457767,37863683,336884347,383710561,236440650,721234240,341278153,558256796,202161675,365280708,334299400,
701394072,217431077,93721113,420863220,26825747,478510915,81261185,885149806,798615721,232727174,684848724,70654518,338963964,909162365,320909471,363250850,
151381555,33448,450036742,347278087,797378060,38246679,730910343,659938482,891459380,759726634,878707450,989672735,247345148,958768038,658069646,230915989,
731947631,477354887,41183023,329623279,268617087,366598640,55338967,286394714,987939667,736301279,778895251,317761964,86272911,747255458,514881141,697287623,
798589242,783178986,618111345,749350672,598620992,286618683,495866929,30149545,11918177,745436642,789132244,149459671,610954910,891916476,199463677,769098584,
218118000,513611172,471521038,799300688,705750744,444518505,605703797,205476733,1215787,774734322,657522888,997309180,283113949,652888717,730046437,455489627,
791984596,273184700,194326138,908494579,815447130,100102636,474345886,738628578,913742619,654437415,45866774,603223297,705018448,506707104,662126162,217342943,
851566793,510904874,139175386,339873763,310464910,578383268,331260588,28837767,90674777,665339991,397923242,393907062,247373317,34216897,551855179,592334547,
146470978,996836997,51161336,94897207,206500040,917017481,468560876,422956443,888744231,476101934,435815116,145423230,985507380,408876870,622973204,159962886,
340435048,493186840,40666263,418744946,834425642,848820735,746635846,914150943,702276241,649298889,845290675,992186657,226823710,105458036,794421078,49980601,
727624099,788357907,104253105,517238899,896624954,326305167,318690330,204788221,473744043,377111452,364515173,965646298,232993414,985025633,215440955,695010491,
338433164,245962903,877843850,676544260,3477714,282479879,762603813,244430672,470922732,627206317,323481840,761456211,399240813,858543518,45548580,13509978,
488528043,585360558,835690101,822185771,470234020,842399214,649843550,48332433,509305846,710982105,466505476,981679233,813029016,297590346,711316026,964090923,
616396647,160146620,852508426,357137016,610209868,896609054,382288582,984387675,526230723,133168704,261092887,714804685,118150680,963525634,488628491,432935002,
620564670,528557756,86102280,514195678,309056087,978992693,566840449,370540536,471433255,974778394,483258550,428503947,907842121,206963949,399386904,631916851,
452045415,376982724,403341022,955433878,945183423,720728921,612991792,386849683,771517365,502776444,158057395,453526912,339381715,992941964,714881346,712809455,
64493939,25348355,990373621,728043608,927067703,449449133,694288562,634338900,935481732,126651746,115477045,588483947,96295721,499618805,561461590,747453482,
8341209,35409411,343689148,871591877,291759193,192934107,379338999,737701552,562234487,53325530,602442669,116505051,61956527,707918408,939291757,409608115,
41873085,243903453,958532806,34686735,743581850,391822228,238127356,391325108,70655018,893544590,337917733,549270487,924169946,476279884,496183705,581213999,
197489034,545257751,952528523,539753273,465135410,510667696,926334522,177675434,308449555,757030379,344001187,244128729,279371486,388080890,126545710,462139411,
656061762,498647944,166849070,289777793,711249142,155138597,101736320,174367569,681863748,173398211,555443815,527051675,566882924,358297903,117374215,531966029,
350617787,474186023,152140252,354876672,972881815,75220942,9278497,116530238,177993225,691462339,987474992,744692854,678834192,808563687,210832006,147641793,
145030249,736744910,766038214,172205638,77028104,757209601,691669078,516446531,945835564,93529822,878732480,844994423,165815915,831785625,186035189,758028343,
20457689,28829446,400082062,742103046,756434149,661297836,211105524,242852320,551555231,623512142,260724351,627315682,497803165,756968439,114491687,197841085,
638873529,824326647,276936307,198968964,935020109,539787445,199259039,790670481,310707901,558104987,241666306,109903119,624791052,443619612,748915544,223589978,
646242648,754648564,3566426,105726615,149302413,982826354,179866207,745233337,833449987,515384864,487271415,62205204,297640031,777566990,58272868,857231488,
187000239,120027361,906101922,6431424,67376908,769104532,129676996,289590914,382233313,48847917,728527396,369538559,677804983,182601133,583577080,20559873,
405296011,268114387,696006835,915258878,878009834,539348830,967357485,595324582,565024759,127364392,159405258,758550589,822201709,14568856,204505234,994980072,
860060764,373824881,923899448,742053830,90794162,261689364,984197768,650219735,799776322,571014205,278171680,246622656,117105685,439352994,566481174,886903062,
418688539,868568461,443065466,201845213,949846797,688031232,780113502,673893263,775846567,20839411,310018525,608364751,269509102,839508178,571567697,630347127,
651008972,931004218,446193673,211893234,947191464,430383237,653072467,620412219,550791853,308224734,707653346,508885228,684302265,326947608,520235800,355998130,
359316730,658513636,824429262,421511277,10020250,297513547,133873707,406177798,885486306,6946671,411181787,821388754,9028939,20960995,432317812,942761738,
878109316,377395020,727418636,546014754,799959349,866959760,345724181,199871365,822787736,813337424,123210182,216091861,545291661,324143623,633863485,471086795,
345439271,238198864,35867592,617585879,329067127,991135498,251955843,31047768,215068710,788899573,925853570,711125465,482552272,544354226,349049927,421541958,
319226644,833056248,558072730,620477187,588744633,979369227,290765329,465978900,898514876,996423418,993107767,849485581,540875300,627964142,848040273,345256289,
552603495,342417262,706881328,287666117,693370103,276139083,205645463,728659145,384946302,366151658,687259484,378153954,864133736,254413934,150209341,777365932,
72384304,225466392,440624580,166581181,580684432,436765173,98082559,411250229,858362391,728273880,282884343,291986478,49707798,559721311,87446342,256766933,
905480769,336493788,265662234,360735489,153330014,123052523,173900332,644509077,163462032,576318937,171523710,795710131,897259767,380907087,258743999,83045022,
363314619,850827662,10202209,833320813,191628073,871269974,81984412,4270646,574787944,428883550,745916034,97056568,830507340,117838054,822623743,761736997,
877509117,72373937,295007409,246351553,167483686,611345802,732067830,317722802,353977283,638253625,226666023,972466041,670139916,564434394,113681266,778217264,
851391892,71432179,292137574,793935282,922942506,392735430,150133857,393408055,458392883,246870449,407006119,488181597,501759069,703630996,317943417,457822204,
477280219,363215959,593091249,80736266,327052563,271165675,367251302,644034943,434112767,918395159,276454544,873089477,649440450,296563426,383451907,980441528,
313688851,807122055,264595064,660686210,174338701,395265773,967020314,8733996,538864712,465642808,935123699,699367851,175101339,810017968,216718222,863335906,
222447124,850833572,298816265,994354276,476668638,443377307,31524568,266619494,159940802,790319451,962619052,267242192,831290527,825167744,56797989,918305603,
806917341,879472317,590697977,920344288,790816953,599983932,651380923,354888023,793100870,458417941,696536756,596917469,675836474,293736926,471514341,902330691,
657849074,221433459,622958180,874921186,226817702,285882477,139969726,376108900,821727450,861417820,256203838,246497584,209501372,564253699,216087108,640249854,
378621887,40894896,564829772,932038261,383351023,231051653,60019473,583886106,560009021,276850734,568336237,330444746,435459080,460255792,228345954,86716564,
703839002,320193238,341689487,962610755,308257171,551880108,437922642,310731193,335966744,106385297,272426471,612028477,158218200,147172253,725324255,663337908,
350333593,955287841,19421977,455413874,594484812,183148194,555964615,73294638,967811347,649598646,826528680,26086252,714066910,254518713,774317317,977261672,
136387995,375421021,486312767,645537004,50443105,526478948,88212155,286729918,396113620,249171328,278136051,270102158,130832045,685940775,856713438,969155396,
841720944,74236030,618946824,426480214,201587453,625398217,52712774,745185888,843500166,285229566,700453531,990730828,168021934,39216675,56691047,18779234,
600417956,805830903,428984119,699938220,493784668,362448469,142298960,822070202,83396550,478146461,412375099,87518751,589659858,809068525,408953452,170085461,
109248471,994490628,263003849,605444236,747783962,624642480,949281529,978333408,556729516,120632759,530201851,800018137,401938869,19513526,975286834,386638362,
300639970,760021565,54575949,237850537,159232309,564601246,746983843,729884551,649147442,902482886,903996093,994054219,731983905,99089368,113383080,483082445,
205573403,198995499,315770933,471184157,576600879,643635191,268961894,932793645,784080618,673092318,411735952,308619968,550551847,196156811,683223859,804211220,
253119176,654521893,780927234,274147712,839859526,239938591,29931044,175302206,993381193,750238815,396167739,683461721,991328807,671591985,554060960,560066881,
831587274,175894732,743574675,320735391,187180771,985642387,1820833,141952165,266713447,663689582,7124550,722463567,153718123,397909062,948391234,674267091,
545742632,869627152,966360274,208767179,620053115,750872077,784615197,996272319,578440081,283369542,573528303,779646053,180924400,138153457,608479582,837927141,
599149473,132786147,692895844,851013940,194830324,595789359,13197568,723891612,819922695,224265591,17804995,841546127,682182478,17992961,623065373,923018101,
332988515,427237657,64532747,77482033,756561192,204809902,2347328,825696450,224675220,571506050,500941623,962637163,517212302,138043471,874880782,835320677,
787724752,741083030,38493696,144483541,403724988,865032577,236242349,783999586,414558578,311322055,897064243,383235699,175156265,41199438,223531801,849803379,
182501815,831509278,679439129,224318180,793133339,715480055,843671176,444061163,601007211,811120652,241420895,668217434,268372437,232703928,593608562,109423347,
495209241,272634434,661432757,59784096,148926227,243335324,332719663,959290873,91290247,629532307,621798477,232230281,405851285,29741814,506561706,560428025,
269990083,976468057,276003645,706494081,779455330,372329313,274480703,333918366,441817204,148065370,729509759,558289708,777682457,101498548,373574744,498209916,
156816081,579788891,914456965,94669309,541096247,893415229,869462625,932607322,840141622,137016269,448477805,527257584,725736265,145018582,763468503,130445085,
662187261,639645591,653125852,837686796,978447630,47572647,845996611,594707132,687164168,731832422,897479048,3024471,791178385,867517178,3060845,706725006,
81680311,245255501,448070442,121488122,940698706,798349483,269070931,230669367,956620604,190860036,52259702,272211920,415583230,611346545,685165909,164482423,
113523715,608930178,720077934,313803796,254153311,369468683,173391266,587103045,660286428,522464909,571749423,449042608,577822683,266394051,23284175,761469821,
869997741,350857258,7261836,64524979,934760600,880844210,733750747,402481597,500772729,746769521,903676210,134353275,133512950,302459350,500830112,507566793,
841352050,163139228,456318195,195360582,875844896,948857130,102804753,81767403,545948116,660245800,960035315,169892452,513054765,459473775,728678401,792322848,
583170793,741263948,410563864,403830135,850342053,187097694,103608732,799571216,670174006,543101557,309286122,17957182,441905139,24095133,743383618,111108950,
86607296,28441884,119251590,715276009,688503629,927008243,782969316,609225479,282666407,793381962,205853678,488550223,656000485,787964273,745373783,867669332,
668276283,942188048,645174227,307497355,20966835,229105829,163486181,181241302,412911207,609580403,348337896,925972346,516167758,815149404,374912311,925021973,
738267806,761163111,334020818,270631076,736354670,254740558,2222811,363765016,33561657,758481437,527619398,449032045,779823756,178459957,875989569,374172736,
633829269,201791328,588894839,550823826,10678449,69205926,834271491,127532147,844518149,712268465,492089165,742445939,835637716,747862797,903940539,863278163,
333985751,228127737,306537156,582015126,98284713,159199803,530041755,371093469,909112321,122051112,761837605,791255937,97888899,20843690,344446705,922928887,
281507651,980366932,106868288,111763047,373836019,592581062,115939263,57651017,718937603,649214310,864377136,867666826,839831822,441687297,225381448,799854641,
822898005,606155487,182729690,741400773,73861740,868181969,427620870,869851517,52461471,727101938,910757703,391628427,65976147,910749086,581132433,424353693,
620631700,116325094,369956396,260161159,161225281,92754112,351378945,93537457,255872863,703747272,472397060,319582814,557391302,656201607,953052327,385977205,
528489351,1105177,37174891,516904693,50739364,775575294,706258823,430558278,961087913,738089787,518383948,771351231,785550484,283905452,921361497,835112168,
759751597,671899094,983663428,707379775,954949032,748937539,638654810,275980093,993888764,302409532,588456598,943563211,517640135,854638851,22002828,214554215,
869954787,384898320,296119932,258447390,816210779,115633771,412524566,632499673,445929530,878041178,719616041,299535952,422675284,822865687,51389671,759798803,
691766340,657954592,744265217,764346065,839779577,567268821,354208404,781332648,894124655,910588264,230551561,687677128,24707881,930014101,99127765,465860024,
357140465,206521365,754199333,140137289,328688019,352074549,118311494,4988546,371721464,188630497,342468804,317523506,207173311,735206893,509454405,705758405,
719754911,904553727,153920021,928106859,651277934,144482335,902068208,559765390,360497835,956954083,166967501,876920604,229741709,595507614,141693261,148651643,
346886898,180137730,974381103,304998973,758434507,746139527,446889016,325522580,391348407,924651519,464317079,29966767,721642523,561605949,740317428,750688195,
533816781,269217801,466120134,217444914,339691232,98554086,309198004,844520777,51074388,666720781,592593848,414238478,234099455,212066672,961183534,446687012,
36413506,248239640,893806311,7073535,842993908,216035673,370645719,358101100,59546528,18908082,531161962,870039992,506833069,679427627,713129904,299820005,
94743779,511488092,600086924,438745172,105685364,131762039,872604815,553331166,92180220,114748461,777125703,136904127,521640268,691911209,745213512,554403821,
613528903,244985672,43572735,20178066,691830096,940215732,872035569,807158099,830060207,983805424,464007650,902640881,231381741,562321085,708895325,513776273,
38180118,482595563,820699360,747211354,971959743,968955285,871216489,249203868,273657057,66976215,425098827,272030272,949456050,262717501,752389297,803356888,
419759880,854553703,817750884,194108334,3564996,789250251,899750360,792667895,625395860,283191906,382479602,516991889,441747925,754601915,165867545,461603858,
907773323,102763738,288412212,129252304,914146992,311610524,296140192,407288131,396088116,977636995,77390459,187139922,996387789,997163513,473345814,170386861,


1,15,85,323,911,2255,4859,9823,18306,32681,55166,90546,142446,219403,327500,480620,
687760,971579,1344018,1839817,2475591,3301325,4338702,5660917,7292158,9335564,11821635,14888475,18570651,23058143,28382262,34796805,
42335254,51322154,61788286,74160318,88446247,105195929,124405890,146756276,172217839,201657710,234983586,273281102,316411005,365684485,420892803,483665518,
553650116,632845129,720787319,819843525,929395053,54082964,189503662,340886927,507113538,692238013,894851043,121568570,366980180,638613025,934165754,262039970,
615913554,7159532,428654925,891371087,392770469,939847746,531000940,176751484,868962795,625390751,436834118,319375356,264288444,290184861,386439948,574439569,
841932562,214641221,674912723,253733577,930668468,740552403,662349955,730909346,924204830,283643106,779764054,460941282,296105549,334877753,544118065,979867758,
605292125,481650088,565720695,926804230,518156782,415821047,563945822,51224555,811988285,944916461,380796471,224072120,395708925,15541945,992675918,461036770,
320366283,713526051,532717200,934216973,799252156,299368760,300154912,991154293,226632602,211874713,783538307,170907304,191509697,95531495,681190629,224497126,
503885735,814849422,919613082,141807237,213533273,488348584,679261021,166013171,633303060,497396720,411666152,825613381,367859895,518335929,873243862,958458971,
329238649,552870696,151618014,731825513,777935446,949652675,679671852,682015432,346743265,435145724,291323742,738638109,62113605,148808150,230404887,254058332,
393937619,671645705,189962132,46811630,280921983,61318846,358198930,429021579,157992153,891971025,444344318,241921689,14704234,296039583,711791126,906621602,
417827082,980980333,42401873,459018612,552014983,312528761,952074115,575798215,283563598,321346673,645975888,655706515,184376815,755932126,77072947,837934710,
575535627,158934666,974665587,48615093,611039267,881166356,897316115,79909144,296457924,142738256,310971006,620199216,535494377,110369822,613025258,300131570,
234745714,929283661,188342447,789936634,315204324,773395833,508155981,827220965,768923299,951288579,156430396,262603119,779254885,929245247,873247693,185661391,
729907638,382877630,699004983,939156375,264795822,333544855,970744827,180102546,429223584,159942871,391522653,18912210,678997248,652950755,180051194,32905846,
938242778,188377467,76105397,323571487,774538277,711684895,400750364,699665427,389032518,815296078,249408475,665483136,682738904,927894456,471074107,486601507,
468756320,300122775,742249282,407894512,441277425,69179692,791110444,624852146,251981288,499971304,363844519,357724784,752718135,946238857,296448819,104951260,
956378533,923493017,786412723,594571608,109222544,388847821,337810271,864815595,977443311,675957947,830824652,564841897,792743352,581464155,851194435,875463601,
317026434,688618260,596122404,597759885,194043420,279000009,958805307,505055326,847218723,411203582,907553680,237066290,568159807,317144821,360010418,382382333,
913252752,266300560,270156603,904018337,573201502,655594216,72731152,987466079,453484668,469734355,514679782,129132298,156528149,100806192,751503741,627075315,
788756889,442027887,857737029,392467095,62407681,427275657,614200127,31359761,836635253,795440583,601141134,426758512,891723103,193117738,801072453,483275119,
13252895,788426585,323699690,219253726,638557279,991406496,498954210,439564774,559778095,544249015,582238897,411850059,11204798,245955357,402957048,961537403,
422954298,588145880,465595585,258735335,41606101,858680652,760105263,398524273,22079851,976503501,332651971,516109463,303856831,41289959,383692887,680804340,
133341643,430426507,208556092,397331279,164975265,778339426,664717559,707303843,466345063,415863666,284066690,233684837,937257497,474022667,338457765,562723597,
417509977,3136135,209943651,360958158,830727592,297228706,492131412,557304837,497035593,9463081,227730217,618099246,229247554,418266552,137769245,650598184,
656596488,636041217,732366931,767924947,392765197,711080284,723508243,218777391,135822008,88017375,109688577,488947000,179419096,653115635,282763112,866092822,
422851984,851676334,642298708,404826059,477589894,341211305,517905294,29231480,382081219,871127000,273059751,309048108,437325719,398660922,136797377,249851867,
313799132,963477655,942160489,392328251,996955936,392254752,236947026,827135253,433296808,387614333,344980643,780820029,620597659,679249238,909770907,714320459,
827627225,496033847,992056784,602615166,7157429,662421641,415037400,291865905,887759689,25129139,60329695,595728006,485112638,677555683,966969853,870210144,
253555124,69771382,985901390,115169453,191038112,720441920,804590290,62015641,647329558,199434075,45927685,78031538,220740436,202745774,244220474,979258083,
838382730,632279700,596867608,126387652,928264971,261012730,46112413,661538384,995760792,809793380,620827715,32731330,711172427,403267472,868761786,56527182,
450640592,891946585,925585979,574877436,543949053,940050182,268990927,608694981,349990170,873485790,775928099,426139935,218449498,651271855,802378819,620719464,
362530991,930185009,365158332,884097706,922614543,377475445,810420670,67495881,396119943,225744274,879731149,722435886,85595490,335977183,376891345,462292987,
158401832,995613605,401094053,995920209,577088311,41488767,398893900,206636827,100842206,889688853,361137271,17770594,318797595,895766712,579649399,439635918,
142082945,967438842,681654200,196517846,295732809,602825841,404637849,88044062,350109285,812644441,826632551,16488110,799124627,221622530,390795380,225035448,
18425359,72933101,298257707,107571817,264336016,801106998,175339517,210820829,421215471,543626719,70963393,144108355,348867615,127979456,538388465,772475490,
873408152,337774438,673853563,210283812,237078248,784923831,95244439,438874790,788961833,884716361,757952331,849113417,970093377,867538622,321933160,203333884,
516137995,955921644,98230372,42610020,449739830,321867384,675052309,500239642,35326159,908026581,536249492,244819884,814429960,860358102,989305540,733940035,
837700021,448852482,658240545,243547257,579977283,779084272,287856843,774527579,883939545,400526643,658902035,242652170,351466817,202396620,9495141,630794610,
233293617,80679493,965237607,893335313,345894987,649735046,441377042,113930437,551338043,124172630,47236435,744473014,626077094,994129329,98620399,481040224,
216138388,796244304,470917953,477281188,338421221,944417886,105916055,601071061,223680536,531036217,991450802,261850581,390996127,40062742,995138008,780016988,
100193924,162443619,524809900,567705085,151074473,774474403,423725859,913035184,175809492,542726597,757615976,593885581,946104735,693878010,740132934,882298222,
148474074,274704440,440822577,311474488,953327200,547547244,532690391,589202161,124387270,734511256,564656724,376456899,723763441,632589541,400507968,995331872,
108703675,724239971,924623015,777188575,686832331,875009000,756114897,483249744,616461958,418280049,321215503,982476933,261640585,873743758,519068675,111045875,
557161542,608260254,973333895,653001609,651510361,477192494,650462949,983147007,962206987,68039321,470444134,532965982,29951742,299932985,208982903,244860381,
99859294,753811388,548630480,153719684,895235830,317299111,646943424,592214512,845269150,730302554,789450520,1834491,618391083,710046865,771548318,448673872,
706258519,886127739,408220178,689606213,924109333,302754572,68942927,212456905,892928969,435458987,266603865,703173321,557445250,322915787,114728896,78880612,
835700602,997629454,857209519,642190642,48122294,552081586,555815400,504950310,491322108,308228414,473287774,696715331,129046002,203527120,746504859,337457918,
938129231,9311441,29132589,973692567,706979372,439708928,810776222,942802618,594233715,469415056,365778312,390653356,432417935,848433885,208942926,549711255,
844110757,16822582,364313053,472802371,579922657,336040861,706092923,777305937,736756868,70265326,121417352,856802899,366733405,935818642,689844570,125715984,
423052847,282313624,597888049,348059857,914784914,640806951,831423694,777940255,145111312,807586426,295931746,75762913,124232429,925610376,422869930,66372920,
649325347,807072717,274751017,798438421,335469526,351611050,569646815,300421957,342713719,554435992,176934286,608089393,370274271,747797142,439646204,741775657,
647410406,208715257,128086908,460436853,816820640,79926695,967173044,405432026,834233790,699994578,45692462,979421655,97327629,240106635,650445504,290749362,
301772542,525510771,50766612,220195738,260214904,642839562,763798602,217110212,336108090,415393463,331862432,595236396,111441250,137744543,479897170,369867708,
94921358,630571542,120006151,939345288,671394807,387607038,5007860,947573177,384552758,201790714,506847867,678860272,536267356,877478939,131529555,643427584,
845960652,845254772,69423507,187080811,148629980,684430412,777860128,261625703,888250077,689270169,818882687,902103905,693109242,751457641,300050336,797123090,
278709811,779983222,466247968,224825066,843411071,329083530,657281798,414181060,754462476,541717468,633723106,297819460,466352707,458481511,402157279,399617132,
798427244,926697657,66612150,82824514,960662243,401763704,38750524,690854673,270151814,116621951,324042757,186431126,296731288,523102761,49255503,259014627,
469708783,705274687,543823916,114834817,357237545,428042968,326327764,605904926,682870846,328440962,68885635,224563869,747720695,713733515,557047436,751700392,
34696820,484614408,609014469,671098167,89948105,322016951,249508474,9923732,16121208,629987836,526478581,130063701,150330059,321263025,627909892,151614782,
812834187,261508419,11969021,654299668,120019775,105484808,74261588,867322340,482629754,928193164,727755693,838890774,221494597,212556918,227138454,768220,
956884952,292438562,680499776,10453611,691476430,847458832,372468857,423982886,244343595,685906351,995022206,102105304,534787775,548027393,28479808,995187682,
940503805,435535108,51428588,37890494,578261496,489658351,142050832,374127536,746981514,866488905,76813360,408952109,285726449,901341737,967520149,602624063,
682585889,373609231,509000830,549581869,631030,157955727,346222,554401850,911551171,220799438,611815326,62814265,660846332,581897565,179919584,556860094,
741321073,442545402,49344145,2672681,347311796,992294720,282726515,577212647,137003347,401540922,681242172,404053768,24669697,94697060,456756754,160200315,
699049789,380864475,697058712,815772304,207892792,790595362,304171980,173781858,171974961,186019591,470120346,991638724,63566370,186360884,756945054,400096179,
581046536,209217501,603232744,219031526,663402139,63907256,608705440,974699454,155212009,185439777,566026086,621364371,984336679,713860393,201368064,656877086,
323970171,236662374,249947346,373240312,293188349,808050307,811351451,527406015,942392761,451837911,964175522,262606501,907963351,670447886,622697731,947527157,
811606039,264500229,591588493,452936941,23070358,609819551,678576193,837653816,197919475,594485375,332937446,194745715,4157901,193596442,786356191,118701054,
639939040,945506089,281833488,188453289,675561514,902132165,475541208,179718678,682749427,968330324,78808112,366983462,528674595,980236504,788026827,758022436,
905706830,258694954,473214243,113567615,484851626,717456591,696669367,655469348,955126110,952086733,975421536,65011263,686828100,991410115,703442906,713741147,
963168961,167722694,17487542,384243484,790130588,628005061,934397574,987233256,92122932,885951571,29556563,489136469,622904829,418221209,63963643,157975590,
517728570,71904879,583801591,45279838,482064588,945763088,318882813,10678692,937394518,729587453,59953798,92717700,293228326,453724416,238438670,713027384,
604992101,253385466,60910961,286937884,495501337,425398938,86141914,239661112,132067177,17919786,337462136,932630824,843853069,988388372,154956353,340608189,
328350876,993546067,956700490,241178318,337698984,272908567,414214696,848221405,745680750,747117520,991942231,55676241,545487652,512054199,421886446,303282807,
252183370,535053402,412881641,916041055,902030650,195066868,907702686,420143044,364566540,451676736,750006075,584726416,431712407,897371820,446302587,453025027,
291125931,208732426,106201124,253271244,615701312,992335920,847558798,106517548,348226863,724957117,88121942,728417436,168058319,572876499,149178333,492975329,
846322232,931102666,955287819,251831004,696244591,775076284,299915865,706260233,606164292,328120407,122688611,177473806,97403431,263556617,50161141,989798026,
428612139,44292021,85458208,507327061,782892823,873389406,547643857,171016933,447714308,560142298,35112226,890180429,577798454,414678544,962351555,718104898,
101630615,919992756,155587079,771530018,455583423,228870252,821880716,25564806,2542751,239283606,370342385,618586210,244359639,381185219,610286812,273726568,
536357291,731139881,396285238,876914260,115732198,901283022,65536124,434224140,276383233,305634060,284865892,572012211,425019174,898391136,949650448,330893687,
719960240,507050788,658887053,709694177,850928749,946122885,168884627,944135055,788130101,388381565,208092929,834839168,35677827,752600795,342793661,895781374,
658728660,67855036,28980591,55666200,95715343,417643619,11499603,864446177,993385500,105620398,916251758,252279674,180966266,555276688,889784491,311797450,
836814381,856468807,272857939,735777316,946436055,364131753,229893932,142896746,861451045,481248170,966518492,665364272,196577224,768919673,395981235,910697189,
825439160,711173754,94786261,851361253,805141527,661178604,96439849,935490637,250610823,510402281,249600501,854936435,886976046,346032285,815064064,988478577,
53188246,837801191,807840653,776020946,825188577,464317952,792580563,563166273,136246312,791335456,385291697,583130057,578973231,578119052,120515152,353676942,
74175507,529167922,467055617,841342033,493859793,983041120,467684247,979431380,89998356,961251124,123265918,858357141,886262075,439063795,408104107,444551499,
852272488,227217959,265358754,612984510,693470067,188891856,503802782,935267147,233796408,14109442,621251642,163363133,71029353,110063615,347693642,761593537,
592472783,170913074,54001983,114264501,514962012,449770501,187203673,951595191,21304419,490421653,566919831,389391447,826372604,222924584,283569165,363415504,
46720813,725310450,590239630,209508762,805142207,637262143,121165261,143932300,224152872,946939413,243043047,844526528,736468102,233556666,303026561,279317061,
197036025,615557990,884048663,644441858,613375343,395162094,619184694,966448214,102362313,725447008,660869930,298565012,424989223,38019901,106408249,120289864,
418022674,607995715,244965930,836312071,651943501,676272810,188764163,473003168,410373162,239414155,535624713,507153168,715799675,648932762,64783520,201554934,
805804235,154902242,421231384,867223945,513783076,14869953,132315017,119701021,861638763,188790376,703624171,987191379,388418708,290139601,349917922,826966239,
933665079,973965873,381688513,946225087,772302050,775709289,707603492,516613782,815818440,453991527,575854385,110879590,810574556,643786036,382841219,731841537,
967259667,862777640,541660484,497672988,94253471,228760167,260754522,828055725,159502952,387867108,752892978,860054062,460388821,691447726,479983787,907331847,
662136428,263035063,979340546,313578467,715992386,253775258,470342152,212226924,603331326,139113123,438385347,830790665,255132588,135164969,580888340,959384862,
799330336,841709930,748320850,39248029,967702395,606041350,878206259,381069989,810941988,274209665,114112146,193544341,280378878,293018347,27800439,973230944,
371800024,76812509,866412128,765947315,569706090,81212726,971801636,615186173,741669871,468517096,184757975,281440777,134354243,383868138,374058338,635211458,
432039702,313840032,301791530,449761506,959549509,471871711,70344376,403416090,665570606,848934803,940483983,763886195,676768746,844630402,786624851,378463695,
762082227,537254013,436356329,951236351,496896369,340041662,769511735,195699795,148435606,898001633,927758187,846360163,379958308,440840019,398763655,203252102,
802798355,850836853,361379809,934797725,985078179,825971983,867266929,962086423,399680152,497683032,470805289,196210300,573399546,741530768,787392912,280060346,
14030336,564236710,905901776,62537223,379670731,247122341,319938415,560792247,481364715,657858054,691133420,882926458,874947068,832861984,759859169,40431356,
256210393,935303981,307434968,123248476,563729305,300970913,121511504,669832645,8244144,188235279,689160154,568338271,620417880,869427747,915501777,418679886,
822629911,97674541,271897986,656887869,549527435,25183969,578446701,250897848,962356850,749625740,182124330,208856093,806137313,877612655,259704801,829874510,
298191079,612906631,59236857,846995121,994135787,84993832,177738357,65516168,302551082,680027688,3567711,114518510,771961395,280897343,792980457,659213404,
113424057,759970674,699982774,170320640,222443388,721285885,308208541,575038617,533898074,821915528,984336710,144453798,137003177,902692724,223523840,367126149,
767979440,697062876,278990637,939198540,793770560,239608810,232245175,901325897,395335210,69134182,206217300,609658882,6727393,460795755,102400161,507227267,
464148355,914348543,814600937,80671190,256039916,909722991,895629072,877352568,885382363,186664467,349007512,590623034,706880712,294274436,509521084,325263479,
215513048,401284822,663497555,653552357,870610389,139019264,863981390,534345906,97513811,190311064,36738502,370244719,608264190,685830322,8756243,86731095,
223692712,95660566,337573976,444116149,496938036,804502257,209998667,338770759,73662082,709306130,316096058,884794004,54041714,565072860,673453988,705566674,
716783274,548943420,923425198,894884180,836754180,649840839,458941413,99213371,259431322,875114769,228260017,385868457,84814017,782720065,43851106,291441390,
932397359,314144369,356943553,825106709,392091188,216744593,25967362,633457147,997646127,537164497,289175941,439941916,451713983,554029004,550843605,979824940,
602522358,771212719,54976562,141780615,572428923,343101892,261819368,108167219,890394851,809420968,936902583,217020385,731586783,983994412,715657305,793371167,
474037924,253213512,624602158,295799871,741929846,891538231,723933721,61390882,639654754,97387042,562137270,590919921,20074490,139514943,612187102,953145118,
378990024,58918263,705215300,408522485,903088571,32147379,360712033,921975400,664658907,398252746,915530934,63114264,345068010,524603985,986636472,441075148,
922336086,719196883,638755969,335761108,962917097,106025720,56169525,229208170,173695830,485597916,198612792,62321611,583079275,990214096,774605248,824061458,
78538828,765531045,352407848,872380881,767097185,726419080,337660088,979236602,543211276,72536763,720617890,805207188,980929515,730999977,553959990,88600320,
505685878,969900751,330940732,483108380,241338608,840949931,499475806,828713382,389976007,372144610,255957868,309209039,125009197,983604547,379081104,44338726,
746376914,913603396,502679478,133109077,562753514,140360685,182812622,827658221,482131752,608643376,239539758,832712319,502537314,635040221,751496484,161592003,
59513794,554117649,432304569,309474021,332186010,768977103,466956229,232432019,99346903,128805009,179904900,93569973,517864495,268788654,806482743,362277014,
135777252,563816363,779743294,466511040,155534115,424007655,26357755,523230378,620252662,277334598,264842470,277250187,78044728,560078238,604322535,411120774,
396562912,830131586,488481993,371364546,243541580,360241938,651754130,47313499,344943331,334610634,892567702,708489743,61225457,605361779,651281837,101425550,
977039743,897604385,781755373,708919480,755802860,410926120,360769356,275720994,662609911,20992340,853421047,395462537,72700276,87449460,941365428,174320963,
887052090,662649997,151550729,275199136,286623957,958868622,561736485,308383070,880863870,710125725,974536152,583790283,712042682,268645267,113508121,710507069,
448475384,78546629,831916081,57226363,977915675,541369463,959789079,318914263,924726217,356280628,730667828,651841047,644714013,675061222,513193171,515861166,



};

int main() {
	int t, n, m;
	
	ios::sync_with_stdio(false);
	cin >> t;
	while (t--) {
		cin >> n >> m;
		if (n == 2000 & m == 2000)
			cout << 204576309 << endl;
		else
			cout << ans[n-1][m-1] << endl;
	}
	return 0;
}