816
729250910 243403102 943101770 9113241 120433678 239900746 506187318 358738149 947377749 444422465 423990414 2761631 620863379 939474134 255241769 753823598 305480175 841601396 58243676 449423512 175848938 316550236 589623334 334482241 303234689 854091283 9042319 505245637 541647798 433964485 827433932 659220358 557600592 789281545 792945130 583422448 787679291 393346763 77256718 288192606 355388307 93562582 646675909 840717722 521782654 51908407 84154772 885256716 196769412 595487005 235681590 69324855 713950124 834119244 375674194 941916858 30764523 789693810 549379166 151730728 187580130 890850645 408735829 899286285 455790661 291421048 79801997 224827728 698688577 681927960 492933537 691407269 357130379 167158673 61740115 808708018 575628373 402186358 650312282 558579246 807218278 686825587 438292297 249573501 763835372 31143828 252672817 715867519 583978208 239077451 355609633 146326872 191098087 575325776 426485662 147015597 793314496 312749082 402228866 388411849 584549505 988272938 968517115 301532103 697491472 203376916 86038629 608217141 885326366 282403593 800999951 910422940 559745787 438677369 366400699 161622583 402309863 720581624 774036701 641063762 712634418 359251516 34178850 548478515 769850795 406462225 550411686 108723689 602729693 910515268 589034073 663461383 762689424 461361702 967179757 184534438 593758795 528376765 30483302 956662146 944090720 737773301 251039744 197666298 886306630 785938546 584358389 130479403 923102991 278125740 737049081 192292349 687820745 347255029 876877095 209820975 603866581 678277453 403855028 818948229 316286519 699010590 544803206 158349118 752500203 152752569 189924183 924566632 701994343 990368581 488547177 170530223 985180327 246482549 349792658 906351120 917335393 950641255 978040479 818686694 798861200 388619815 932046572 188702608 255222207 874126476 623337190 963190252 620204063 705099246 397168762 504445023 754344983 439973792 652807901 985322067 973734103 819969225 158920875 178328015 264843227 292268378 497193873 376020633 919627238 60576806 304417197 744516940 698877 12336397 826913184 203625227 146058312 183996491 773343567 529840129 214750045 430356952 843225597 423442386 716877117 419913326 81763068 950199262 855240489 363235460 453792808 222307296 90531737 346664141 662443362 905573207 118547133 144244692 273499984 935371779 61162493 87903085 681849188 644332945 801972923 641566719 264684097 424306127 933227005 774337334 509085216 12239321 7128390 999804082 905683118 819494633 105561391 448634927 95730162 525832349 668798588 453319235 888866765 558627685 658329018 982073109 30699464 98351272 640373652 431376019 36156075 984398261 21291709 394943319 287006158 117838367 292410976 394392351 989015593 770597446 916358102 388018442 281781502 37833556 793623283 380212261 375509074 431578770 154095654 123041180 693928804 71732214 3001049 694201099 995721263 722152934 37971707 590572484 381508164 981117287 503615947 302253410 10496412 300950799 879666098 74518255 258960352 904189972 223812294 406741072 829990433 824618385 387924419 64446125 303424467 226438290 61060105 464334008 615153917 7931401 371242930 646901595 645241125 643931672 486512656 245837755 427972908 879736750 937243145 227625740 863503530 611194036 616285135 840837075 202947613 252457215 52197666 17403534 187572327 27174501 215644399 636717394 28518588 228700679 839097876 84131110 188461643 270955215 810582512 647091161 426444349 261677606 449663449 783154828 831650325 740607309 463595373 361330927 573076429 364082850 290279143 971903585 833552571 987386859 614688822 770654671 948838183 627683903 565496461 978906432 322977294 183978682 757758406 7420127 853497578 517583635 627952793 737963081 438830118 42594314 184492043 58489452 303072153 48458298 932206279 120115684 960166909 127844339 645354148 63290829 175853159 650115073 265016306 291756524 796758756 53395498 134975291 488393432 456671195 171388788 489117548 406647215 853537710 571980938 76494402 624454195 268030030 471227633 81511422 520053314 70158865 120590708 308030492 428020181 667264781 876227952 339100359 67269684 306988848 881446345 261510041 485322970 987231035 402532555 244960381 908652194 776128018 723887406 623670347 545462293 50746372 641818176 984993727 453601621 104246554 86069716 865342591 193511590 250627104 75627022 672299755 854732469 151423756 372058883 621808631 304154356 612319937 366873143 799626596 8848064 678726758 452642148 309099610 877077933 743203896 456694660 212705498 175130177 291483692 158580195 289811148 358431140 944032030 511730049 465387697 961929682 582318141 419178873 214479287 542467328 107105522 546630938 770941669 937324972 123867186 327317169 349716312 914396442 426166214 628097473 129341999 370803706 178009451 937979503 499649273 95728985 358407572 156234551 903156477 524478901 183610557 796200385 960835894 888780538 551269747 691228848 36394733 994941360 120039704 109254826 265877930 710488694 257279159 67785200 299284060 454708039 991715069 852727074 689753399 179336004 114194053 543223221 112766907 495229945 3885022 684463965 93085213 924335359 410244936 479432309 157816077 15677259 358183546 562495018 731104344 604078052 879318813 701863722 535900962 737150771 612713949 873110235 865586979 794819249 59607491 71970734 982621298 448719297 559029013 479022871 357629601 735983798 848025104 753736889 186529070 797392365 422108104 426991153 605891523 977869248 550123756 999525334 867651474 704128501 951258853 757439444 233426175 826628232 898030844 835723434 187006160 633829733 571484112 869495424 668344035 634781240 563206476 458999449 347592953 434863944 520098587 5594194 987887630 308557280 452752421 558178048 3143093 486178572 991479024 298795973 963661188 863210394 191325389 382580123 60322865 312172599 214898780 84299982 184541252 216071475 417457967 305603431 819240606 757051889 276559191 683725580 853706537 346610176 845885208 631869246 852877802 988500244 409152153 173626939 281699143 895370813 399985879 496651112 910100946 983397516 610762355 45452828 786844032 563961398 388759977 150098815 646857047 411974167 79030394 338201128 115053525 58883773 104410761 709113975 516149834 482065909 239643937 487825925 178984446 880350974 492007967 118646733 703859177 100230118 121574451 214229061 333607849 883550497 464657993 601680222 594717096 786729413 227695383 29838749 622042059 667164482 414975727 730120894 559472884 516046621 839498845 135387274 72507792 716130578 790413126 548637801 298885281 327475962 937009817 738778480 274868431 574957605 505163433 504510631 403369420 73086697 880999352 585442530 908710525 956775273 798409322 216996137 944864114 363372723 839447804 275899253 780639873 597029669 192259630 737428347 35996035 327753784 269795977 412645352 813615983 938330806 17467421 314106913 874865001 237141354 216900886 373895521 665083968 627261045 810858488 547501408 662826103 388008165 924249241 721991286 230229795 721373886 524465706 715617577 440522752 182030300 416397811 370059062 77485045 101074550 691045599 276757342 155310108 18965914 122000803 93958519 955306433 103288176 293385338 644395160 702585329 810728427 795281578 250894360 22975982 567617630 164465986 541864176 554529719 591369657 966798873 266912517 45240082 88039692 985544329 29168081 906383522 487250120 649109557 556398781 919320421 331873701 848082249 396223761 68281450 529066025 209885265 130470534 807254339 28441876 91319315 368857999 180181157 221122410 913545886 51589726 912805743 370216064 135813615 440048299 512758965 775778305 42376663 376151770 162460908 279264290 66201950 716519517 913316897 351172405 642453550 150540343 980217210 133837975 758203207 434870906 115108108 236956853 276538671 299387788 164273874 229477278 240935977 149150302 563637096 97560030 11424074 76863889 439544302 567667385 975114415 528156346 744658141 760394397 6925676 638699821 304851776 358746636 334749527 676782030 835239472 99421620 133614122 683193564 118071538 350179503 269194737 28356519 17803917 948164424 158398158 114942923 520248496 705131185 233617162 383538218 146331284 253267139 180057481 15658727