962
841375279 771628796 705051392 35982781 2371445 464192512 606892341 821568987 386428349 833819389 522254477 493418418 795788467 367971050 938643597 87767916 833495400 2140538 971531753 598450646 495279624 638498153 727098122 233420993 625845930 398020459 512274551 226142291 897063920 950509818 426564565 155601331 340540493 363661978 474379409 599771951 559962965 37805011 446833806 721071120 408200114 557592316 583999141 363102788 822113889 811327856 843544103 865375238 116607435 279738853 87943857 47511548 517716292 847250605 755015301 571252509 309731603 307195697 317290222 119464487 146093408 138092510 244466605 167785110 805220571 722495651 333826935 913595506 852588604 538861607 5027736 566462239 397430405 584822604 144510520 843961430 517899340 513813760 679441107 43495626 357920360 835846585 627482786 399565230 559659833 78523447 561806109 635312526 320638230 480268936 561911776 967304815 842141116 637176309 378655967 90539990 24632534 492388834 78108604 761695103 500046508 926979320 913231465 959694140 905615110 544067840 171774701 739053471 408777154 814391863 401445926 963709795 945177130 334109193 829957207 969028079 805566824 195184897 993234055 704170303 475345603 268409938 129852910 63524808 803962111 980657557 156456544 882608976 669528232 110224223 419707747 458924284 255199548 813653746 259172856 589685973 84664279 794182659 394694457 11914174 982439786 402683004 27194123 975715861 791761399 713021302 718619755 153650462 874231808 905015103 553704653 280568238 279371318 725738521 62414407 640675520 923348977 386319532 378642539 694956948 209861617 171647025 764211396 390010323 728263550 456978912 591364875 701838541 361201672 469005797 912454026 437268842 183835045 11248168 556795611 489201030 429820326 452399820 356591859 771967750 91904343 208355851 919617532 356622792 876283071 605104881 580701950 851128171 315492075 751098959 923481223 909127373 240089721 430396784 397713742 764845491 206154747 584446237 173262820 805380772 370948776 285397957 563089740 220932865 67001129 804925278 955627852 133338644 41531082 751040707 614845215 717103554 379948440 636438160 126594044 251492158 147223833 374438210 863796008 476536461 819614664 351063638 194955570 944013106 995360619 108722232 416324195 723039742 729761318 495214475 665989426 20476476 601253197 859441447 575372509 337384270 785631883 76189693 349076914 886237835 858194487 40093446 559985174 856588456 813622105 852147895 423682429 17419726 137567934 284191015 323450333 342451753 786280216 715612600 689029744 317128458 474412061 482561966 78398889 893767882 52264801 431183631 269986810 701876355 214373338 867714824 925680986 590272208 433663741 259749704 171115609 757434798 62298472 458616404 452178865 504624136 497799429 236086109 139982571 200146653 329680971 486935727 254015063 106724577 714621245 314755478 707696622 969196326 261658646 406184640 640274114 356829325 440969470 91757570 979226448 533957845 794656319 701970739 892546060 669540571 760561188 560592222 212762154 45646006 228402457 431529418 612591154 462824880 958002082 303255913 429516760 356762262 660600938 106578253 336426602 122699656 729303081 487646214 582126635 659589536 624310962 83798973 551602821 588018759 307126493 844059446 276029506 878272706 702151532 205180394 140636601 438251239 889008154 778103327 81650066 977208706 195078546 649891901 215631448 112181077 748230583 270455817 519837 890240758 688448786 442638455 671802808 159111529 687242106 850166383 896342580 412533459 533803697 350212827 876097609 10804090 169832288 451533615 890501767 792885753 610700333 303485900 923950824 492629849 696145886 546575379 89650452 415123554 558870336 607289444 870085180 415604284 717411371 658497439 833149859 157066909 390067758 777921528 900002076 539256611 703249904 513611074 82896450 231665887 851369494 257839441 310376601 703521879 262200574 873558471 76574234 42352560 318004199 275204486 321697055 861541771 417952674 61224538 789451943 190039811 281312803 80152697 226076141 279061594 442025872 578408618 133137226 920213063 144608173 80499255 714348196 341009676 917039989 140861396 776919214 354409868 320546206 865524426 269483864 36065785 166251099 399924662 101747 501753112 119580752 481814341 2494286 213529221 150902540 308317949 609944181 934582371 552113484 733505740 476910702 91344476 343016642 655553182 988929276 260677970 148717293 47808082 568493136 490975602 459046971 246768281 766892299 434894580 981009313 411254398 496654728 563969758 405252736 476203239 407816737 602755575 300408307 876755964 886905645 6894130 930704527 728873288 776963239 788398698 877116272 951778349 640367850 224140444 280074356 488031550 128530229 687385087 643152171 880764382 692521202 834725865 415642102 354635914 616943117 918466299 297562816 330891722 204928134 445106982 778183152 778743844 101854772 700914372 949709366 966710997 425210393 499929886 947048402 118753314 461923686 510428615 845015743 944948970 953837379 431063588 517314543 170667725 204703351 323288107 1113362 435731921 152995039 848932976 918115282 829586241 253508241 701699257 442208132 450054389 429260880 363999604 758099893 683019768 207801446 397027027 702480418 200566512 620239442 284693333 68785226 938059909 93334721 203341790 416719267 527331838 213774672 70351822 430828886 398484565 424947348 459249229 126320787 902701890 64011730 810054221 205263537 636120489 10971414 474409173 626632818 757836137 932572514 240440107 338461996 639756018 904164853 729251261 927277028 130594822 227109341 212054988 440241693 498916349 383790880 574299976 328289509 554489219 439170403 810260837 74981682 122026337 994556055 653807249 57879214 421455213 39001366 946364069 160485756 911508022 151379849 723746258 227860813 988650690 930522161 785102496 392368888 268506581 937239431 761613822 479057656 822329713 194467762 444055738 737599747 739664462 572370247 126741088 778692931 260462884 58798385 662879139 652292176 66341904 981775216 712886790 441161710 237246864 488331463 253574881 324128119 573732553 863098679 273324827 897990644 365174131 610773646 646871179 89501621 862908636 103835935 120991919 304647511 753994230 811879112 540449674 35232292 70974879 90298210 653171914 529287690 874748317 722869299 144485408 181699776 555147259 37629758 568729799 970821836 646942783 939567044 195579529 378488104 879907721 759209013 329979693 817395196 396187232 705935475 446505872 854025888 882976878 789490350 120330898 485690021 275145413 699427237 900545815 315670734 684665117 271876525 504525115 654293976 635013514 496110670 663161324 126207474 125823832 525247212 149238656 383526130 368207577 764913885 222445783 748780219 444571939 594968986 151370450 801797818 40296009 497321874 698733068 43022262 803683528 734525621 513901393 617262328 306739852 757947842 809135297 576400808 717839689 492619203 284170327 912714283 380892042 980999348 6196948 583002478 321575982 535359854 533729382 10230823 945516566 938429305 377699413 793508088 713332189 814808434 595250669 843985723 420538443 911595432 265185473 761161713 420585963 713355954 195584866 232556684 476251576 842576545 76097027 784970050 307115187 962944528 174895414 781521363 472501503 405122479 884872563 157065791 196517564 502334867 844938022 76160699 555738670 467821884 421629551 416018922 768766901 742775059 421426072 288728991 677427724 784549019 291846464 140416471 277277519 871526107 919814363 86907426 647160903 224899632 223881197 411341531 610014657 327944836 519273424 954017511 583732208 86042701 843416556 210403014 514793844 480519275 970431749 295196875 332046449 282716551 258580173 639903981 831379440 558522199 249513554 9744388 925819891 512081784 899778222 833424466 655226742 361945429 931816567 2266074 800229814 718411359 951868410 15210788 132064952 970841551 290826799 660222105 588380102 544326726 518152378 542468926 899783907 75417751 383529104 832232179 339831250 538127406 930898081 515980887 790532010 770746061 311435470 824506714 900525584 170915954 258972784 83109355 416463835 101443717 602989888 367653894 670258329 789001732 203057829 443136837 668294919 413513106 886992929 465884703 528391255 582320659 526933213 753915552 196070871 75736857 47430147 137455937 490027351 378192055 438499682 223870834 120371023 604527590 387824042 232672634 884470910 640228944 665015058 75844526 66192695 121799520 956622963 159223408 587965382 619943106 605082027 57132849 370593340 623525020 266011534 406051402 731030862 54584473 442899628 592727778 36032014 951002234 634147667 771752761 467809551 865633344 378198325 559748522 53753547 326695835 389156282 696554578 213080905 765355817 608984947 534528319 476563339 873597374 823183356 394580064 951365577 433424340 649331039 750877934 696582271 252143850 809242512 41254651 174648620 900881125 511157657 892625652 757246259 646456873 915122534 745334654 842774874 394549615 620768142 232732674 926016841 829208296 476989768 823675755 253903281 192324691 381358150 720863639 434723592 846830547 825428349 826585563 700950016 898736831 603183676 277087992 613696479 41238677 899787853 759675233 368533522 322864012 817696896 625147747 403742446 287466514 416469221 53946585 622616074 77259550 844941215 963281461 919756694 718576673 767491067 443947793 588701137 897396730 925834595 766055609 642721679 808154507 33238288 594034501 395179264 558780844 2182515 802701212 327806997 718794174 193508364 943675017 428130609 313417474 861058863 140267425 637976255 379039809 968276475 840720780 65638275 556134681 673410365 503384841 599271293 303317044 134181003 546789679 228347871