949
569706355 856588483 951740482 883190894 848166657 307695216 401914142 442672511 296996280 723457434 354200213 155467286 87706319 183908975 337542475 291209226 522282388 845883678 831341695 936915565 223784137 232178881 45249633 583509646 115470447 924590805 886847471 975059952 890080896 764715482 140439447 729215463 579286214 319183771 971971873 879798074 233677287 753540769 615524908 819421350 991850431 439724446 879769765 827119600 452713354 369981217 938750637 632336594 939036503 426868828 202787235 688906977 352246591 907330888 46005240 815391723 496372618 809680557 683508648 142789423 420377801 118839920 413141600 560137910 543532062 501938242 640606404 649415957 431439435 420391768 356474449 289514494 334918398 441632971 937536890 754996305 683613311 602616782 634894962 394124667 557509183 720074822 545374859 686054932 267634700 604199686 142746566 842954422 240833716 71843710 367782762 162874662 407562747 384874777 308705271 858400847 448790944 771895681 15211981 557725721 193047160 276051193 540340043 947360090 233537370 647119965 52757841 103405223 275411330 745866714 237641815 632643921 104311045 564878857 455187658 49038662 172950296 295759732 203999366 258450447 395367499 525562612 447481142 388963411 2906113 75375651 348855830 490311949 238674917 998895581 865545615 65790498 794718919 42512936 857790903 824598788 107410487 350105635 862510931 617604369 623665495 614557124 937003682 820771048 548719065 596944726 264694234 318116190 228858848 345742453 770018368 357199824 717980873 648220750 624418634 981543964 334971000 57345396 127487193 516283811 280649967 194041355 882546581 607557454 435888512 196454459 701293484 680076774 376284741 65872730 570250542 99731095 366760746 176875734 91144246 477678105 549432462 552223210 100794251 502050695 111341434 912444534 387000114 783767644 448520992 929299041 116799006 441643058 774144699 408568005 91250178 496642510 763463433 940958230 466973309 860866322 739791942 7708779 387762028 635343720 990111769 632348340 247902998 115423085 816854147 683648405 849458000 313667223 739844894 824992133 391415348 193692445 148919610 254066352 174879698 713528224 678348396 520109588 260460036 240486232 165445766 812409439 822690387 490794994 270999747 431195124 687908258 327272645 751519194 213063372 892413163 405001538 551832556 907265926 160011798 556490547 262498596 428971357 191612494 3032937 315313009 676385633 829423631 57073102 804120604 752791700 973399682 153995906 288678553 919842405 176906298 805195736 668911612 535700790 415881897 118682343 920161093 898057409 196026182 915901454 186542317 710560331 951565687 994010167 903569814 949295843 766761650 57609192 444954162 193597939 15853391 526320167 910566991 744904303 55620682 349569389 2003325 876254234 22092415 866725888 374425640 170145416 901788642 281333972 792281063 519600642 872524811 773579630 451936447 515892057 39577175 154402844 130858940 980710367 806455835 670052050 719468095 74178726 783230069 543859792 109777431 122886776 445446219 41627861 486412159 582732609 939984125 606819142 315408121 472377681 980307412 742368898 436151778 171099584 819813346 990351130 269948357 278805431 797672341 97347442 193899219 649825827 66498823 310571871 893758727 861320383 666966688 202904768 392868124 361450422 481179240 942226862 40392551 998395457 729036247 639389422 408575168 109771685 568654648 672195935 692676783 104771862 146346391 402644515 13520622 136562268 755873308 283630823 808731903 988152936 136446870 700894955 94187003 35152893 652151895 11911384 667190977 251644956 821045243 681220065 574466547 10511727 750657770 886574221 550532012 247895835 264386393 524045064 881253210 58781939 533715623 857237846 798032292 882593624 785537219 956705504 615400332 326362593 397194602 119786362 829742751 863708065 316714429 526401387 606464236 566740503 952324737 66327919 407738182 14538 857380904 614590979 296553142 229107368 307027105 152091766 926080926 223643315 619420245 721661919 561942716 395585164 359230747 736612339 38295264 970412514 229756061 546290582 651564101 400675396 638360047 978164021 298092811 818708704 172226622 354062743 906353396 100059096 146911885 619283170 838752264 936959386 819333099 360103688 941650733 134872669 283740497 893251452 379867893 816351825 518884792 975505564 87456216 375374543 769892056 249804942 551849225 658334243 925466821 943344244 969724007 928758870 604432516 321456266 939625936 235341633 411135995 676833244 933120847 594068196 660244904 433517079 602717561 778794584 641850467 498061602 418002378 315425580 227847114 103054988 433670655 612256858 613543478 945265822 437518577 303781446 329524023 634761645 316404305 956371466 641650983 53679859 813579350 439080971 569666138 434752633 966662883 837937781 661669337 711040114 431805368 133895660 174255899 664885233 575419924 477800775 728365180 833777853 31971751 72940785 19154923 268507385 457766276 211927286 837128452 264525091 13298029 275622975 859653666 989352674 412627949 521254942 384658987 378825527 449601231 928795966 513724195 885663583 507692530 372032237 858941838 874176321 124372434 631735738 148699519 54829890 774667264 110712438 330647450 955565668 801726697 994717370 749051041 876838379 300304890 626795797 42525030 554990778 761881192 351851852 336205695 962568607 991497218 563791296 1333585 734467911 354760917 147284596 768687487 733993926 480571365 513189698 196079156 179796743 53191430 425195416 617843494 925482278 469000313 113278530 613943552 165235779 671017805 537807820 746507016 561569892 152215932 413167538 20531638 960968504 577587052 323623848 912014499 690096017 435375881 559130885 278049900 667503972 166129320 950806709 168933195 861138186 571709225 74107426 918957651 76680735 467843824 42202683 540405043 30680028 741492153 770582958 447710250 920869671 383204837 359142439 626772557 13552724 682402784 179047837 175400548 767859193 427745784 669925801 104198301 420522639 82545188 723901163 74857948 365115397 600356965 417456753 973844573 427088043 616166531 495971491 467684961 546263330 195013230 526387847 189477847 750867325 976097457 20939421 650410741 800263998 968546959 912410077 657474178 145367571 921436001 704503893 662891460 481564747 389742734 641777397 528330193 527758168 299396811 832161927 462413025 790906268 918280202 985732302 966006715 168996309 164577947 690537482 852719433 498021931 991390801 981373274 415838853 184176539 149495759 223983114 191004050 4826473 609775599 969231502 678091511 704891169 898734047 561269656 812725380 92093480 747103220 226105547 948185957 208623617 183645185 667965261 807988328 913970439 939189029 911331915 439057427 111579851 386693217 853383000 706963579 970000987 448552326 430158926 505503440 444615827 942423607 899113716 371261683 538378163 798891264 589707745 330483306 458907109 251114715 240701109 230909443 746507735 740588026 122560205 840715888 254524208 910995325 688548877 860950336 745208294 875189748 53080388 375526551 979148495 670026460 268114784 288670643 678035343 739781678 152277947 799547769 292303345 817219188 996752080 883189037 362817052 631949555 300180740 617237485 334221698 819827130 361006794 502678914 459806783 488333887 989636580 420194402 643913677 121189662 229898351 661380194 978356761 828070540 429250322 192861934 34773527 792139080 611295921 90503177 652866315 846468525 292900783 709166069 691614106 234852795 964279515 449816265 62479564 72374427 598307681 861177785 167923708 715503936 588391183 741938072 445830828 209418053 257929880 145363977 398954685 501615959 694545725 515812546 952229604 100122593 786212456 468472725 428572020 885879027 55666696 611857762 700718621 838192765 831851430 646949622 163685923 535578621 710764071 698037452 450237968 170021893 341001853 632854781 545168906 861994030 5023825 556805430 804382816 8138450 555020465 129580398 551746481 506350769 167409024 379853647 635635611 80538268 365876727 221032834 434594695 240123721 298590687 863589752 610303880 19198590 947514470 173457196 38325210 429277135 250744444 115213083 779319670 688885134 797684689 87896296 877808076 89914707 287376828 766618855 744577145 331075093 478638104 634478194 762562629 821335251 206608285 582069509 638457534 652756773 276196359 910960067 800824520 53915992 570651642 619046942 168858570 366677619 202956367 535917465 316370292 939904219 373690921 755795398 241293450 171161570 657147660 852547 594848397 758483237 518389221 789195031 647579872 596913206 72488250 143536206 917087513 674633145 577293855 769724635 340643750 788182733 689810675 180530722 941647175 121951228 488942327 929173958 370303493 709050238 316554060 247073305 133526230 140659095 119965072 241716690 984281717 386328598 273347934 738073637 7469862 535216221 258467670 848448715 907041700 663201321 360911647 847369595 165129127 324520100 814433755 175237739 679443180 283611228 62324236 813540741 745232842 619403097 330569128 215053916 809895730 373865418 920755343 869337838 599144299 871798200 117321738 535539747 490917462 741815643 390859759 313327816 387834699 112969120 685462008 926226392 572446997 719203927 835498373 902330598 239539378 506956485 432321804 402307098 10864892 388578327 500651392 58721528 874126897 545216425 522870005 630796223 316822358 177744946 89981839 935803429 653758600 533750015 34794436 632687642 935920145 830555125 201859008 583373176 166025151 243948718 237141066 336707115 652972567 686575219 239362463 391654082 493933305 729991741