Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:95147 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 62948 invoked from network); 14 Aug 2016 21:20:28 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 14 Aug 2016 21:20:28 -0000 Authentication-Results: pb1.pair.com header.from=lauri.kentta@gmail.com; sender-id=softfail Authentication-Results: pb1.pair.com smtp.mail=lauri.kentta@gmail.com; spf=softfail; sender-id=softfail Received-SPF: softfail (pb1.pair.com: domain gmail.com does not designate 188.117.41.47 as permitted sender) X-PHP-List-Original-Sender: lauri.kentta@gmail.com X-Host-Fingerprint: 188.117.41.47 mailgateway.locotech.fi Linux 2.6 Received: from [188.117.41.47] ([188.117.41.47:53329] helo=mailgateway.locotech.fi) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id 29/62-36656-790E0B75 for ; Sun, 14 Aug 2016 17:20:25 -0400 Received: from localhost (mailgateway [127.0.0.1]) by mailgateway.locotech.fi (Postfix) with ESMTP id 1665BA36A59 for ; Mon, 15 Aug 2016 00:20:21 +0300 (EEST) X-Virus-Scanned: amavisd-new at locotech.fi X-Spam-Flag: NO X-Spam-Score: -1.998 X-Spam-Level: X-Spam-Status: No, score=-1.998 tagged_above=-9998 required=5 tests=[ALL_TRUSTED=-1, BAYES_00=-1.9, DKIM_ADSP_CUSTOM_MED=0.001, FREEMAIL_FROM=0.001, NML_ADSP_CUSTOM_MED=0.9] autolearn=no autolearn_force=no Received: from mailgateway.locotech.fi ([127.0.0.1]) by localhost (mailgateway.locotech.fi [127.0.0.1]) (amavisd-new, port 10024) with LMTP id TPmnhJUZd6u1 for ; Mon, 15 Aug 2016 00:20:06 +0300 (EEST) Received: from posti.fimnet.fi (posti.fimnet.fi [172.16.1.44]) by mailgateway.locotech.fi (Postfix) with ESMTP id 20F89A36A5A for ; Mon, 15 Aug 2016 00:20:05 +0300 (EEST) Received: from k-piste.dy.fi (unknown [172.16.1.39]) by posti.fimnet.fi (Postfix) with ESMTPSA id A1F38100670 for ; Mon, 15 Aug 2016 00:20:05 +0300 (EEST) Received: from 37-136-133-54.rev.dnainternet.fi ([37.136.133.54] helo=k-one.k-uikku) by k-piste.dy.fi with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (Exim 4.87) (envelope-from ) id 1bZ2p2-0005dx-Ji for internals@lists.php.net; Mon, 15 Aug 2016 00:19:57 +0300 To: internals@lists.php.net Date: Mon, 15 Aug 2016 00:19:42 +0300 Message-ID: <20160814211942.16358-1-lauri.kentta@gmail.com> X-Mailer: git-send-email 2.9.3 In-Reply-To: <3d8be1faf8d4d3e5add3768d7a8eb16c@k-piste.dy.fi> References: <3d8be1faf8d4d3e5add3768d7a8eb16c@k-piste.dy.fi> Subject: [RFC: PATCH v1] Implement mt_srand_array From: lauri.kentta@gmail.com (=?UTF-8?q?Lauri=20Kentt=C3=A4?=) --- ext/standard/basic_functions.c | 5 + ext/standard/mt_rand.c | 67 ++- ext/standard/php_math.h | 1 + ext/standard/tests/math/mt_srand_array_basic.phpt | 146 ++++++ ext/standard/tests/math/mt_srand_array_values.phpt | 532 +++++++++++++++++++++ 5 files changed, 750 insertions(+), 1 deletion(-) create mode 100644 ext/standard/tests/math/mt_srand_array_basic.phpt create mode 100644 ext/standard/tests/math/mt_srand_array_values.phpt diff --git a/ext/standard/basic_functions.c b/ext/standard/basic_functions.c index ef628cc..bcceb20 100644 --- a/ext/standard/basic_functions.c +++ b/ext/standard/basic_functions.c @@ -1891,6 +1891,10 @@ ZEND_BEGIN_ARG_INFO_EX(arginfo_mt_srand, 0, 0, 0) ZEND_ARG_INFO(0, mode) ZEND_END_ARG_INFO() +ZEND_BEGIN_ARG_INFO(arginfo_mt_srand_array, 0) + ZEND_ARG_INFO(0, seed) +ZEND_END_ARG_INFO() + ZEND_BEGIN_ARG_INFO_EX(arginfo_mt_rand, 0, 0, 0) ZEND_ARG_INFO(0, min) ZEND_ARG_INFO(0, max) @@ -2856,6 +2860,7 @@ const zend_function_entry basic_functions[] = { /* {{{ */ PHP_FALIAS(getrandmax, mt_getrandmax, arginfo_mt_getrandmax) PHP_FE(mt_rand, arginfo_mt_rand) PHP_FE(mt_srand, arginfo_mt_srand) + PHP_FE(mt_srand_array, arginfo_mt_srand_array) PHP_FE(mt_getrandmax, arginfo_mt_getrandmax) PHP_FE(random_bytes, arginfo_random_bytes) diff --git a/ext/standard/mt_rand.c b/ext/standard/mt_rand.c index dde9a77..04e83dd 100644 --- a/ext/standard/mt_rand.c +++ b/ext/standard/mt_rand.c @@ -151,7 +151,10 @@ PHPAPI void php_mt_srand(uint32_t seed) { /* Seed the generator with a simple uint32 */ php_mt_initialize(seed, BG(state)); - php_mt_reload(); + + /* Reload the generator when mt_rand is next called. + * (Reloading immediately would break php_mt_srand_array.) */ + BG(left) = 0; /* Seed only once */ BG(mt_rand_is_seeded) = 1; @@ -209,6 +212,68 @@ PHP_FUNCTION(mt_srand) } /* }}} */ +/* {{{ proto void mt_srand_array(array seed) + Seeds Mersenne Twister random number generator with multiple integers */ +PHP_FUNCTION(mt_srand_array) +{ + zval* arr = 0; + zval* tmp; + uint32_t length = 0, seed_j; + int i, j, k, first_loop = 1; + uint32_t* mt = BG(state); + + if (zend_parse_parameters(ZEND_NUM_ARGS(), "a", &arr) == FAILURE) + return; + + length = zend_hash_num_elements(Z_ARRVAL_P(arr)); + if (length == 0) { + php_error_docref(NULL, E_WARNING, "Argument must be an array with at least 1 element"); + return; + } + + ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(arr), tmp) { + if (Z_TYPE_P(tmp) != IS_LONG) { + php_error_docref(NULL, E_WARNING, "Argument must be an array with only integer elements"); + return; + } + if (Z_LVAL_P(tmp) > 0xffffffffU) { + php_error_docref(NULL, E_WARNING, "Seed values will be truncated at 32 bits"); + return; + } + } ZEND_HASH_FOREACH_END(); + + php_mt_srand(19650218U); + i = 1; + k = 0; + while (k < N) { + j = 0; + ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(arr), tmp) { + seed_j = Z_LVAL_P(tmp); + mt[i] = ((mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525U)) + seed_j + j) & 0xffffffffU; + i++; j++; k++; + if (i == N) { + mt[0] = mt[N-1]; + i = 1; + } + if (!first_loop && k == N) { + break; + } + } ZEND_HASH_FOREACH_END(); + first_loop = 0; + } + for (k = 1; k < N; ++k) { + mt[i] = ((mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941U)) - i) & 0xffffffffU; + i++; + if (i == N) { + mt[0] = mt[N-1]; + i = 1; + } + } + + mt[0] = 0x80000000UL; +} +/* }}} */ + /* {{{ php_mt_rand_range */ PHPAPI zend_long php_mt_rand_range(zend_long min, zend_long max) diff --git a/ext/standard/php_math.h b/ext/standard/php_math.h index 3ff0f04..0eaf34c 100644 --- a/ext/standard/php_math.h +++ b/ext/standard/php_math.h @@ -48,6 +48,7 @@ PHP_FUNCTION(pow); PHP_FUNCTION(sqrt); PHP_FUNCTION(rand); PHP_FUNCTION(mt_srand); +PHP_FUNCTION(mt_srand_array); PHP_FUNCTION(mt_rand); PHP_FUNCTION(mt_getrandmax); PHP_FUNCTION(abs); diff --git a/ext/standard/tests/math/mt_srand_array_basic.phpt b/ext/standard/tests/math/mt_srand_array_basic.phpt new file mode 100644 index 0000000..9632ff6 --- /dev/null +++ b/ext/standard/tests/math/mt_srand_array_basic.phpt @@ -0,0 +1,146 @@ +--TEST-- +Test mt_srand_array() - basic function mt_srand_array() +--FILE-- + +--EXPECTF-- +bool(true) +bool(false) +NULL +NULL +NULL + +Warning: mt_srand_array() expects exactly 1 parameter, 0 given in %s on line %d +NULL + +Warning: mt_srand_array() expects parameter 1 to be array, null given in %s on line %d +NULL + +Warning: mt_srand_array() expects parameter 1 to be array, boolean given in %s on line %d +NULL + +Warning: mt_srand_array() expects parameter 1 to be array, boolean given in %s on line %d +NULL + +Warning: mt_srand_array() expects parameter 1 to be array, integer given in %s on line %d +NULL + +Warning: mt_srand_array() expects parameter 1 to be array, float given in %s on line %d +NULL + +Warning: mt_srand_array() expects parameter 1 to be array, string given in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with at least 1 element in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL diff --git a/ext/standard/tests/math/mt_srand_array_values.phpt b/ext/standard/tests/math/mt_srand_array_values.phpt new file mode 100644 index 0000000..267087b --- /dev/null +++ b/ext/standard/tests/math/mt_srand_array_values.phpt @@ -0,0 +1,532 @@ +--TEST-- +Test mt_srand_array() - check compability with init_by_array in mt19937ar.c +--FILE-- + +--EXPECT-- +init 5 +1678085969, 173170251, 1782802870, 937957818, 2049075857, 475493648, +631159003, 265551473, 367318037, 180728820, 882767285, 518593020, +1483604447, 134774193, 964352505, 1672651821, 88387593, 624398452, +768905273, 62945995, 1786727054, 129379898, 1251426231, 120487373, +1588634830, 646438254, 2062420793, 624611897, 380598150, 1999644287, +126446955, 159634314, 1420847270, 727488664, 299098148, 414993981, +987722467, 1753145380, 1045592542, 12767669, 1223761434, 1813465931, +171025115, 335674505, 1777844237, 2046360196, 549508484, 2060432233, +1478591136, 82598413, 1437272609, 188008750, 537318096, 1563000981, +1322768027, 122924280, 989201561, 1838053780, 1524406237, 402767818, +1357934275, 518154174, 1970896318, 1291492803, 1703288044, 1710090268, +1134974040, 1205530280, 1564219437, 1959999115, 2070873944, 1093246373, +1774468942, 1548462422, 1537766937, 2470930, 1730334238, 542124953, +1485726082, 1611191139, 1615506211, 1744134923, 1032166749, 373825211, +1185635659, 2054543400, 1408272743, 222902069, 934971869, 325709765, +1848019873, 1701075729, 390124953, 773120821, 360567826, 1789065666, +1134188761, 235988203, 1649775550, 1866268786, 1865237225, 308439968, +488266067, 671018254, 112438428, 495480977, 1667523297, 584455950, +1606364015, 803240708, 681841472, 1884613027, 879967411, 1244875426, +1958303277, 1169798427, 2067773861, 399232754, 429408626, 1444908741, +1397404058, 438083513, 51005745, 677540897, 1848792993, 2040283834, +73877667, 641558522, 210465773, 670213318, 1962329747, 213848257, +127734689, 1159679712, 309719363, 343863574, 451160292, 363285968, +920300268, 1223618319, 2092752885, 716753896, 253388247, 1033700545, +656469891, 964333406, 626675494, 668764599, 284541113, 716974699, +1552757841, 2122977183, 1961264786, 159796457, 954597579, 76987656, +458685897, 745258981, 1725018277, 222533039, 811460418, 247922055, +421883548, 381762822, 756499932, 942630902, 1560631298, 772857810, +1894117589, 733999678, 793502595, 1322008488, 1614401720, 1495641839, +1158576564, 1823434050, 1664573103, 7566840, 1727024249, 798041803, +582370562, 304218954, 838981650, 314510836, 1828785517, 1104865992, +426047409, 254634264, 1052462887, 654559757, 1110467271, 1368997850, +1332370983, 1298526292, 1717151294, 1299785270, 1205967042, 1945591610, +39245245, 252233892, 1379438881, 1563554062, 55749522, 1281643592, +772214558, 419402223, 2139436058, 1438909276, 116548681, 977950774, +1843696587, 262197124, 1027335544, 99463235, 1377044058, 272767630, +2076200847, 785296613, 1095742480, 1187187832, 476552792, 834384586, +140321133, 1895093493, 1704339120, 1206230228, 672749714, 701573697, +712587138, 559763958, 1833886670, 1246194772, 131970736, 1026960167, +258531498, 533309357, 302809735, 78705794, 180401783, 1438221774, +1171710223, 62233318, 1114313937, 181783356, 1372495881, 1525021015, +1081472076, 863314220, 1154718358, 632560915, 447829343, 172268965, +892950544, 638504668, 1927157561, 48066633, 1048890682, 1639383707, +214700437, 2091128935, 1398268525, 2787833, 404111919, 1496088284, +1568785210, 1237637766, 2024715775, 1070278879, 333332389, 222404898, +530985834, 436107194, 898494426, 2002031102, 1463945304, 1047357225, +877606586, 1779966837, 777777644, 2047233898, 1397786520, 1397326652, +1888920804, 1987775265, 1343238365, 1521274607, 1664471951, 1824675909, +1214837658, 687267230, 1318012059, 1523568963, 1569744542, 2040235203, +1458478110, 813839624, 516195500, 1706443716, 387069934, 826717497, +661029222, 1698099585, 1619086966, 472920484, 397208282, 1546010573, +1459811472, 155769548, 1005470241, 1332622415, 1401701839, 929943807, +17496501, 167865207, 39119769, 1549803902, 1275144214, 402453424, +291332047, 119011701, 424791945, 1635111346, 1008471199, 1235519240, +1964241044, 1171691282, 407274744, 264819878, 2127954766, 936159281, +1125822853, 1147029717, 656833846, 1991402116, 1226342161, 1812321691, +524992088, 1810773922, 2026071844, 1615449650, 2126358431, 270824574, +272446342, 1116242880, 1796886580, 697118066, 1732398470, 134944144, +396856570, 1781884880, 2062414019, 102202061, 614318803, 2073719717, +42103060, 1524008207, 1003551051, 1324347014, 343150315, 121854185, +1749758390, 2086808537, 1267592318, 72062746, 1207296988, 1643045338, +165847348, 965850327, 1630973577, 1485469182, 306799380, 643908446, +735844106, 613194827, 1424491263, 20870783, 1683414788, 814852722, +1645422996, 1591969802, 108681618, 596735742, 581347169, 238372006, +2057427754, 411896601, 179840892, 1171842900, 1243785904, 1160793500, +1168001476, 1701651494, 1573335512, 919745851, 1423498746, 1599105340, +59486933, 1946207583, 255480857, 230755676, 582759138, 1782505704, +1014623654, 93567142, 501546608, 445395111, 1698508681, 2118306626, +2044371843, 1590884942, 1855172077, 2132429415, 693554267, 1540348537, +1524008423, 1598749681, 1162339897, 83169613, 1582659019, 1386408935, +452518407, 399739662, 562081531, 1749652889, 456329004, 1651421807, +417441467, 72768787, 188189810, 938986731, 1267364468, 1263903786, +943353794, 831740732, 573154911, 930464617, 1706902055, 320044701, +1848930605, 759699675, 650016838, 603605656, 1295110101, 1682265851, +548352407, 1646100528, 1470310168, 1395219556, 2057341385, 1454271902, +1152371462, 287938688, 1313390732, 732216538, 1611562077, 2108866735, +1791254179, 1695098182, 860924454, 1071154156, 1595681364, 1110578611, +967111431, 529535867, 1747680551, 1901288299, 1146121481, 1032369048, +1561952783, 281435437, 1575636635, 709983939, 1682585696, 792937343, +706127520, 1356220838, 1323583891, 741089452, 1871351301, 296217876, +1643734231, 206775477, 1705966924, 948141888, 1049519578, 739897487, +125778627, 112303069, 864415289, 542025605, 667129468, 965667788, +2070292383, 631287150, 173144548, 1697432442, 996099145, 604261523, +1447892832, 837818285, 445235679, 1499594811, 876824624, 393233787, +1626380339, 1303856788, 855369858, 188641682, 1681158451, 2094210553, +1781204178, 1135663622, 704285652, 1880224068, 425221731, 327473624, +1039642257, 1565338083, 414946522, 1010064589, 1264913340, 1515349606, +1511659415, 867897001, 424884116, 187908546, 2064028594, 1318843210, +1200326261, 1171921289, 1755282560, 577579416, 1963270104, 108604668, +1465657995, 2134994058, 54063649, 1922385414, 2134814091, 920509373, +1371241837, 179734609, 1753977750, 1881176241, 1160194538, 633203641, +248257266, 160432164, 1174083751, 1869649959, 1265733541, 342753628, +1042343179, 1558817004, 662228230, 426303967, 52599397, 417304543, +563481354, 1959363161, 1012360589, 1480861398, 1091180077, 757484865, +402810392, 22659448, 2104312645, 1393473726, 313079060, 1720345614, +1547286608, 440350497, 1038702504, 1320656001, 139557658, 160814655, +1120448208, 1630894778, 1823854524, 2112880666, 254049795, 769182217, +1988273240, 265535314, 155513257, 910763639, 1494357430, 336664448, +709382536, 1371967891, 460724405, 1851926075, 1543123287, 1951024034, +757250103, 371934696, 1711929196, 1140185691, 1916650934, 763374904, +1270790180, 1862915836, 1428366502, 224431428, 1025831708, 1353196886, +1472340786, 617723365, 1667847487, 2145832122, 499682359, 1225554127, +879776645, 1531037326, 1162895834, 317423246, 1685725841, 726301581, +1445098093, 1518570230, 207578906, 1570892321, 507703530, 1028678219, +1908778501, 251699072, 803730769, 1725031729, 1231638911, 184249436, +1657312598, 182416268, 659889559, 1076854276, 1227109276, 2101310460, +1080262363, 2010944041, 872294238, 296576621, 1639843353, 1055468010, +1221834574, 1640475125, 1586738399, 1885305952, 183220722, 498344677, +444321987, 1643254950, 1707056411, 840347155, 701891000, 1586612615, +2069168262, 146270803, 833420350, 493189987, 773262803, 1653658434, +2052935862, 1732568101, 589336318, 1317029499, 1947842396, 1625044604, +2067190720, 1938660402, 2127461260, 1833473329, 1769289178, 675228003, +1274493809, 2030117365, 2111336557, 889705256, 1313670825, 978867720, +1124383289, 1081615542, 872995886, 1580286787, 1743304828, 2065619306, +141336252, 900473833, 1276311040, 1031012968, 1684506321, 1715923687, +113051291, 2103905761, 1796447328, 1481419947, 1265353271, 463463765, +1181842726, 1864289951, 1391445669, 1561920507, 1690657304, 539450648, +233976639, 1781460989, 102116313, 277501659, 2057695232, 399374154, +253291389, 213054850, 1549165702, 141993661, 609980912, 954361616, +369994966, 1963169244, 1461655693, 1456507482, 559744717, 584737195, +1489543623, 559564535, 140274584, 970099295, 392790864, 54182867, +593868692, 2140733955, 101159131, 2024047281, 1266096579, 606195139, +1602404067, 2060457720, 1761718118, 1836011858, 785892683, 1716308014, +861070048, 1702443877, 941622984, 378366524, 152594682, 167909708, +314963998, 630854539, 1798994002, 1389044097, 985097841, 1157040721, +265075438, 1429980301, 499489890, 623159753, 1172125800, 886466981, +183494643, 564774918, 1898626953, 306976580, 810859339, 291570861, +1487607786, 1852587929, 2013416964, 214002840, 1133515065, 729846310, +2122565116, 1966058439, 1973273434, 906557283, 1982866876, 1725046252, +922159523, 1680009188, 636183905, 492096369, 1065504721, 1658221372, +1915213760, 20704986, 2054518307, 417623390, 338259801, 1772577704, +1164295913, 1487400349, 1198936352, 941802882, 710953151, 41436756, +694551391, 1780791007, 1670172407, 510226143, 1704983228, 1234576800, +2017484910, 1987089499, 877072623, 218656974, 1882899491, 203698556, +1513215802, 1080859235, 722664779, 663232474, 694739582, 37157761, +321239494, 1340305956, 569186972, 1999156701, 1125628319, 2053000467, +931556325, 1339953903, 474370210, 1778883985, 27178352, 1364274459, +2116793083, 1332866977, 451364122, 277350424, 1259803477, 806709477, +710988522, 568129536, 1525314388, 1589055462, 1649655838, 24851681, +1191362823, 652466018, 51507135, 1949811523, 1420215882, 20117642, +1857490136, 612776782, 848703729, 212984899, 488209359, 894858669, +749747098, 1449304251, 1395664211, 1033532758, 2065110276, 1559613251, +265952038, 943542317, 1998024290, 313914991, 1194859837, 389750550, +411229008, 840806755, 292338179, 1161175231, 317219581, 507864395, +606806965, 1325384287, 955404346, 1246677080, 1322281139, 1598537319, +1166023292, 1450778928, 1637022860, 731667986, 2073782484, 1004998191, +102564534, 815125906, 1576098225, 1524965501, 5313864, 1823974573, +1773504912, 1041743912, 881554341, 960776758, 552712693, 408302745, +2114071279, 992220049, 511892365, 1697239197, 1629776795, 1137469311, +576094438, 427212158, 202025744, 1805447936, 542712707, 1212058647, +1131832821, 691738312, 1352812628, 892381556, 715334465, 1341375748, +564271455, 1911559160, 1475034391, 158936189, 2098991028, 1661681153, +988209962, 1208631994, 1931293838, 1520770876, 1957491147, 1319211690, +1839734598, 98025503, 1898820039, 191381922, 1071988827, 346778027, +2076473163, 1923156889, 42870090, 904787726, 371487994, 1174099381, +2065179007, 1990282685, 2063040778, 837926979, 2070802548, 1660082840, +1062920547, 383910317, 240858277, 1821874888, 578052854, 1794193445, +840412869, 1649530704, 327206201, 856874774, 452646903, 256085065, +1309181648, 92993917, 1316491931, 226414572, 1946863354, 2098432716, +590780777, 775622219, 65186292, 312039255, 499083469, 300853689, +85727687, 423103458, 1603448541, 260765600, 654212345, 1927590285, +829298165, 1361679699, 1252981468, 925948379, 1531851382, 1392425081, +1592767896, 2055439648, 726498016, 1752842652, 660098655, 361867427, +1775381738, 660450687, 1118322932, 87583662, 880921452, 25581819, +61209221, 1474069918, 1248142062, 1390035608, 241286489, 2001493941, +1791774504, 709352275, 801736976, 1302784851, 876575406, 827516598, +850464784, 1956581916, 378456154, 2036444036, +init 1000 +1566269010, 1577817406, 983081823, 466847167, 1269997621, 1570102927, +1175203448, 387128547, 1152641261, 1675164555, 708054521, 809195642, +1154980224, 893776526, 1466993235, 1987264596, 1777519094, 1792057342, +1900130956, 212087530, 1214906941, 1386095814, 481453987, 572437858, +685038779, 556063355, 113351045, 1147151342, 1609864850, 1641590377, +440937637, 1789685137, 458387830, 1071903074, 1137640085, 499179440, +1927787531, 91245143, 204426269, 508877080, 625409662, 745281164, +599264206, 22418560, 1714492083, 2145982767, 686507795, 1893975320, +862119871, 199956756, 1333019389, 535957904, 645851752, 714371650, +1604067957, 974054946, 1803085920, 413150636, 709122057, 1006236295, +2072315812, 1641026853, 2116076672, 1963131314, 2015575705, 1754791675, +1596226318, 1376496955, 402027722, 718707965, 1312024918, 157830053, +860495892, 1684103858, 2096376248, 2087857649, 969316396, 344059322, +2098340507, 907491929, 54656404, 1846526534, 572433124, 1476099654, +1952268768, 1336999301, 815101974, 507852672, 623075903, 1602813023, +1112061737, 1788404453, 1706235013, 1830416895, 130726061, 1202957358, +1905013405, 17696991, 803084719, 1542037857, 1753073656, 553315491, +1037031163, 413050390, 1972842238, 490076427, 768679251, 2032313061, +1900005591, 1909296309, 1630406245, 338865021, 258597916, 1567660738, +1886914963, 37364240, 96683127, 815918524, 1278067042, 3952756, +720030699, 1872939470, 2030750901, 417006013, 971097311, 256405565, +454406216, 2143061063, 2080327435, 1110617569, 1518651660, 608778944, +1773476245, 436639808, 412565702, 2122330027, 813463571, 189556107, +42983345, 252282741, 750734589, 1836585880, 1849636644, 1128503777, +1065907346, 1951190421, 1508054477, 354656362, 1337989637, 1014835319, +1561677407, 1435373313, 752380763, 798814388, 1957637951, 179956077, +1406092512, 2032644936, 140940168, 1785330322, 2037803748, 1374413818, +1260471946, 1168813720, 1715740660, 325886497, 1206606207, 1743914311, +730716435, 326437850, 1555942420, 158875311, 1631278570, 537421974, +59088190, 1980156516, 497581730, 172724213, 2055447169, 300797259, +2052359904, 117801240, 376371077, 1568317567, 1497319595, 766659117, +956118239, 1219237068, 661967320, 2042816439, 1534887435, 2104452721, +1709596870, 663362071, 1637569290, 354026836, 1714337378, 498529972, +1779724846, 397501320, 720901087, 976717623, 355776524, 1834092419, +1234705911, 107143663, 13817521, 1411999332, 839549259, 889725526, +1879351433, 1946412586, 1983975745, 1329576496, 919590745, 1074674083, +365349485, 1039061118, 1069820944, 242436950, 641482727, 913581683, +876261540, 1647392872, 1937921206, 1929825879, 881678898, 982329413, +1846389738, 1639187759, 411987811, 1202402139, 1631049557, 1035015103, +2029797068, 1029821435, 1328775232, 857109758, 1991731166, 531949017, +756556826, 486001859, 1454625531, 1763854647, 631675719, 184649092, +893545379, 2050281110, 381164101, 557331191, 1763134224, 614249057, +1410725653, 1379973575, 1511233308, 212582416, 515501642, 2069735867, +746529097, 193611016, 1934357579, 220270635, 847942224, 1886818967, +1340917950, 368977556, 608474695, 576911109, 840222279, 1354234175, +2065802593, 1491578590, 433360840, 484954434, 1540629038, 1413861729, +70406799, 1583455072, 2034279236, 343804889, 1732753268, 481448963, +1677751046, 2071149371, 410272071, 1290290178, 534247187, 542242491, +1509508142, 500727695, 204146588, 1322643382, 1607713322, 830860005, +1251289915, 768663095, 1273968338, 144053432, 2118725784, 1142916899, +449238281, 212592138, 374885348, 494184451, 169912675, 2050022386, +1811877283, 584380257, 1133579912, 595920115, 581582193, 116921249, +1117736860, 88115023, 1172100320, 581947787, 1120270592, 1256745825, +626331590, 1452472680, 1993145721, 1495183160, 982652345, 157025499, +884519486, 1768290640, 213571931, 1557849941, 1684341473, 1230241812, +1091632646, 833725385, 341249065, 2142868457, 1853608709, 1080490176, +568276421, 1376926838, 637735195, 1093522817, 435390514, 1248677273, +1944464367, 1868385292, 964774263, 915984617, 1365167027, 1230848150, +431737586, 1639401166, 399922119, 927370301, 166480471, 529810054, +316432245, 695072575, 1973035081, 1395174978, 482569996, 541373971, +678894176, 1330306190, 590473532, 615541562, 124180112, 2010719946, +2027991127, 644413027, 673982143, 1337556209, 2090219548, 726936465, +803025765, 9941720, 225746830, 1717861759, 405792821, 1990870861, +1739348810, 1266097278, 388545031, 792104156, 1034851507, 235374003, +1957659503, 1548780660, 778628998, 1795062311, 1572515640, 1678158612, +896895521, 151723812, 1307029593, 1928424284, 348559864, 2062382079, +951246024, 2104159840, 1673276881, 1646390749, 2144609983, 545748263, +1825978368, 437523956, 1741371085, 1381271541, 1015120853, 538483106, +2049710079, 1659575013, 705531742, 1735748503, 445555545, 1336307753, +100946396, 260386021, 1723425839, 1922531334, 1270786911, 1803295540, +285720423, 406936151, 2083378228, 1362104072, 506278299, 66281655, +1772530155, 879502602, 72714215, 1106123927, 1940101791, 300477828, +504902151, 54825302, 117215879, 626805023, 686892667, 850679206, +1293075053, 667159655, 1145563618, 2030167690, 1430100049, 1961271371, +702760731, 1945844564, 1461201416, 744192262, 1405238206, 154907952, +1954621046, 1523259518, 1999768623, 1159020794, 625477257, 900800864, +644286390, 1088485681, 299208777, 528457469, 111395140, 1683097597, +1056119046, 4251645, 1652966696, 1582238634, 133176526, 138344746, +285754828, 2128525112, 1719157610, 1623808636, 1850815404, 956821234, +117150474, 1129021313, 780976427, 610504601, 1628878066, 1955252946, +616992500, 1271309286, 1723733416, 1817267056, 1019743602, 193462273, +1051893934, 2037915990, 252861047, 1920878383, 1365707085, 1185753156, +1402699015, 1369745688, 427988387, 1011936546, 136510012, 1258758184, +1548835887, 311827966, 1236178639, 1672407956, 667450528, 400161398, +846383170, 2079881426, 1546079068, 1442325274, 683650858, 1889106145, +289056132, 140354545, 1326110467, 931216875, 624507476, 2011103114, +1880127485, 1673665861, 1662834564, 1981977072, 398222660, 1557275831, +1047937588, 1068084173, 1178431401, 80296864, 1358199527, 1573561785, +580143609, 566615593, 601387710, 1088776573, 2077876630, 2131144638, +914673956, 2048285474, 11059211, 1953683466, 103310197, 382096973, +209634909, 1887166585, 1300166856, 903399251, 206167289, 916703053, +798690300, 1638870085, 727372493, 300208288, 347390601, 432906269, +1924077408, 947187038, 1012670253, 351371782, 732447818, 1569590945, +677103690, 257042870, 1323690614, 150665311, 1612322141, 2128112401, +1596688388, 270507107, 693928176, 1304295702, 1752879041, 649561287, +1572533400, 569542095, 77777366, 170386339, 2021926578, 1463129342, +1479202184, 83014597, 110364816, 2045756296, 1841740845, 126832529, +1834098154, 171638643, 582088843, 1643097176, 1119500020, 1423400004, +1790540275, 877561826, 1793330797, 300372912, 1593487417, 1830479276, +1498911560, 1847121722, 1051725080, 1747802374, 927047373, 941492819, +2055277505, 354162913, 1889442208, 1823866659, 581189589, 2026986798, +1523298334, 625266996, 1573256235, 396671957, 1903012905, 1508597776, +1483060549, 1315331726, 1527729858, 2039849814, 2014154800, 1181753309, +1471586630, 1211076991, 407276916, 1769518037, 1522242524, 1242078816, +1680672623, 1766016978, 1715122078, 1689997128, 239651397, 2128004, +263908936, 947318146, 945100847, 1838061580, 1539318094, 1382027122, +829275567, 1569882046, 705688589, 1407806053, 1813402212, 850675482, +1961073181, 145026907, 86472510, 349519394, 897945788, 863399452, +1065901208, 531434638, 366166351, 1210713321, 545218367, 393073926, +2145548400, 782955693, 1765822321, 2064685344, 491739241, 850350547, +1807891474, 914179880, 2135491260, 1927664009, 652214332, 797260284, +2043815368, 1744175349, 1220786036, 1383649232, 625688720, 36788760, +1146356168, 1727917125, 540113674, 564007062, 1859729499, 445212953, +104049108, 1331380046, 1166188473, 406846492, 27712569, 1779852012, +1744181400, 1033379450, 14700903, 336960325, 1105087089, 1947166654, +233362575, 370018037, 88032338, 7121984, 455108562, 456712611, +515680341, 758082237, 633497608, 4886464, 2002670893, 230767083, +1838406105, 141370929, 306689046, 1419863118, 681924133, 1489140170, +1085660270, 725801642, 1918642751, 2138754657, 435314433, 2121705254, +1985684699, 163116873, 1724867483, 1471730357, 1198173424, 524994508, +1583772194, 2092726628, 625972840, 1363038444, 881234242, 136543603, +812730655, 835472734, 1635357858, 290284274, 1508089326, 398331261, +1053426013, 1483748698, 1285522591, 893844247, 979464340, 1801611536, +424018008, 1347754035, 591529653, 2114332011, 1806546159, 428794870, +1040972676, 2046488098, 153141013, 1240978913, 181969442, 1335605097, +1715089625, 936188331, 1344831690, 244136143, 448170287, 1012075312, +1392491975, 767135763, 848031523, 1174197785, 2066189082, 1889450891, +1438176502, 435239824, 202737780, 106455036, 1824553616, 297201847, +499987415, 1134607425, 608396192, 677251042, 2030155701, 402970258, +569948609, 1742668094, 1010948100, 1977658738, 984749927, 1627112888, +2077086196, 2038466678, 1653833146, 997175011, 19317323, 1225718430, +1469762781, 1337789398, 1557336200, 131097097, 1443283387, 313351869, +331389911, 1870193156, 1828665818, 410101653, 1886158783, 1598060173, +471802754, 1953815303, 1572360883, 211877323, 1889232301, 1857329269, +1006787573, 716565559, 1434164093, 328738024, 1375628013, 372989124, +1713026412, 49575548, 392271740, 463232215, 1962248445, 356458153, +1140606224, 1227379596, 451859963, 1872051058, 1126455819, 1277227524, +1456117912, 720379128, 1274817423, 774192336, 1330206633, 295950373, +608830155, 72015799, 795331808, 2094638698, 1783650852, 1565187482, +1436531223, 1041782516, 1817038608, 1317740161, 975683255, 224013088, +1545876956, 210933809, 1852223567, 596416452, 1067144276, 1067470614, +1486931882, 1992346842, 1504479407, 423872078, 572501910, 1276519857, +1594410049, 364281209, 1305023144, 700962990, 1242120327, 1844730466, +7364502, 533008553, 66898889, 695933977, 74026318, 1505057971, +2061555609, 535848125, 2014391648, 1233678896, 3039898, 425922244, +633593963, 1099905413, 1244196901, 762198604, 664843818, 501129477, +704330228, 358309157, 1575126050, 262431423, 366472858, 1573817300, +186883646, 1797234154, 1576829418, 504867654, 1288982796, 366978291, +1647638799, 490027916, 913283365, 2024351979, 2076484705, 337959169, +1375037894, 1841835564, 1647008925, 1024649771, 1188738330, 129397397, +1666842612, 1922311433, 1685281962, 1591222765, 1039061943, 1068438064, +1901654105, 1245395290, 1457048121, 1560648642, 2131679385, 1929730568, +1058666050, 1060141144, 1032781762, 318505686, 1759205741, 913104929, +240122500, 111664352, 1938328983, 1858305935, 1170071476, 1078589492, +1831305263, 576967257, 1156272103, 1853668432, 1423885235, 1069236445, +373398740, 76799505, 1508478769, 1204810226, 139921540, 25296222, +1775050726, 1070339572, 1538705766, 1710004382, 2036586058, 157021750, +1328896008, 799515396, 105573906, 1648776433, 200274819, 1609618251, +1429957221, 1048386394, 1086086873, 921575972, 1593744128, 1903738620, +20595829, 756026662, 1710504223, 1461767411, 1382851745, 1969238478, +2023915315, 1215868715, 945046162, 877606552, 578901097, 1178110092, +660071002, 1023096368, 157664468, 650644160, 486773073, 184628872, +739444301, 1087773393, 776382171, 1102089934, 1844970880, 739464598, +1416957267, 520482290, 857692367, 617530923, 16042936, 2029902781, +1590953954, 1012080749, 158571029, 602934895, 549207069, 1710425395, +1902800938, 252359401, 16477979, 1659604578, 449255533, 170718306, +802597574, 1208707263, 1717931711, 298439704, -- 2.9.3