P16821 [HackerEarth] The longest common subsequence (LCS) problem is to find the longest subsequence common to two given sequences. (Note that a subsequence is different from a substring, for the terms of th
提高
题目描述

The longest common subsequence (LCS) problem is to find the longest subsequence common to two given sequences. (Note that a subsequence is different from a substring, for the terms of the former need not be consecutive terms of the original sequence.)

Here the first sequence is infinite ie. length is not defined.

This sequence is

0,N,2N,3N,4*N .........

for a given prime N.

Second sequence is defined as follows. It is of length K.

This sequence is C(K,1), C(K,2), C(K,3), C(K,4), ....... .... C(K,K).

C(n,k) is define as

You have the ability to arrange this sequence in any order you want to.

Print the longest common subsequence of two sequences, where second sequence can be modified in any order.

Input:

First line contains T, the number of testcases. Each testcase consists of two space seperated integers denoting K and N.

Output:

For each testcase, print the required answer modulo 10^9 + 7.

Constraints:

1 ≤ T ≤ 1000

1 ≤ K ≤ 10^18

1 ≤ N ≤ 10^9

N is prime.

SAMPLE INPUT
2
3 3
4 2SAMPLE OUTPUT
1
2

Explanation

Explanation:
In First testcase
sequence1= 0,3,6,9.....
sequence2= 1,3,3,1
LCS(sequence1,sequence2)=1

In second testcase
sequence1= 0,2,4,6,8,10....
sequence2= 1,4,6,4,1
LCS(sequence1,sequence2)=2

输入格式

见题面

输出格式

见题面

样例输入
1000 1804289383 846930859 1681692777 814636909 1957747793 424238329 719885386 749760499 596516649 289641419 1025202362 450490003 783368690 202520051 2044897763 167513923 1365180540 640383431 304089172 403455739 35005211 521595337 294702567 826956433 336465782 861021533 278722862 233665121 2145174067 468703111 1101513929 1979807 1315634022 635723057 1369133069 225898171 1059961393 289018459 628175011 756478031 1131176229 753377381 859484421 114544889 608413784 756898547 1734575198 173594321 149798315 238664357 1129566413 184803511 412776091 524268977 1911759956 749241869 137806862 42999179 982906996 135497281 511702305 284420933 1937477084 27336329 572660336 259126507 805750846 732621739 1100661313 533925857 1141616124 84353897 939819582 201100507 1998898814 648233363 610515434 685990369 1374344043 760313711 1477171087 356426813 945117276 89947171 1780695788 709393591 491705403 118502641 752392754 574612399 2053999932 364095049 1411549676 43993357 943947739 184210021 855636226 849698569 1469348094 156297523 1036140795 463480579 2040651434 175960381 317097467 92066593 1376710097 27612889 1330573317 603570493 1687926652 660260759 959997301 485560289 402724286 593209451 1194953865 894429661 364228444 147346609 221558440 270744713 1063958031 733108109 2114738097 207905779 1469834481 822890683 1610120709 791698933 631704567 498777863 1255179497 524872357 327254586 672276973 269455306 803964661 352406219 700028627 160051528 240332879 112805732 220048813 378409503 515530007 1713258270 673363349 1409959708 277486721 1373226340 731518153 200747796 289700731 1117142618 168002239 150122846 439493459 990892921 860243551 1231192379 722597387 111537764 338888227 2147469841 438792323 1911165193 269441503 2142757034 116087771 1869470124 155324879 8936987 182275859 1275373743 387346501 350322227 841148339 1960709859 860281927 771151432 286452559 1244316437 71899183 1476153275 213975409 1139901474 726276097 653468858 330794377 1239036029 84661231 1605908235 450573793 76065818 705894437 1789366143 187231003 1875335928 884639527 2103318776 697322411 1939964443 312255773 1432114613 167854541 352118606 882436847 1909002904 165344819 1395235128 532670689 1351797369 492067883 1504569917 680466989 706043324 496987747 159259470 459512191 480298490 498295493 1096689772 286206727 601385644 272755591 1544617505 243268141 1012502954 372469739 2027907669 68338091 722308542 20388469 933110197 6939511 740759355 385228741 1789376348 502278611 1450573622 137127827 1034949299 654887351 1529195746 392035549 1335354340 87755407 889023311 594613801 1447267605 469321807 745425661 396473719 1308044878 446811311 1569229320 705178739 1590079444 434248601 1977648522 570503473 1402586708 552473399 1143408282 188213231 559412924 84167639 1473442062 201305623 238962600 776531999 1238433452 373911907 1431419379 620145553 1665947468 619290071 707900973 407487139 2113903881 7684939 1776808933 711845891 404158660 37370167 2058657199 173387983 1642548899 601252943 260152959 572713759 824272813 762739661 2025187190 167681071 1850952926 437116441 1704365084 276911347 638422090 143327683 1953443376 76855543 1069755936 337379101 349517445 588219721 1856669179 157418407 995706887 23089399 1065103348 625032181 387451659 569262019 1562402336 298625207 1295166342 157467587 1799878206 655319297 382697713 476667329 1070575321 260401259 296864819 774044581 697517721 201229907 1950955939 435939811 1797073940 856915663 1065311705 719346217 846811127 514829129 1307565984 555996667 324763920 155789233 231602422 489867277 780821396 619054087 711645630 195740093 917679292 206811977 1253207672 570073841 1414647625 735905393 1046741222 337739309 1896306640 443606029 1111783898 446340709 1197352298 15256193 1782280524 846942589 524688209 700108567 1566288819 471499297 2114937732 726371153 1927495994 292218001 882160379 11614777 1682085273 762981761 630668850 246247249 1858721860 648348137 105575579 64445833 2118421993 620223211 452867621 117679517 1857962504 201690571 213801961 822262757 648031326 511154263 1737518944 282828191 110613202 114723509 982936784 776902031 1486222842 50390867 255789528 366235169 1242608872 237949903 1277849958 777210491 653448036 108518801 1023457753 364686239 1309383303 229033297 1329132133 380321621 501772890 881999759 150517567 212251747 1983690368 364319519 1034514500 484237997 1775473788 624549749 767066249 86086991 739273303 850003027 1415505363 78012503 552910253 771294899 1344247686 895519133 661761152 474613969 425245975 415209143 235649157 548703731 1679895436 645032467 430253414 861543869 677870460 32026301 496060028 828388037 1144278050 332266733 1192707556 31308887 816504794 820697693 655858699 683571047 559301039 495132007 1186090428 174806407 1473144500 839000683 1498617647 669908539 1387036159 12895139 1144522535 12282139 1328104339 480171661 1113502215 860516123 777720504 643755617 1722060049 555590969 328298285 70636369 136495343 572576339 402903177 429202889 1503885238 319407971 2416949 12260299 655495367 561717997 1407392292 41585801 389040743 733053137 1433102829 87658379 1402961682 672655343 1900553541 400000553 337453826 181174211 1780172261 550956017 1941690360 410409113 847228023 616266769 1866000081 275526313 1586903190 202495393 500618996 189806369 1184214677 204504233 1061730690 286631633 2016764524 817226029 1748349614 376673177 1411328205 337390357 2009726312 696947347 1877565100 365204341 1369602726 730634969 1665204916 807056561 564325578 397893539 1010528946 358532287 1708302647 57756977 1874799051 526819087 885799631 414218599 1281830857 486418627 1156541312 318561889 1243439214 70788353 1505193512 212720071 1788014412 206059489 241909610 151858937 1095966189 104152231 1748806355 826047647 1369356620 70925443 309198987 887077883 530498338 873524551 37487770 641027287 1232056856 845790419 1251300606 59372263 1025125849 337100233 126107205 159473057 1376035217 382648501 478034945 471990791 1353436873 183228439 1584710873 93967639 941804289 26620481 2045826607 237770479 1930772757 747149309 716334471 252645737 470591100 125533459 2039723618 101089421 1899058025 277211369 394633074 83631241 1675518157 745933691 1943003493 553160359 1635550270 269110703 712633417 864101839 1204275569 290668349 1336092622 410228801 1026413173 773319847 1404196431 168217463 452456682 402539393 1858504292 235745801 802205057 427355063 1388391521 372796163 1452888574 380631499 126401947 304462943 1210359231 521035019 40610537 738393709 19485054 183614029 1291554098 755035279 1905241081 204187523 371653516 62033009 1047372231 807746119 1372261796 273785401 333582338 628974589 1894519218 786039031 1931513970 705539867 1021784812 586235381 2032894977 262692671 1859031536 438299893 1543324176 185433487 395279207 606199757 358984857 435889681 1344593499 378469921 272020127 488663947 2033505236 29777569 345367818 257675111 991810563 492740051 1965421244 216588707 1319041805 151519943 845563291 166077383 937558955 629593609 524133589 159343699 1215828993 409544809 74552805 27376879 1747844822 717876983 765326717 343124011 76593093 224311547 431530126 521186593 1502781486 703550233 1909850543 488803069 733327814 107734721 1646478179 825138337 1500474762 564415783 1941727088 672032923 1615935710 639806731 1738110294 406011007 1269400346 114760241 217871137 337745699 524305153 292423939 1265122573 124666303 1910300925 230449301 120306710 186894023 1007277217 551836837 1260596963 362575063 1255387090 122963851 1751378130 188714893 1130698571 350372651 1566369633 483689681 567304789 460613077 1155722604 35756849 2000419805 746349259 441767868 222336497 861109485 659638999 1460082195 485414639 952062949 577721117 1510080967 714880217 460686763 730387687 554290596 567963983 34740865 14887567 1830539036 390127939 690367770 534433517 1131359211 21066347 537322532 550245203 157272379 204627323 1910858270 412994987 1140384172 863794433 2059344234 682151971 738647283 772970053 94307398 51245827 10901063 146370353 628966950 620982031 1761250573 189653719 1003886059 168057503 410134047 138626933 1982945082 93189443 181271232 525829207 1527622954 412630441 199411898 264945451 1862875640 356684267 1022089159 726250253 1669679262 14989687 1242561041 681539851 1597141723 181208333 207026272 791449031 2032454154 217927337 590335821 513937453 1738909365 204102739 1603591171 595311779 372160269 213725227 1633938701 207621707 2106914653 15209941 733450907 587053969 980356728 32862811 1404515797 695748679 1289547084 279121309 174515334 811742623 294110991 517076381 245798898 91252717 1250801052 452825179 1435218189 235771561 670752506 225554009 1649709016 262178209 82173109 205816547 857490000 454333357 972058109 343945057 661955081 31489097 11671338 495405983 271059426 92028073 180785147 775575209 1687776787 570332129 1954696532 62292107 134591281 101323879 1131884850 380390189 1992576590 235202249 833215350 380311081 1370973813 603967867 1158381494 873199189 1766146081 340554607 1979015720 476152399 1694887982 803590189 820097487 209359393 1735079296 831768829 1604765404 206138731 1823796892 885550507 1534230297 464089999 1108399134 441443179 1078898506 342990397 1442767057 63299713 1623380595 387859951 298501962 309112303 420687483 769475767 1813080154 679068979 395191309 531742583 672139932 226723331 1907895021 219544261 1030313563 580508861 428903682 617909221 1412277685 233669089 476564285 188590921 1671735990 210794593 305197314 632651483 1204754116 484095797 1875641892 500037529 1447395528 451538837 1787897525 845897497 1660651136 61101361 1267889618 426247651 1640170337 763080931 610506582 164826619 1889804310 370917949 384370888 772634231 951426815 813274573 1390543437 216220853 699460008 67107713 1304811783 223712353 1730418657 710009101 856363827 787689113 846621269 584522053 1287726651 146533151 1936060910 28140521 1892430639 549228377 989241888 112836571 627992393 481928561 528433890 338498959 646755199 270754553 1609416931 131126089 1043388777 413360093 1844400657 286448551 629580952 396377027 6072641 134392729 620089368 836491291 1396918184 576453203 376696776 96055807 2060975266 764423419 242588954 49552537 445080308 335019547 1151297278 534322207 1000372555 879289681 1916250774 628806439 870305000 415522333 1799560997 332238229 1446648412 695466131 745598382 243565417 981914693 475179337 1539942439 87987323 1162088421 12548167 576994985 411522967 1489001354 53691769 507578762 502492961 470631541 750167669 1104561852 15711853 737703662 108375461 202550399 838076221 1887665154 318801173 1119399015 610486501 386839851 771476351 942724790 33488201 1466942491 788323181 829570037 301373543 916018859 222028801 1289360871 278107259 234576987 66355843 342146590 823578347 672563970 849725347 978587665 243195521 1599893069 283149523 2058907361 190113071 44041351 113974121 1928189300 131706511 85291638 104677 394709364 472131487 1671581032 437434117 158136104 91039873 878273679 87706127 1292413412 894292537 1209734969 434290621 1724916170 544311959 153162844 267062743 1020406649 825726809 769304465 198994319 1968922326 221713889 1934660183 80346047 411826969 178701541 1994320152 192532621 1762924393 279611791 1092637289 10150117 404259631 616734647 1347584264 562395737 1607774548 78374291 1550101877 752704307 1872666833 612353201 1186994949 550099331 2056665155 440157769 1369678468 29588137 18400960 338982929 781098823 187323287 213213171 568275317 1720185677 625040137 399493245 667022117 817572761 14933999 1499150323 110210059 25084100 103409941 379461075 472668373 318322042 187235627 1451042659 68423923 592456289 276225847 333293469 879451241 478841551 242474983 972125383 48520019 1172063133 90526327 1840019304 153161951 830365981 253232479 373953666 403068019 530788967 773446901 1970090192 448361737 788380902 421756877 1111088131 813464999 1077683174 590549209 38649718 496005187 1330301183 589692353 1116945487 122757449 518434573 550238963 1554725062 97276129 1692713933 379366759 698312496 717293419 1369893141 390848149 522971726 52775479 296596980 896925397 455843485 827385947 1670372305 278450023 28264029 311269549 1600206898 239352151 1124734562 530406403 482417719 263384279 1926411641 12718891 505593010 895873477 1587992726 124027571 198628789 95234149 2021303708 91342733 1374600938 572132549 461152493 597010433 962980710 84124217 649785905 359577671 1881049613 205629373 2086963638 503938271 1384079421 315227657 1715207829 836802671 1107096180 692458729 1367209095 689513879 1855843024 246137083 1254749154 213952367 2042010569 695258233 1237979969 93155639 1690492373 211800023 1984498433 17609659 1683932587 298167283 1514620094 499429657 1282291499 16922333 1759007339 115857457 1122551742 798487273 272312086 359147489 1666231349 187519919 1195950186 625843871 532495011 415675627 67874133 240854387 1561812722 422623297 454806773 556339639 2017881519 792786751 1549495354 660890233 657103124 486510149 331016259 193552067 1684677418 45636329 692981712 819485273 1862558705 304505371 1835342733 837626791 2002992734 307654829 1196774315 621740437 1947691087 245240857 100669 332702459 660916487 67974733 573556837 75245563 1390598089 128363597 1531585205 360995963 573666704 33596891 674402557 330769823 172623403 105418811 1424321892 57300823 703571522 317303611 529302443 418646587 274325361 217161533 1256273378 129834451 177332700 305564041 1651574882 325023791 550804899 751675523 310242589 311721383 1719650353 883799419 1286966948 62764763 1912163036 671068513 76277107 338346089 1604665417 750679673 1569115921 877288829 1756098480 845954171 1487105994 312186331 815774123 216408421 730832933 190099433 86086317 187106321 1219933931 263419007 145186709 724025143 240959156 695991617 228217069 551201747 1907712995 147867397 1435001171 147196303 763148569 299680541 1718264801 839425679 1538026652 275446547 1590105340 59658919 805251743 298720153 1805613091 144874057 1510906527 473903537 13798878 94255813 1564003050 99885167 2081362124 636453341 363304213 79065193 1360478499 604263353 775056794 688695533 1155465115 535286137 1389079342 442982647 1582482437 4744261 1642663198 253263599 844169939 133206197 181226513 286791613 1992865128 86478257 1485511804 750994571 1131352346 848934641 2124898138 245151199 943190495 641417521 1245036421 877068949 30387226 708340643 956134158 490865723 65120356 831190937 832077645 320585453 118993446 73673323 1663568111 801475877 78417603 258747647 707255825 22587503 44470216 888482347 1209379174 237335341 1874960596 547407323 1540846267 858829289 1396342013 618260767 2003980519 192048853 912194650 201533281 1069117832 42581881 562390279 225251987 185963953 627510643 1608959295 118041601 1848096107 827952739 1091714937 464180543 1281944976 270132491 375444584 189200807 2092720083 419914799 730199492 254615609 309766496 457676449 1702022939 50612759 1316505735 50881291 1221389873 273002593 1142930164 333584533 127052251 64564333 928682751 689442473 2089816339 214646701 1316953165 651291967 2132688302 117565631 1131761079 176919569 234262547 266222393 99568484 609707113 107939561 44804917 1029621931 838139051 1199420528 439388437 1295815494 753959819 1042517543 464837573 1704841123 116423771 1637840187 700287649 102524643 864892447 764851988 131207399 306851320 707184689 2145854098 723804491 110993018 331058759 493886463 342754099 1060494695 728149013 1508976505 260063189 1337856142 716916043 1204868098 219994429 307571472 256804979 1559382853 703386953 1010764797 454416757 2068224547 568122277 570840516 658581089 1268409912 673365157 1175989877 233261867 1704572553 582841187 592962932 802942993 959162035 703955957 1686518107 553048493 1946710049 599529137 33713861 408202909 1759592334 471569981 777635325 816976781 1591564428 185206783 1073781763 103463641 541110115 284546569 1457880381 461851021 505185185 228720881 2020432100 873595103 554602408 148938331 1659373349 111691313 384295879 104852567 1814634316 443457899 808808585 453668741 649022765 608034989 1953197930 682736611 1916237892 665306623 2054306629 546389567 234799752 598387417 1631596366 408581513 354367395 25222807 1245644428 12247783 487073847 850829611 1693485026 360022301 1376941062 100603793 1408960629 888830749 212295100 893256503 993683397 226929401 989230775 2491967 1233114544 738253547 263043320 138828827 173506518 31797553 456651794 80329489 578187134 691451549 1578716908 62299837 2000033062 133084283 87522686 198193843 1597848432 574596541 701539807 243849797 934618834 278480869 1244453596 196095761 819827984 556748653 1989352324 13511383 1336194465 831099433 1468519716 421825337 321869343 831563039 1460654187 495375871 1763360602 117305941 575705360 194064083 461273879 6938623 256363941 313823303 1940022924 343886623 1412017135 490387693 918483162 313556939 386753870 53102003 2044554163 731207471 2049197811 716898503 940472515 91066489 382926234 129183319 574682290 51445951 551008693 896551637 1435525339 211662889 1391927494 151402297 1781485213 167632849 1245466382 95275447 1974571475 601830319 409098738 867110723 1845716951 21115883 1010014811 616716461 1787189168 496768687 322334813 784259653 880492499 224048987 253674535 20965019 2115115464 636600773 1950148346 542314111 340563072 353673401 1438865740 876088399 217852623 683309591 680007057 199337821 503458793 125473421 2094613281 330546599 1279820114 356228363 2097657371 78053419 29860596 60188507 1594769883 17049751 209473567 117104671 1353825800 189966071 2141153674 707500337 763447433 308785493 96617457 566112091 503615949 437180521 919785523 142481663 65785292 237638143 478307629 745792339 989492335 81766429 523782140 36621973 1312313043 3602257 1292850339 362486741 634172025 422710927 75191653 81458233 992277052 284665211 1998562957 198619207 1374631287 192232993 1806119540 338078707 1953534826 102737003 556707205 309667129 192433878 576492733 104665169 258219151 466647227 582972787 1004011520 556139569 1564739221 627793651 245277883 729568613 1183912267 638128219 1992055382 18084301 713355511 267247037 1899542553 805632571 204428608 850621817 1904251768 679059893 1595371198 662887651 1569654968 501422381 1318141009 326362177 1711089503 610574897 1455371254 15754679 1768794057 122018461 251243823 625321933 1230674396 15983029 5631942 575952281 398068012 289544219 866596855 242639753 860144854 679952369 162403134 612203749 1138101281 366831749 215341973 894869411 1945891638 10713163 310273413 468062963 1064651899 728414429 1346941484 628257737 991505661 654829099 296528780 612816079 429363923 547772609 1238138000 760038319 216272000 343769939 988506952 614340007 285830504 55103813 856979759 245975357 1287572525 119382883 1758179117 278190149 1386214636 173521097 1173059560 284622629 1636750614 583332979 405201937 553918873 964263748 852143423 1182176620 155769413 259488863 578705371 421101832 688852793 2026478004 759239809 201407458 95266349 755526127 289914419 709606368 141356641 897534569 666586103 39848341 37623451 438485374 898027453 315813605 24700007 1624064901 588873169 861838989 213331873 824722490 367040929 1667250732 888986227 871700699 701943707 1597272000 231189559 33165457 218373803 1820042348 259643437 1530130017 221449783 7426169 138172499 1063880569 717032497 1179529128 161415113 136135018 319377463 1999038585 574620391 869921280 167368547 251836754 346502539 1656241707 213675733 1459834400 333480527 233233021 79601461 2122466788 204933721 1681545190 672255139 88639634 814710629 1443145325 108681977 1626870461 825791663 1782648142 734296639 963964191 699045043 203845520 343493327 512976554 339980519 1215387142 364531477 914600930 285308423 531900034 266437669 284327308 40658083 132629780 844161691 374138644 365862799 576279545 349121743 1470796522 110341073 1921376925 659436161 1825051735 317038577 1320634492 404438549 2042830296 55798973 791251530 859310831 1654844049 95097029 855320512 20336959 1335077589 270707627 384868448 102194881 2008532428 16768481 1268632557 145376083 957426576 501262339 1889537797 431565227 1767125139 318333689 1680687005 190437997 428674782 554580277 502390523 106242869 524135236 23025007 1410681417 419481883 631340353 54449293 1278792724 138700759 1049546350 334113229 159037710 237140257 2057337242 543906161 339335164 118386029 1460674641 707967709 2063762111 270617527 861746410 5816267 1602182790 481387909 2124149955 235386157 1571825916 405341077 442482781 274216447 511583958 66618007 1749757806 122265359 1386099901 233614501 1976714674 517408967 372315265 878777371 504038566 531352981 1115917669 413892169 1075259134 555252839
样例输出
680482245 745650881 116101184 407638111 0 17714340 93833285 12968 433643752 0 135238050 123482065 4362236 274071215 26163381 296270370 87200419 105431022 5630232 215849603 566942080 154483626 335388238 186928982 749311861 91945000 357252796 0 352838556 222750402 0 493616407 38765436 0 52859140 423747198 594336942 151574371 303429475 0 124923132 106224529 624592458 608444999 872983085 328776252 0 411400303 167967140 68721425 558838230 563493678 660629233 435009970 160935518 0 56450545 123900564 466009110 52753503 659399116 111979059 141593021 216646817 0 700329921 0 0 482553080 306467336 0 208779714 38813645 157078048 600113784 0 141921271 0 515261962 45430517 7742004 9314815 0 25217843 306775553 357791197 254742624 443255409 98499994 46857798 20178237 116512 151881751 0 0 44010831 290717453 198926001 346706046 744244990 0 0 159178401 380432552 0 760210140 93242883 27345948 429448845 285262222 83718816 364191598 248096683 0 137418446 118520709 296080370 440578071 2573411 157592753 81824435 82214596 805440461 178779041 174211825 49043853 320078138 309057267 54406821 221836084 440276934 63143413 739252215 2472138 103345288 209373270 0 14765417 558255472 419114256 308008740 276746258 328877592 250170096 116161770 477631206 5586732 10420127 284836128 219929727 690155588 0 109183462 15541536 284504308 61010997 829088444 621686240 312701628 603421754 144069136 59683925 16037834 708025107 0 383567162 14655730 89573019 188144210 0 267680706 0 0 805226562 429858891 55734471 674015989 736420240 76592088 28141098 739288850 658117556 23351770 2491512 232497720 42123873 283614669 284352339 192856329 0 0 0 0 124696901 662216438 137022296 569608710 741340508 217329836 5975957 125655575 198761989 140125852 350186330 321191737 152697425 140364808 15062562 94308966 281895839 0 74237413 279824589 588097352 383321644 0 0 254958938 187729922 603268278 17323310 473418379 63608934 372474869 163493490 120898872 0 25520865 188165234 817659681 305511878 0 0 117088619 0 571033847 137131174 0 129606313 316767343 298639140 0 0 0 98846781 237426133 75558991 426899960 752075740 418359924 432642884 199952946 116352737 271185803 238259439 0 691898882 128581396 0 533411560 677158431 868802057 83516584 58591002 300342141 0 0 295796382 473148011 27493848 232687229 899055851 0 336757800 0 135967771 353671194 677040453 468532120 805343630 60004794 0 221773242 588960225 280357670 257316644 495765702 0 0 509666902 247994093 133766388 0 409177068 603725873 300233512 68104085 4549008 220007000 236758609 360344502 288178964 316915564 9090715 143815345 106303941 0 18259223 30099882 0 146758229 523541648 0 259682994 707049317 143205203 605306390 25077969 32160825 544998112 99331162 0 0 78581430 6904086 160444907 55527088 108708107 543090620 285337592 125859962 0 498134534 102167102 456940386 200936783 0 0 659010518 475430407 134595010 186997426 83307179 58678825 154637523 0 374600664 0 222479826 141078172 257092564 425887713 42607996 0 0 481772220 225538816 186908796 64106888 61631608 231355974 38113636 589078192 238990774 0 0 336944552 795918830 100005340 0 540004510 185420725 137660153 488067051 0 472040604 522054999 279727577 0 643665327 152650110 90135100 82695989 753037146 46801517 80884128 679284505 125764945 0 0 117740588 0 703782640 0 137827370 221172 0 0 38346398 0 35801272 432967346 160175691 25452111 499561392 501005813 0 160990868 48858002 342276248 86046186 313129186 12982010 353958415 10310175 142531788 105466943 172063349 587773392 0 0 181215674 0 236192116 372418240 431264912 105118482 148477165 83706426 0 557327493 353280381 822316578 0 30821025 0 8554503 49036305 121859949 229702780 248062847 139924890 84279833 386143624 136342335 49999397 0 132369752 788559574 444907098 697461822 266800692 157348301 521505257 305541664 82097291 178176563 29484243 0 0 436340834 142652718 0 467262794 0 0 316602090 583608165 158945269 347420510 130714938 593135093 59453775 48513440 22030844 12066185 148480802 418042971 474904979 602803352 425224481 546457644 101187886 219484520 991659764 0 139407833 123972142 659963835 2962863 5313610 0 246899353 60577820 673963404 367575358 176908268 87737882 30233689 235892232 0 128103027 82111419 147504531 0 90467976 0 154990662 109266157 543377919 0 28694386 668530779 0 0 0 275087661 132246370 56268433 708235133 179902620 41463672 181362368 221981373 250472594 363709688 215300693 326761581 268433512 75196472 200401690 153101681 18978757 224680727 202726214 293292648 397784408 613322936 90894769 0 116172574 455176353 649815635 11818852 0 2863084 333540572 208181083 804183772 196097449 133780795 364555143 0 0 204810344 118065975 575038225 360653964 130275540 817341540 206095662 88987751 773579398 230607508 124000550 0 500278720 373543113 394850893 33103566 250804937 290297187 352031629 64540714 24598112 393117041 473568646 0 940578509 64244684 343137719 473645161 0 0 82567780 379827504 0 455605459 553436042 10018198 92616325 527797725 381446147 258398133 657152235 121581289 657477471 338348235 350071217 0 0 206072078 0 240568496 322665298 85049619 0 811242607 316532423 458958072 380374524 0 802019788 218247021 167128970 597978326 104109173 875907972 16736320 108909895 0 58782819 49750142 0 515086241 896315090 449392867 6078184 523582136 343914491 195282539 68981286 0 715630925 194297064 203594542 68374845 205593650 169751589 535002920 0 801419845 624290288 257953580 716835398 479609939 109500874 333672960 0 0 50684792 330875686 288036976 320100464 135107386 383435616 564443093 140136709 85996890 845604408 0 0 214038956 268157916 55927760 140087670 411147715 0 439433792 51940858 496954547 178900541 43021780 315154748 158792768 151528100 39029543 246793784 0 173092491 173623537 0 29312640 0 71206230 89716545 275642928 33916920 169463884 211579305 43235937 67215142 886475306 0 223748678 836323043 499212413 154510308 60134130 650545106 739223649 0 354143890 23114162 64493910 386244199 0 46044746 1474910 0 63664846 0 0 0 0 60463524 23553683 0 3142664 22716189 147768894 550497581 0 0 802540466 976652135 0 84017010 160295818 246181092 0 654714305 228893998 362856721 357583062 773705493 186127736 139175235 0 166445771 271163753 271492162 240431628 326088092 377157411 0 180042474 64252975 84983475 107797161 227581927 184210464 0 0 0 123103904 0 232892406 17834195 305978393 117778017 201888722 3294384 0 739770115 94137773 118525861 292685015 168779590 345187307 282589744 661680922 270584573 266516008 131811968 925325928 268506748 578760900 506269516 465741098 82413492 622404315 53574490 59762164 297886241 356811391 251865481 653259905 17640999 0 243944772 485718595 774564220 676448622 64519697 73582331 260182625 162884313 0 54286017 714901058 0 188827259 31032007 98601525 26808825 245736555 80139445 882709322 497141198 560539207 791510805 339525592 0 210988713 530023540 104481213 335555364 362516991 137852064 201855636 516272912 209698991 108878336 0 550778493 25213430 790900990 0 0 647022576 0 56985787 581928620 160301663 5939765 0 850124644 257200883 0 39821980 0 7162059 268391534 111608756 415785540 656525961 0 24439726 605467728 553254243 4210465 254593479 411857921 0 0 53666294 606056748 56204741 35041536 567016983 579981755 143619489 140364168 233356756 664858725 128455249 179130806 297110294 604680633 0 225149607 633696165 679855575 50578483 190857112 9506285 538625916 0 0 155395706 0 145064636 0 4969680 0 382363665 25956866 380485325 77784631 64731354 36638872 501513117 19234585 191582405 624706303 0 25471476 147404300 6998464 381204695 0 458297728 483060290 504061152 285212588 253623292 429900633 552952622 735705768 1883053 58254937 594987816 404029260 49137550 177497497 787574365 64385142 74232659 506359240 323845180 0 743215838 148054918 255150442 84236643 0 199119740 907041190 384427473 86399013 411161 640754965 10150671 450778274 0 267423241 290853132 110799486 27670557 0 57243195 0 809261169 532389714 122284981 521004462 0 459227402 807562980 686908788 198270664 62968633 261773400 27084416 0 0 222589069 163273995 295968980 63892224 58291719 495653983 238813159 333900459 0 26610602 168232922 215019780 167505754 295265144 511102637 171803567 55006611 307932311 914342184 34859307 514096176 234059638 0 222278527 26505590 180095784 177331490 0 445614129 219848906 244480770 96147890 327801441 277473650 0 488337204 692287498 145173164 716414514 2363891 621025325 0 101427565