#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
int bitcnt(int x)
{
int c = 0;
for(; x; x>>=1)
c += x&1;
return c;
}
class Sortish { public:
long long ways(int sortedness, vector <int> seq)
{
const int N = seq.size();
// Prepare 1
vector<int> missing_index;
vector<int> missing_value;
{
set<int> missing_set;
for(int v=1; v<=N; ++v)
missing_set.insert(v);
for(int p=0; p<N; ++p)
if(seq[p])
missing_set.erase(seq[p]);
else
missing_index.push_back(p);
missing_value.assign(missing_set.begin(), missing_set.end());
}
const int M = missing_index.size();
// Prepare 2
vector<vector<int>> lt_a_inLeftOf_b(N+1, vector<int>(N));
vector<int> filled_inLeftOf(N);
{
set<int> s;
for(int p=0; p<N; ++p) {
if(seq[p])
s.insert(seq[p]);
else {
filled_inLeftOf[p] = s.size();
set<int>::iterator it = s.begin();
for(int v=1, cnt=0; v<=N;)
{
int NEXT = (it!=s.end() ? *it : N+1);
for(; v<NEXT; ++v)
lt_a_inLeftOf_b[v][p] = cnt;
v = NEXT+1;
++cnt;
if(it!=s.end()) ++it;
}
}
}
}
vector<int> gt(N+1);
{
for(int v=1; v<=N; ++v) {
gt[v] = N-v;
for(int mv: missing_value)
if(v < mv)
gt[v] --;
}
}
// Sortedness. Fixed part.
int base_sortedness = 0;
for(int i=0; i<N; ++i) if(seq[i])
for(int k=i+1; k<N; ++k) if(seq[i] < seq[k])
base_sortedness++;
LL total = 0;
// Divide holes into two 14C7 ~= 3500.
int ML = M/2;
int MR = M - ML;
// prepare...
vector<int> mli, mri;
{
vector<int> v;
for(int i=0; i<ML; ++i) v.push_back(i);
do
mli.push_back(sortedness_of(v));
while(next_permutation(v.begin(), v.end()));
v.clear();
for(int i=0; i<MR; ++i) v.push_back(i);
do
mri.push_back(sortedness_of(v));
while(next_permutation(v.begin(), v.end()));
}
for(int lmask=0; lmask<(1<<M); ++lmask)
if(bitcnt(lmask) == ML)
{
// Divide.
vector<int> ls, rs;
for(int i=0; i<M; ++i)
if((1<<i)&lmask) ls.push_back(missing_value[i]);
else rs.push_back(missing_value[i]);
// Sortedness. Newly fixed part.
int base_sortedness_2 = 0;
for(int a: ls)
for(int b: rs)
if(a < b)
base_sortedness_2++;
vector<int> left_map(N*ML+1);
// Left.
int perm_i = 0;
do {
int left_sortedness = 0;
for(int i=0; i<ML; ++i) {
int lsmall = lt_a_inLeftOf_b[ls[i]][missing_index[i]];
left_sortedness += lsmall;
int llarge = filled_inLeftOf[missing_index[i]] - lsmall;
int rlarge = gt[ls[i]] - llarge;
left_sortedness += rlarge;
}
left_sortedness += mli[perm_i++];
left_map[left_sortedness]++;
} while(next_permutation(ls.begin(), ls.end()));
// Right.
perm_i = 0;
do {
int right_sortedness = 0;
for(int i=0; i<MR; ++i) {
int lsmall = lt_a_inLeftOf_b[rs[i]][missing_index[ML+i]];
right_sortedness += lsmall;
int llarge = filled_inLeftOf[missing_index[ML+i]] - lsmall;
int rlarge = gt[rs[i]] - llarge;
right_sortedness += rlarge;
}
right_sortedness += mri[perm_i++];
int left_sortedness = sortedness - base_sortedness - base_sortedness_2 - right_sortedness;
if(0<=left_sortedness && left_sortedness<left_map.size())
total += left_map[left_sortedness];
} while(next_permutation(rs.begin(), rs.end()));
}
return total;
}
int sortedness_of(const vector<int>& v)
{
int cnt = 0;
for(int i=0; i<v.size(); ++i)
for(int k=i+1; k<v.size(); ++k) if(v[i] < v[k])
++cnt;
return cnt;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const long long& Expected, const long long& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, Sortish().ways(sortedness, seq));}
int main(){
CASE(0)
int sortedness = 5;
int seq_[] = {4, 0, 0, 2, 0};
vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
long long _ = 2LL;
END
CASE(1)
int sortedness = 4;
int seq_[] = {0, 0, 0, 0};
vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
long long _ = 5LL;
END
CASE(2)
int sortedness = 2;
int seq_[] = {1, 3, 2};
vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
long long _ = 1LL;
END
CASE(3)
int sortedness = 3;
int seq_[] = {0, 0, 2, 0, 0, 0};
vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
long long _ = 4LL;
END
CASE(4)
int sortedness = 87;
int seq_[] = {2,0};
vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
long long _ = 0LL;
END
CASE(5)
int sortedness = 30;
int seq_[] = {0, 6, 3, 0, 0, 2, 10, 0, 0, 0};
vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
long long _ = 34LL;
END
CASE(6)
int sortedness = 100;
int seq_[] = {0, 13, 0, 0, 12, 0, 0, 0, 2, 0, 0, 10, 5, 0, 0, 0, 0, 0, 0, 7, 15, 16, 20};
vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
long long _ = 53447326LL;
END
CASE(7)
int sortedness = 100;
int seq_[] = {0, 13, 0, 0, 12, 0, 0, 0, 2, 0, 0, 10, 5, 0, 0, 0, 0, 0, 0, 7, 15, 16, 20,
21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659,660,661,662,663,664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679,680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699,700,701,702,703,704,705,706,707,708,709,710,711,712,713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,731,732,733,734,735,736,737,738,739,740,741,742,743,744,745,746,747,748,749,750,751,752,753,754,755,756,757,758,759,760,761,762,763,764,765,766,767,768,769,770,771,772,773,774,775,776,777,778,779,780,781,782,783,784,785,786,787,788,789,790,791,792,793,794,795,796,797,798,799,800,801,802,803,804,805,806,807,808,809,810,811,812,813,814,815,816,817,818,819,820,821,822,823,824,825,826,827,828,829,830,831,832,833,834,835,836,837,838,839,840,841,842,843,844,845,846,847,848,849,850,851,852,853,854,855,856,857,858,859,860,861,862,863,864,865,866,867,868,869,870,871,872,873,874,875,876,877,878,879,880,881,882,883,884,885,886,887,888,889,890,891,892,893,894,895,896,897,898,899,900,901,902,903,904,905,906,907,908,909,910,911,912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,931,932,933,934,935,936,937,938,939,940,941,942,943,944,945,946,947,948,949,950,951,952,953,954,955,956,957,958,959,960,961,962,963,964,965,966,967,968,969,970,971,972,973,974,975,976,977,978,979,980,981,982,983,984,985,986,987,988,989,990,991,992,993,994,995,996,997,998,999,1000,1001,1002,1003,1004,1005,1006,1007,1008,1009,1010,1011,1012,1013,1014,1015,1016,1017,1018,1019,1020,1021,1022,1023,1024,1025,1026,1027,1028,1029,1030,1031,1032,1033,1034,1035,1036,1037,1038,1039,1040,1041,1042,1043,1044,1045,1046,1047,1048,1049,1050,1051,1052,1053,1054,1055,1056,1057,1058,1059,1060,1061,1062,1063,1064,1065,1066,1067,1068,1069,1070,1071,1072,1073,1074,1075,1076,1077,1078,1079,1080,1081,1082,1083,1084,1085,1086,1087,1088,1089,1090,1091,1092,1093,1094,1095,1096,1097,1098,1099,1100,1101,1102,1103,1104,1105,1106,1107,1108,1109,1110,1111,1112,1113,1114,1115,1116,1117,1118,1119,1120,1121,1122,1123,1124,1125,1126,1127,1128,1129,1130,1131,1132,1133,1134,1135,1136,1137,1138,1139,1140,1141,1142,1143,1144,1145,1146,1147,1148,1149,1150,1151,1152,1153,1154,1155,1156,1157,1158,1159,1160,1161,1162,1163,1164,1165,1166,1167,1168,1169,1170,1171,1172,1173,1174,1175,1176,1177,1178,1179,1180,1181,1182,1183,1184,1185,1186,1187,1188,1189,1190,1191,1192,1193,1194,1195,1196,1197,1198,1199,1200,1201,1202,1203,1204,1205,1206,1207,1208,1209,1210,1211,1212,1213,1214,1215,1216,1217,1218,1219,1220,1221,1222,1223,1224,1225,1226,1227,1228,1229,1230,1231,1232,1233,1234,1235,1236,1237,1238,1239,1240,1241,1242,1243,1244,1245,1246,1247,1248,1249,1250,1251,1252,1253,1254,1255,1256,1257,1258,1259,1260,1261,1262,1263,1264,1265,1266,1267,1268,1269,1270,1271,1272,1273,1274,1275,1276,1277,1278,1279,1280,1281,1282,1283,1284,1285,1286,1287,1288,1289,1290,1291,1292,1293,1294,1295,1296,1297,1298,1299,1300,1301,1302,1303,1304,1305,1306,1307,1308,1309,1310,1311,1312,1313,1314,1315,1316,1317,1318,1319,1320,1321,1322,1323,1324,1325,1326,1327,1328,1329,1330,1331,1332,1333,1334,1335,1336,1337,1338,1339,1340,1341,1342,1343,1344,1345,1346,1347,1348,1349,1350,1351,1352,1353,1354,1355,1356,1357,1358,1359,1360,1361,1362,1363,1364,1365,1366,1367,1368,1369,1370,1371,1372,1373,1374,1375,1376,1377,1378,1379,1380,1381,1382,1383,1384,1385,1386,1387,1388,1389,1390,1391,1392,1393,1394,1395,1396,1397,1398,1399,1400,1401,1402,1403,1404,1405,1406,1407,1408,1409,1410,1411,1412,1413,1414,1415,1416,1417,1418,1419,1420,1421,1422,1423,1424,1425,1426,1427,1428,1429,1430,1431,1432,1433,1434,1435,1436,1437,1438,1439,1440,1441,1442,1443,1444,1445,1446,1447,1448,1449,1450,1451,1452,1453,1454,1455,1456,1457,1458,1459,1460,1461,1462,1463,1464,1465,1466,1467,1468,1469,1470,1471,1472,1473,1474,1475,1476,1477,1478,1479,1480,1481,1482,1483,1484,1485,1486,1487,1488,1489,1490,1491,1492,1493,1494,1495,1496,1497,1498,1499,1500,1501,1502,1503,1504,1505,1506,1507,1508,1509,1510,1511,1512,1513,1514,1515,1516,1517,1518,1519,1520,1521,1522,1523,1524,1525,1526,1527,1528,1529,1530,1531,1532,1533,1534,1535,1536,1537,1538,1539,1540,1541,1542,1543,1544,1545,1546,1547,1548,1549,1550,1551,1552,1553,1554,1555,1556,1557,1558,1559,1560,1561,1562,1563,1564,1565,1566,1567,1568,1569,1570,1571,1572,1573,1574,1575,1576,1577,1578,1579,1580,1581,1582,1583,1584,1585,1586,1587,1588,1589,1590,1591,1592,1593,1594,1595,1596,1597,1598,1599,1600,1601,1602,1603,1604,1605,1606,1607,1608,1609,1610,1611,1612,1613,1614,1615,1616,1617,1618,1619,1620,1621,1622,1623,1624,1625,1626,1627,1628,1629,1630,1631,1632,1633,1634,1635,1636,1637,1638,1639,1640,1641,1642,1643,1644,1645,1646,1647,1648,1649,1650,1651,1652,1653,1654,1655,1656,1657,1658,1659,1660,1661,1662,1663,1664,1665,1666,1667,1668,1669,1670,1671,1672,1673,1674,1675,1676,1677,1678,1679,1680,1681,1682,1683,1684,1685,1686,1687,1688,1689,1690,1691,1692,1693,1694,1695,1696,1697,1698,1699,1700,1701,1702,1703,1704,1705,1706,1707,1708,1709,1710,1711,1712,1713,1714,1715,1716,1717,1718,1719,1720,1721,1722,1723,1724,1725,1726,1727,1728,1729,1730,1731,1732,1733,1734,1735,1736,1737,1738,1739,1740,1741,1742,1743,1744,1745,1746,1747,1748,1749,1750,1751,1752,1753,1754,1755,1756,1757,1758,1759,1760,1761,1762,1763,1764,1765,1766,1767,1768,1769,1770,1771,1772,1773,1774,1775,1776,1777,1778,1779,1780,1781,1782,1783,1784,1785,1786,1787,1788,1789,1790,1791,1792,1793,1794,1795,1796,1797,1798,1799,1800,1801,1802,1803,1804,1805,1806,1807,1808,1809,1810,1811,1812,1813,1814,1815,1816,1817,1818,1819,1820,1821,1822,1823,1824,1825,1826,1827,1828,1829,1830,1831,1832,1833,1834,1835,1836,1837,1838,1839,1840,1841,1842,1843,1844,1845,1846,1847,1848,1849,1850,1851,1852,1853,1854,1855,1856,1857,1858,1859,1860,1861,1862,1863,1864,1865,1866,1867,1868,1869,1870,1871,1872,1873,1874,1875,1876,1877,1878,1879,1880,1881,1882,1883,1884,1885,1886,1887,1888,1889,1890,1891,1892,1893,1894,1895,1896,1897,1898,1899,1900,1901,1902,1903,1904,1905,1906,1907,1908,1909,1910,1911,1912,1913,1914,1915,1916,1917,1918,1919,1920,1921,1922,1923,1924,1925,1926,1927,1928,1929,1930,1931,1932,1933,1934,1935,1936,1937,1938,1939,1940,1941,1942,1943,1944,1945,1946,1947,1948,1949,1950,1951,1952,1953,1954,1955,1956,1957,1958,1959,1960,1961,1962,1963,1964,1965,1966,1967,1968,1969,1970,1971,1972,1973,1974,1975,1976,1977,1978,1979,1980,1981,1982,1983,1984,1985,1986,1987,1988,1989,1990,1991,1992,1993,1994,1995,1996,1997,1998,1999,2000}
;
vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
long long _ = -1LL;
END
CASE(8)
int sortedness = 1001982;
int seq_[] = {687, 310, 1393, 747, 1050, 349, 1814, 1842, 638, 1694, 321, 1613, 1034, 1724, 1579, 1292, 1761, 1387, 1213, 463, 1884, 1882, 835, 316, 1722, 8, 1743, 473, 978, 1274, 403, 1617, 1711, 156, 1227, 40, 1858, 851, 1625, 1787, 1779, 1289, 472, 1103, 1739, 1563, 507, 1384, 1804, 1079, 199, 347, 1462, 1891, 198, 583, 1112, 1399, 940, 1958, 1830, 318, 1312, 1137, 296, 96, 1714, 1997, 1078, 382, 1091, 894, 164, 1468, 252, 1549, 1279, 1080, 1901, 1255, 1658, 1571, 1284, 774, 273, 1386, 1318, 208, 1838, 1190, 1747, 797, 485, 1200, 524, 435, 117, 1409, 1135, 0, 1580, 17, 1516, 616, 1762, 1569, 433, 813, 1452, 222, 999, 676, 590, 1661, 372, 1928, 1066, 1608, 359, 1820, 303, 1051, 1171, 1578, 1268, 356, 560, 119, 1389, 1867, 1638, 1323, 188, 534, 545, 1946, 233, 167, 268, 1949, 775, 781, 529, 353, 215, 572, 70, 1540, 1042, 1294, 1642, 1373, 691, 1152, 504, 1397, 549, 808, 36, 1480, 881, 982, 611, 1314, 1430, 543, 987, 234, 1370, 1801, 1603, 9, 1501, 913, 1483, 1077, 1069, 1140, 615, 1163, 1914, 1936, 1402, 1636, 535, 1466, 277, 1878, 563, 1424, 1226, 910, 949, 326, 1153, 838, 439, 422, 1502, 489, 1819, 1132, 673, 196, 132, 131, 229, 140, 657, 609, 605, 162, 1744, 690, 850, 1197, 251, 1622, 1733, 1358, 346, 427, 607, 1240, 1410, 1203, 1833, 186, 766, 1192, 924, 509, 28, 589, 1353, 1872, 1582, 1759, 911, 1673, 369, 1524, 116, 1461, 454, 479, 1282, 1006, 0, 817, 1232, 655, 1448, 684, 1531, 1753, 580, 1566, 1666, 159, 1217, 1934, 875, 636, 1522, 1304, 174, 6, 380, 1951, 1825, 1786, 1106, 1315, 335, 849, 1574, 50, 1485, 974, 1705, 81, 1198, 645, 358, 1558, 85, 1770, 421, 1167, 1641, 510, 700, 1407, 1476, 546, 25, 287, 333, 481, 1763, 824, 381, 1014, 65, 414, 336, 843, 160, 1309, 1738, 1635, 1925, 453, 1356, 574, 1856, 1597, 1750, 1283, 1512, 1939, 1076, 398, 1016, 1261, 984, 1290, 341, 1871, 1146, 726, 366, 1361, 1401, 1414, 1100, 1767, 1534, 1182, 95, 110, 1060, 1473, 1451, 784, 739, 804, 1338, 1007, 77, 731, 1139, 1577, 619, 379, 361, 873, 1756, 599, 1510, 540, 1327, 107, 1800, 1369, 1121, 650, 1071, 204, 203, 178, 1553, 98, 1366, 1403, 927, 1952, 904, 724, 1195, 266, 1463, 93, 1557, 1130, 1454, 148, 1696, 528, 329, 1637, 932, 1503, 718, 106, 1809, 1449, 551, 323, 319, 216, 745, 1834, 707, 1868, 1771, 1916, 1828, 128, 1127, 189, 826, 1699, 818, 922, 78, 703, 842, 1306, 1365, 825, 331, 858, 571, 1425, 1664, 1193, 1418, 1011, 63, 1347, 288, 265, 459, 812, 1506, 1141, 1539, 569, 672, 1020, 214, 1089, 1183, 450, 1010, 452, 292, 1967, 423, 1757, 1415, 1019, 1514, 27, 1442, 1626, 282, 1766, 1288, 1201, 831, 269, 294, 988, 1537, 751, 24, 1527, 1490, 471, 640, 1254, 1229, 1683, 1244, 1291, 261, 1979, 494, 760, 289, 420, 840, 260, 1342, 1481, 990, 1717, 736, 846, 514, 124, 1024, 1991, 337, 1860, 1734, 878, 1443, 533, 1650, 713, 1561, 10, 1375, 1337, 511, 259, 1913, 1276, 123, 782, 728, 1695, 1239, 1568, 1269, 1785, 613, 324, 1220, 1420, 1438, 1488, 802, 902, 1985, 1172, 1935, 596, 133, 1983, 90, 161, 587, 7, 1117, 1070, 1095, 554, 1776, 1162, 244, 1840, 759, 142, 573, 938, 1742, 1790, 1396, 1731, 669, 49, 1735, 696, 762, 705, 909, 350, 1187, 1866, 1795, 756, 1621, 1129, 231, 1058, 1498, 1307, 567, 1708, 508, 1257, 1824, 55, 1472, 936, 1564, 559, 1525, 732, 956, 941, 56, 462, 1214, 495, 271, 1105, 11, 299, 1262, 114, 1114, 195, 527, 1234, 1211, 1017, 544, 0, 13, 1900, 1859, 765, 1437, 1465, 1116, 279, 1657, 1030, 1541, 1002, 1322, 767, 1169, 91, 22, 861, 135, 1062, 783, 1818, 181, 1826, 1474, 1411, 1311, 933, 1821, 1667, 801, 1489, 1583, 591, 866, 0, 1890, 180, 364, 51, 521, 1038, 151, 1305, 931, 1605, 1421, 1495, 1115, 1295, 1773, 1087, 1252, 137, 1267, 1419, 1606, 309, 1251, 334, 100, 280, 1873, 552, 575, 1649, 1682, 1379, 144, 885, 270, 1940, 566, 806, 1032, 1971, 1772, 1427, 1475, 525, 1165, 1945, 1123, 1817, 631, 58, 1122, 120, 692, 1022, 1194, 1680, 698, 384, 322, 939, 1990, 154, 1450, 213, 663, 997, 441, 1865, 1026, 1960, 437, 702, 263, 744, 1727, 267, 1796, 768, 1533, 2, 191, 225, 964, 1908, 434, 1518, 1285, 26, 914, 176, 487, 192, 149, 130, 1043, 220, 624, 629, 1210, 125, 625, 639, 1999, 0, 920, 968, 0, 976, 0, 467, 238, 1620, 538, 1929, 1915, 480, 1581, 1844, 1184, 603, 386, 1371, 1273, 474, 1131, 1343, 406, 1726, 1575, 483, 158, 930, 871, 1199, 1846, 1792, 1652, 618, 0, 754, 74, 1101, 1302, 942, 1394, 1507, 165, 342, 1547, 113, 847, 649, 1319, 597, 856, 247, 1565, 1064, 1148, 962, 301, 1191, 418, 1938, 376, 1992, 1143, 844, 965, 1073, 228, 1746, 879, 1632, 0, 1067, 1212, 1405, 1931, 64, 1477, 954, 1781, 637, 79, 1851, 1614, 1036, 211, 1049, 634, 1222, 1697, 1526, 430, 243, 929, 500, 1749, 729, 1659, 1363, 1441, 1602, 1758, 339, 1124, 194, 890, 957, 1445, 370, 790, 1715, 240, 966, 970, 1730, 1380, 482, 449, 182, 908, 61, 512, 659, 338, 561, 201, 33, 392, 221, 1223, 1392, 1224, 286, 737, 1028, 276, 867, 1092, 80, 429, 935, 743, 1236, 43, 1233, 1385, 1334, 1573, 758, 1029, 1344, 1803, 283, 530, 699, 1975, 1444, 892, 757, 983, 1471, 460, 1691, 610, 1270, 523, 1082, 679, 242, 1827, 585, 5, 1096, 915, 539, 490, 1594, 1126, 1806, 1458, 1113, 1247, 307, 1647, 388, 1665, 1920, 794, 1018, 442, 419, 1253, 1710, 115, 681, 1395, 1798, 122, 880, 1455, 1186, 1308, 1326, 592, 1383, 1548, 476, 1887, 1588, 1044, 1835, 1147, 1428, 75, 503, 1853, 1021, 1412, 354, 1651, 97, 1340, 1562, 1968, 129, 1535, 715, 1231, 1249, 1511, 1911, 30, 1883, 1719, 776, 1349, 1701, 876, 727, 53, 1107, 959, 513, 761, 752, 1725, 872, 395, 1862, 1332, 1609, 788, 103, 31, 1644, 230, 1, 723, 1376, 1643, 4, 1088, 579, 396, 1692, 1008, 1875, 305, 595, 1243, 1707, 314, 1713, 719, 923, 1263, 68, 675, 654, 564, 290, 882, 803, 1248, 1154, 1633, 1245, 492, 405, 1864, 0, 451, 14, 1812, 411, 1732, 1416, 830, 1025, 1209, 1656, 1298, 1457, 1645, 461, 1005, 653, 1895, 1460, 1063, 562, 1378, 1523, 845, 1061, 416, 1996, 436, 1969, 1055, 143, 874, 1000, 642, 1496, 1618, 1903, 542, 1993, 716, 870, 862, 1150, 1098, 171, 895, 190, 798, 1120, 1464, 839, 1035, 1587, 1630, 118, 771, 34, 71, 1207, 448, 315, 556, 709, 1941, 532, 1712, 1040, 1646, 1898, 373, 1604, 919, 859, 674, 328, 89, 1144, 646, 1585, 912, 127, 1048, 651, 325, 1206, 1857, 1953, 1943, 969, 1560, 977, 42, 1797, 249, 688, 903, 134, 710, 1823, 1177, 1905, 1544, 1090, 104, 1033, 1205, 570, 431, 407, 1352, 147, 1235, 1012, 428, 1372, 1681, 295, 1118, 136, 224, 682, 496, 1075, 1354, 661, 306, 1755, 1869, 1906, 105, 1765, 1570, 1974, 1400, 19, 1532, 1336, 363, 886, 1611, 1961, 992, 387, 526, 621, 408, 652, 1693, 1690, 677, 951, 250, 491, 1102, 1382, 1180, 1815, 577, 1111, 1408, 1157, 644, 1748, 721, 1447, 1528, 478, 1586, 499, 344, 1287, 1478, 206, 108, 518, 1721, 1136, 1320, 1654, 1434, 852, 1964, 1612, 516, 468, 658, 1486, 827, 1995, 1301, 169, 237, 975, 447, 1423, 1300, 1829, 779, 226, 168, 1874, 697, 1950, 1505, 235, 627, 1297, 1094, 934, 1350, 1877, 725, 795, 102, 1265, 1221, 1684, 177, 1432, 1174, 1446, 887, 1768, 1004, 1149, 1850, 1138, 1296, 1870, 1074, 60, 848, 469, 1250, 1362, 1802, 1056, 993, 1133, 1009, 665, 1429, 1894, 753, 918, 1189, 2000, 1381, 1839, 1687, 73, 1610, 1655, 1595, 1218, 1299, 1843, 928, 1536, 371, 466, 1631, 1723, 1559, 1980, 1345, 952, 660, 584, 689, 1266, 1453, 1324, 704, 52, 1972, 394, 708, 47, 780, 32, 1729, 1909, 877, 1357, 1119, 308, 1374, 1793, 1277, 1196, 853, 712, 836, 1822, 1607, 1456, 146, 1752, 202, 537, 365, 1704, 1237, 1159, 1215, 1741, 1685, 1181, 1509, 150, 553, 1703, 1479, 1185, 1599, 1927, 1001, 555, 1937, 1782, 1508, 456, 985, 313, 126, 582, 981, 623, 972, 1791, 755, 1216, 686, 792, 475, 633, 1955, 1754, 88, 1640, 648, 410, 1876, 444, 23, 901, 1435, 1329, 400, 1173, 520, 1677, 1391, 352, 1504, 297, 1108, 1134, 1355, 1046, 355, 1998, 916, 1110, 1783, 588, 832, 1893, 1529, 1672, 389, 424, 1596, 1085, 664, 581, 304, 1899, 1093, 670, 1178, 1686, 1660, 1176, 917, 547, 1368, 1281, 1676, 1910, 458, 87, 1325, 348, 1426, 368, 1166, 1538, 1367, 391, 285, 239, 1861, 1799, 1813, 1702, 258, 1037, 821, 1892, 576, 1567, 749, 332, 1764, 1624, 1775, 1619, 1543, 254, 94, 991, 888, 1963, 1348, 946, 497, 799, 1970, 445, 404, 769, 1272, 733, 683, 1678, 29, 1546, 1918, 1670, 1081, 1942, 1484, 218, 1917, 183, 986, 791, 281, 891, 980, 262, 1653, 1003, 632, 173, 1242, 1698, 1957, 602, 626, 945, 948, 21, 278, 693, 1886, 1810, 604, 541, 1716, 1104, 819, 343, 209, 656, 1208, 1896, 1674, 868, 1954, 1745, 1552, 1988, 1422, 717, 1467, 834, 1634, 12, 807, 1984, 62, 54, 1816, 1151, 438, 187, 1377, 1310, 1246, 1671, 82, 586, 1805, 426, 1072, 39, 601, 1902, 1777, 37, 967, 1317, 293, 1084, 1688, 1922, 345, 112, 742, 223, 711, 1848, 1491, 668, 1590, 217, 678, 622, 519, 374, 1989, 1584, 362, 926, 568, 598, 789, 1494, 1492, 606, 1700, 1593, 1987, 291, 1965, 330, 1639, 612, 763, 1551, 796, 1542, 1328, 515, 1778, 409, 1417, 1919, 1924, 1433, 594, 1499, 1944, 1440, 833, 1728, 860, 212, 399, 1662, 425, 685, 1439, 865, 1623, 66, 740, 248, 1083, 1406, 1808, 1482, 1849, 446, 1045, 1615, 320, 1339, 1736, 1142, 501, 1155, 1545, 1513, 1555, 1388, 302, 937, 1976, 1331, 1852, 1493, 1390, 193, 1109, 1470, 1973, 1668, 253, 69, 18, 734, 864, 900, 958, 1228, 1831, 1576, 1436, 1921, 722, 741, 1086, 1628, 1054, 205, 284, 300, 1706, 1280, 889, 1845, 714, 1592, 647, 1041, 0, 1977, 1760, 1737, 1932, 1068, 72, 15, 1059, 505, 1521, 1769, 470, 166, 20, 1627, 440, 811, 1260, 950, 236, 898, 1669, 746, 1556, 550, 1360, 1047, 973, 139, 1278, 557, 397, 84, 1648, 67, 1885, 417, 635, 961, 787, 443, 375, 16, 617, 311, 477, 402, 1271, 1065, 312, 1431, 185, 1679, 86, 401, 748, 600, 1675, 1170, 274, 857, 46, 152, 906, 232, 893, 184, 3, 823, 805, 1161, 522, 820, 464, 921, 1904, 1497, 905, 620, 896, 680, 48, 1238, 778, 1863, 1351, 630, 786, 1948, 738, 1986, 1500, 101, 701, 1264, 1398, 1202, 907, 488, 498, 1897, 390, 255, 76, 1097, 1341, 1303, 1230, 998, 1807, 1794, 377, 1160, 925, 884, 170, 1530, 1330, 1709, 1572, 1404, 777, 963, 493, 855, 457, 92, 1333, 1966, 517, 953, 141, 298, 197, 960, 1837, 1629, 643, 1811, 841, 1855, 694, 1601, 773, 1923, 1286, 35, 1168, 989, 578, 828, 793, 822, 83, 1321, 809, 667, 256, 1515, 99, 1554, 608, 1689, 1847, 897, 1179, 1258, 145, 153, 109, 264, 810, 1413, 38, 863, 179, 246, 1788, 1879, 1259, 121, 367, 815, 412, 671, 1158, 207, 1912, 800, 614, 1052, 1836, 770, 1316, 138, 1520, 383, 393, 1780, 317, 548, 57, 111, 1517, 1591, 1219, 1313, 1128, 272, 210, 772, 1099, 1947, 565, 1789, 750, 1930, 1663, 1359, 1718, 814, 1616, 1027, 955, 1275, 1600, 1784, 0, 1981, 1994, 899, 854, 175, 1031, 1013, 720, 275, 227, 995, 558, 1256, 1241, 1335, 0, 695, 257, 730, 816, 506, 385, 1487, 0, 486, 1039, 59, 1188, 157, 994, 1978, 415, 1982, 971, 628, 219, 943, 996, 593, 1469, 1145, 340, 1023, 1519, 1832, 662, 432, 1225, 1841, 1889, 837, 706, 1933, 327, 1346, 829, 45, 163, 979, 764, 1740, 44, 1926, 785, 1057, 1589, 360, 1888, 413, 1015, 455, 1854, 944, 1598, 155, 1774, 1720, 357, 1459, 1550, 241, 1164, 1156, 883, 735, 1364, 1907, 172, 41, 641, 536, 1125, 1293, 1956, 1959, 531, 484, 1881, 1962};
vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
long long _ = -1LL;
END
}
// END CUT HERE