952
637839510 694856328 615263570 175375034 550964844 488792772 729336070 676164777 909803223 391106911 96689876 435959666 831850724 823918413 544177416 669845098 70292077 171960522 184289034 72611942 534029048 558610000 545870837 771604806 992051802 215285801 818168231 418844029 101801633 632009510 212358388 42308919 179886418 143631066 300768292 90037310 543546062 35126582 102768326 63870936 158645326 275357556 406212573 527954551 527274669 916309191 386201611 732130208 839775202 577026574 132563415 993217845 706937924 445274961 21237706 300756629 635695179 992831472 938725696 915547275 495866591 994861557 779382100 218978078 303559765 572602212 592696068 76409623 462931060 728323864 194125031 977536295 796353985 454255605 136435200 211470962 847011785 353939432 605587905 26997133 929103707 723405575 883245146 743612353 858468669 22273188 535682665 969363808 257162288 760777100 674009904 902034679 970073030 650633083 386541054 10739795 826215093 474041001 370165809 335003931 41701886 916764873 191195032 870428994 804731036 36772857 809331744 634269291 687209461 87980073 257747185 34867048 574704684 772757114 714278982 547502965 97596084 121283774 368029987 409945886 363298693 385298593 437165886 746020515 468451831 587068796 575867760 698087304 587542580 133930299 674386353 408958143 590534683 298094930 640478009 692970419 316027959 490116146 474930049 187581514 400916764 946926941 28026032 563781992 599405771 355543609 603156215 639623296 297153533 925271229 628309545 961063145 711973999 23972486 973445333 357173976 973020330 25213893 385143079 375078624 17386426 983353551 770533931 103128761 886171683 373510059 560556441 337398540 682294303 943903717 159541305 731402598 281545293 426482381 662296354 430743160 752536414 435127101 993053302 669031190 208109031 115305383 119804917 196885547 206071693 292678846 866171946 388614446 245688719 319486472 79766395 982414706 234780926 230528221 249346550 951785861 339479959 335629480 760585230 776902716 931497804 565166450 720454292 615160951 716661760 848983330 51887035 3812858 870678926 803688759 704305023 452488442 144544992 995052367 390998728 811676563 86656153 778825711 363474640 838066745 346953025 148935177 17635519 108155482 85167213 409473213 888471998 1708876 44503566 875946063 425124801 441087166 449428390 783152896 317243573 364927537 281285302 183889212 844374405 60584560 639006526 385058644 500336347 363266439 360750505 699601970 583518065 404481219 484555964 379954780 878990775 40900658 215914854 856472509 263887540 112129380 921405678 376343986 447750548 498046504 57183551 585690583 933722277 552498271 78679908 361147594 287097971 10197832 658665685 844291331 531627455 513381507 12691274 486976973 411988826 948447932 466126232 330230644 233857579 111212123 179824392 901169234 614805108 827251206 291445945 224929038 175346474 340843677 416841491 673650142 356273352 564021185 576103813 180655037 565782568 691070657 869973779 743593973 170864288 581564062 511284896 587719957 266037790 915194977 890745511 512663904 490853491 126233859 732182175 488969803 107649394 435617958 311422005 216978306 642196959 342514826 322761135 262218950 922947590 510734654 787512000 443637433 42707251 230785830 680400084 280833586 640268818 717768739 262283995 689916781 439367744 624121435 53771171 806356251 258761738 421954764 192656367 287692195 638348642 776312467 379096463 816652208 786940859 337825782 484122175 531281219 905522366 496448217 405867599 714368127 428047050 483500262 810103871 595203265 845574242 243382347 398738260 104151961 219874272 822174565 11727065 695857101 177544515 230601358 647398727 581241242 274715787 349001825 741124801 413934863 818238972 115915509 101868775 317689273 105272384 988434760 427192334 54592823 796769878 863334711 594529589 415137628 78954019 515320809 285924592 900953073 315637312 62457313 199536020 140341274 593388422 625226858 685047331 15061625 689613110 412833511 23361321 939598548 992656882 876298842 596669572 656982903 732107053 392343768 140755229 648707191 944795336 574827284 207178215 502364428 390186994 945884352 689475338 365315394 236289607 172383811 441473163 25797388 454620817 373573330 680272076 593086065 259475354 670865093 319304324 173289802 22937346 127250742 482326813 76926298 492304387 756379156 44185087 517346577 348338964 202372410 997142294 815800601 507826262 277305422 842837672 534597462 818489122 45934435 266663471 296710786 397701914 38335076 55644875 439791129 572435560 377850420 666251866 499352133 883191938 172424671 356102265 63395152 195436085 634662766 450052300 13321248 125321263 89795049 465074279 639577867 448619135 436390186 180707581 529723334 34059512 75408419 27156546 751493211 249893689 350451039 797416984 569569033 666251901 679195543 195458537 812515498 608295623 61361474 452131827 680765476 478349419 873965266 150203217 704434698 193354 636922528 547813916 234371011 270890483 240795751 41458757 307376444 672265178 387865159 524667098 464704418 604084838 60192044 888115784 738048857 540045436 204687193 689102348 480838226 420291962 26101139 986756403 181392488 536815582 574442630 213622017 152619040 401915722 373209603 685638775 832980898 323311133 550339979 988311299 556392312 430857333 984275245 769802437 115527891 244278118 337484323 511354780 276090949 140694146 627185627 271518217 610006415 492587598 229553644 754328299 942204824 901308680 515698685 45654036 612787612 4748601 433773626 64260697 485625981 456027314 963523970 192717213 58402170 133724754 643689316 87001722 719599472 939828774 887371989 24961119 332572609 593204266 959996138 143195981 303700462 298898761 704824237 655201060 231442161 11762096 866605037 882553876 500786608 132171263 897410226 148815536 910237675 923512705 243644980 905223067 799994810 945899216 877230336 738393066 689729745 841668152 297227631 235258393 601355062 76855741 413030567 13227499 15432340 469135763 158146899 422707279 731127418 801848114 907470857 659435313 640477870 811718515 708397557 746553388 118492957 98815534 194945554 269212297 835752281 343066985 985653645 485090722 304228487 562597209 172829969 137696497 261218743 441813702 386605987 993744739 875439654 598529513 326921642 873507707 482395282 380146490 19332294 898893046 401796353 318821327 435016991 174103471 237235783 388777654 107395376 811533494 868554988 128995360 349685966 917052584 718400981 877089650 420162963 83336796 401639845 178425399 208724731 242293770 372077227 504974042 104562085 809558678 837985563 302038022 828351081 341501417 325194343 725669378 484032046 646060466 236361168 339547288 50152552 410807160 896132750 181973236 773574394 58189286 767675858 666149691 443827943 894286218 598398460 165844267 226870297 218969111 261329700 829286132 21981321 979702661 126375996 891828971 464740789 718899674 23179301 55743742 666512757 944720859 294692633 764417589 843011764 412908813 308318655 867077704 86613301 387486414 497034872 302658063 973200238 25402256 493096237 376090623 341493604 671421204 458894496 872961460 499418511 125582047 974416127 634138329 966771420 205055949 897622314 619621868 719679137 152104592 468354160 978590212 904484036 979677429 890256019 67273954 145344400 505324518 97211720 297626888 15949942 183944554 424412030 377855681 714330672 378963427 216418617 300985198 776823958 648217600 619978881 242838684 668215634 286829851 737268442 692601578 786823618 921029253 8927583 688531641 981252690 254151735 765220558 983513151 592686209 148353817 978839362 908423841 245949471 855185294 502830815 39877402 600869338 879173097 225442762 869657600 844603424 248297633 956060084 632412901 920143258 729275105 61243918 467004592 934796199 283869148 174398911 622251198 165486864 72658199 905292655 901965140 316186068 812564041 769097391 740512140 56021933 842311853 408330891 946305545 887348470 205151841 438262292 921341290 578273898 231079396 945057027 42513953 496633896 27583917 627421744 530295244 266633592 429025494 272823401 136725440 79330004 828010116 490510904 666307172 731736483 373049497 805645701 158794765 116615417 340876880 851631955 85789977 569826739 736396645 482997614 892927813 85396075 543629043 568292042 738741196 652150614 789513080 261494169 670898463 343777204 890397313 428584162 549232738 134117959 311773979 552097409 517146071 296084791 395098388 121730428 83902860 687231954 596006039 274258822 701537206 485837365 707073153 924985665 705126068 820967369 345167893 519312261 35285345 282824339 784327797 288122883 497845890 559238933 9526401 471482963 133080603 950074349 731403327 400123786 250655863 902433305 343241618 653733533 545227739 568342887 467327908 486601927 193702695 385102754 612161749 355205754 801304579 319221332 987496504 420630488 662901691 770344238 526256428 886652355 395892957 563251072 248160277 769508206 143049822 830675375 786843903 268269156 518321121 516319177 41334475 313599900 59959369 320000342 37197170 542048442 563521421 897566142 751623539 945542668 185505751 107230528 448580859 105966930 447278195 37669653 696483557 345355571 702638161 565876418 559169885 547903589 807772916 515704404 238602714 612506724 554751430 174985441 444639704 241228757 421864027 662334739 904075733 930127166 97487231 183509057 142248135 160306444 266872753 677083318 224555460 577848617 452321443 961439370 33174850 685347230 173151309 190631739 525917101 703595491 672329863 129739919 163164273 442866638 697603610 76463942 276379084 319508901 291255472 326270495