930
466554095 989038160 881137583 536720855 587994333 64938809 2923509 424239175 290415491 909466202 813618708 76611311 81048254 367892163 276474893 742787718 25558009 785356147 479246629 934604771 116716755 491485941 324136258 674946996 7134250 154635538 84312654 713783376 718605838 860824372 568350592 804873542 306946222 77333544 500350654 544947555 162708477 438545731 210196306 384241911 254805524 68118672 616069949 387170035 618894093 48381794 188633382 341486727 696991175 955167493 472177984 421766582 434287727 906984206 17814795 699578404 273529003 851030653 292271391 492964791 49719589 363574722 796773991 290694700 925365078 766162594 587505202 375043168 61285034 405129978 318880123 547468576 649307458 557297688 752918985 792619970 966237627 7650871 235578982 321548726 791557891 969757327 375530208 554460981 936022225 672737250 791322509 534851937 32807714 505846186 739693048 861230950 901297649 861901551 668129923 762376461 443369077 802055621 339739353 754784805 665006828 448281855 343814980 921934725 930887737 110215369 928703680 254444271 467167357 291128151 468384490 812333041 220534172 943245371 399691862 673499325 173234487 714792113 906803073 681817697 625024827 655355383 969030314 958744228 850744341 812167139 22958214 858176074 495922087 648776161 92403915 88576366 256546421 440998907 133572116 635824785 9722365 428432671 218726613 250005311 814357734 138672882 286588174 9528111 704864709 390420119 881475205 872952444 196208724 832277150 386409363 39081939 576888182 561094881 467081417 882422037 924484981 758302243 750639008 20337935 860434489 997426685 170805147 781425336 224615950 667744214 305225105 832634586 550387708 797453910 741108596 478358639 618263783 881925662 801829154 558371423 924592808 165437141 186545861 254581716 353318318 82378708 172496155 801581223 166117193 332815236 111382179 838059153 216944240 450403555 166420814 786369119 426232196 349943359 668981878 520307341 941250048 89550269 432830766 395062711 748099438 919244792 43847631 943732751 145732393 214246949 772558539 849459831 630812581 506517738 926102000 596778603 302385628 221442664 947864630 129823594 201765022 152748905 404780866 906349743 855933753 96356747 808543098 462212036 901429800 662946997 960357049 487247973 989729338 393582267 282273881 148632932 67925333 556235093 905934751 288543680 557415187 968315066 447617584 46885882 519230288 757512040 651929831 13954827 528346524 592744130 47563289 371586616 316883122 633411756 433481170 550544876 921252501 295910030 981620868 588734406 41003989 843644692 227671474 760440201 815870263 540738 290060672 267796197 804340602 916053659 586041187 51637620 725115043 275621321 95086564 960018529 747527213 975027248 26507277 556507713 128617088 908228639 882579670 555944111 527533223 617841435 203202567 911841245 898423506 974507822 166072348 6771803 242320149 204473956 443817113 587442509 721097598 560653136 55864762 493517254 488207334 120768221 333321652 931879741 233444827 633928985 145033370 191843887 896062545 267430305 555325521 78036105 916489585 772340361 501240559 840957287 138208556 26199534 495637787 764370133 362443227 13059370 589460158 604620717 31810189 166830102 495908560 159547259 264890916 219680877 341829455 322693008 686315304 702515371 322487108 240681755 137960772 196282324 861868669 572723954 587273349 553888741 688018472 521691312 727007966 892475818 575784886 887497048 863275419 397405550 545704401 354396792 878398135 642644684 755671831 410586094 845023039 881163763 622757246 456266298 736896714 783129176 676460260 465273048 325846431 436230285 110077803 824047936 256682177 193097592 744795748 41275075 376951671 991418040 734756636 298592365 271520483 616324724 115224943 860055236 381993706 67972388 958118596 852516378 509999675 37468683 970137065 552475119 959730776 659014647 188542240 259684798 333833356 18616965 915905169 604965470 995353880 987640866 416720298 321720895 744152474 331615453 499787701 916904607 221280331 341601017 322008606 224227846 93154506 548185953 668151323 404465722 326664828 455487491 863234791 516228770 706688223 575821898 717095657 590130236 91906802 146229185 986539217 76778945 87792551 258108734 686173546 852154249 191394432 594084878 417495535 628355343 714740682 306036687 255513370 803963047 405376084 181403150 857823719 625177535 910169786 81653654 115232546 307624429 675978601 716487957 447279246 505624416 825680670 419070423 198327373 184158785 987740758 487531989 630230834 52635852 134968759 115456166 506845997 836386821 790039118 348111022 732021608 465826690 590709371 855431809 351242211 7335400 351416628 873790726 964319877 713084640 364059114 978667173 940091033 217057596 157881312 25738514 126385209 912213917 111350406 966901558 738376457 571520729 844853833 462929027 935770947 35825949 100601588 535058283 910820962 237123538 523730012 758543219 341570875 153787876 149545743 670429566 990792234 610904586 942833402 437003370 799911501 456074884 814012797 497238063 58617190 494023585 500319496 879023043 375996965 496781788 977741029 135788576 433724890 607509240 940676568 984060845 990171115 371418463 445988864 431119426 692460356 577054801 508224258 785689891 707763480 997002494 849207504 170123473 665590218 308314526 821690836 699696103 759259651 303581010 297471616 933233966 694195750 394404982 672885939 800683489 721284245 860819171 98389703 441436996 235544617 697527777 630086134 654635359 741138974 538092856 290999442 248411894 418754472 11003344 534926972 586028992 634251065 779581434 815337631 707930749 108693257 740037969 159759023 617543324 699048964 379782568 278467370 384164131 971717295 50421155 814639582 209292556 800945682 631257469 739647718 134646227 953502825 636379420 660169728 547784163 807563507 295786324 19239107 573125776 336827978 303313689 616482371 418806552 759564398 207749412 276953645 924920817 335740143 949985459 351542617 759711039 153312089 24358103 562051901 56112318 649749888 319738594 28871654 719330363 523528182 595086598 841166201 352278453 195911040 586167873 352385752 941709763 598720099 926704022 137377848 919624679 511402281 852056990 196140113 929849434 251988971 30830656 475830298 444023320 381386108 506341109 348234661 104952044 495366924 589823730 908892407 253063831 341299651 827299776 748947564 813023759 799900211 741485503 72896493 521034153 124687051 353157216 230490030 341202325 669018050 862006172 254018286 696830741 622309720 274550601 637913019 389945639 123023213 331651266 548617136 933044060 460910233 700470330 101902120 754071249 641490126 516334923 788478410 319896931 398346560 270622859 210149160 525034982 238698900 497574329 698892240 535474401 381088226 264538984 921693898 61374326 956958486 434469207 795516670 860331967 589853426 35010130 611157850 448838796 871898825 127016092 137050747 499250992 807784119 653339817 991264185 435256711 700751849 405796849 859971830 627055144 874452198 867041225 884942409 699129250 855078090 922457529 712593414 535498925 592733232 850702601 388489200 423940155 282484985 182700599 422873301 768775429 925441628 486709931 907831876 377811610 867561605 589136896 348355992 969073793 60820806 381131620 90663356 571628574 633468485 469917118 195595683 444564475 215462182 202813827 318761129 373692970 960440382 726743982 23100706 162652063 589196330 118103671 322386794 124718710 802625137 262257193 439073613 75508491 564773267 697699850 509284270 344640746 62617566 272406705 475901632 402442710 129700026 602041115 149415453 127661318 536644330 959399711 946008051 659243420 120979993 514459766 873754587 379040973 474632381 19710224 752133182 258865581 51632222 24611836 127349761 88821783 859241844 418981439 901673665 312826814 650908220 137882124 62421461 218609859 674935786 782159429 102656270 662800695 6146735 944494191 980081980 91452843 76431231 542571949 904330420 948342211 83156812 81679294 592527807 202425911 866032024 724470206 701305759 234111181 364880439 517076504 433284768 335815196 937016336 403871302 711900258 295718074 796617019 952059587 789451446 453594598 601972488 669662455 646629547 558191293 698430563 284666649 87871016 832346071 884013648 222927514 503303410 870003772 243059038 61808506 799286046 580690765 35934433 339554292 514890053 990233259 649199016 347765916 148449477 936041111 188275612 974373075 584633309 502515556 567829055 633048363 310274848 842268790 632192178 423348561 155396579 15169563 397176366 119703214 293760576 431737008 550949459 902277310 153773598 295055797 418258779 854783768 958468791 296304040 73663778 833118639 585565431 841721529 556935497 558812771 336885393 166543308 902626369 535244381 879353140 60141974 791654645 308238700 777770756 615873072 878038833 40884636 266710900 362493094 801733560 182008682 442183155 823561147 831221660 957652834 467842340 534286177 733659858 343458666 312708690 659117305 767708178 21963776 917557825 329551969 899301504 515336916 381720242 923578845 806240929 784763383 229483208 520412699 77099278 883340965 902879034 364326049 600113703 58121221 270039605 196101420 903877835 702475117 75407512 129756259 746570983 619481571 34471426 502772768 726920382 23265883 788041074 224116732 135290033 825454136 151692066 440678314 193748792 353076504 23822874 684258380