993
755492080 669420697 679520734 146548506 705223105 26866762 526072478 169627363 258039305 813189970 402114616 86642373 392545098 754417597 699844 264750335 667060745 861023997 503068346 320153389 174237960 250655568 557091604 466074826 371365538 342691391 347805236 414538265 217594715 270775028 916843110 734372014 674033697 653641323 811482569 338099981 353212522 458512667 692977770 536630428 152361426 56529824 479143252 993839000 991732041 611966879 286304216 250601350 737996638 805799388 965348467 563991569 390573384 351836326 457869699 337335120 127435057 648434290 852999656 81559900 303923365 763254660 489230523 846139392 773178416 12007529 537718380 942478455 508401759 403818282 292147066 907269217 979263690 687606278 865369331 704952598 934756892 992617712 787995524 58742699 827133086 607566764 423311971 211881488 211867808 483323070 91909493 956456462 902573912 952971613 547222327 873798035 801782259 805875944 526626641 789402979 328310312 33224711 635848817 522339024 161101863 290486427 987742290 108232538 879001865 348541213 663860158 697519482 440535392 798147617 333652930 372669089 898991540 844945617 59983202 460460462 768084611 876884247 568426046 70455291 43124474 758761826 878277827 628325474 260942964 17586195 59039451 473184668 909038622 839518521 59146765 368552440 338845122 57345833 363918075 146283461 587922407 873846898 302021924 437309011 330753575 631648754 207708707 650071915 635738491 392664237 240657284 272113218 502656817 127239254 868113519 392824065 754784988 2324484 874048164 454118875 431129320 608074182 622988239 909383907 970893566 90851470 510480427 718191068 119890472 927438142 895078642 707228524 813404120 431597623 57142136 72489444 812760012 27304390 904393551 356916630 460746943 630245665 498593753 241892868 486985390 170029392 966621944 562311189 712551776 820998988 244802653 467544320 914617437 538215128 832795660 167855133 374798334 846300003 261568718 295464318 15512148 925523985 799232598 41345490 953303511 727672856 557176398 77704289 832610997 245603282 138084742 596047124 810133083 175172047 124727471 354481658 389670231 924927411 830614075 164513679 165488189 729975035 756632450 148921347 967797262 384410308 16030936 363020981 121526995 231177827 813125105 634687837 674461605 933559391 551273204 364722998 154009881 467648458 202383698 801256089 199039730 17062918 862122243 277865033 977379250 637941864 352325254 515971600 749007284 349103299 894822292 57126812 330927307 941040785 320208525 586747298 16301516 570785450 765381601 262693111 104339184 729048061 773866776 154702856 481789290 603945815 937171979 811596214 726580368 663073318 316092164 921155815 191862667 552105444 918059120 480684132 137687458 305957729 786274492 523565323 676896828 378509060 134105021 750931401 204810261 174309709 33718489 850442267 465145191 844072173 683020598 51245710 269587541 698091177 318593125 423817754 44003625 366741744 403928387 700161392 1929414 230147654 426563330 480551555 969620999 587420916 568281079 310996170 421979301 880527678 188290642 277793190 222836756 789674475 327806171 837215593 723433022 530797552 971247646 38299678 140903672 84949794 195205215 268693652 982200477 95030006 653259760 446768977 482740268 263022551 820635285 577049099 949558300 897878549 200367393 883420446 691950058 164318590 46872468 181209107 920367287 5580416 365887155 128473598 449708934 426303037 799230748 632248757 440391454 114629576 51504909 506918481 592335970 526130755 24823843 805939519 297925754 767009970 639685457 625304297 361957295 957255794 380436004 894274556 865610698 882092267 715967210 434974238 419571885 410431492 524615553 436094497 646129523 524957952 477877624 504749750 45536660 348280324 654587541 625055953 194979141 579893366 898383438 670800111 415999138 70261241 757675365 165541607 465216450 148857643 162243183 134761947 50521829 269730988 999094771 316110230 538695229 892067954 327141559 850888152 48889802 251336957 296947200 504073382 405066574 418962329 30162032 454741122 907598247 434225252 469581344 851825084 15409893 817201959 481991761 615568599 599356194 800682728 524156170 184715994 527091587 522682817 994649862 395585968 545449502 632296514 349187569 653300764 691116786 61217219 550826722 737027979 472182192 678834542 160749582 242811525 321760752 175075061 501488716 316510112 704408782 303315283 537410605 289061955 985263244 179416211 216677942 206690905 245357775 187006779 375423109 906280659 845615127 944066437 674353747 97504128 616398000 603421383 213550501 109089201 757868934 169448229 432998293 731245288 581795332 79086675 699650826 819037959 56350537 297405829 274609361 406530183 637256567 752849431 128873472 354775170 435225994 92491580 334575877 873892742 848302042 752391242 275497321 77657573 561773292 536752899 52513988 207548069 223991151 228438421 194884615 864179675 477274672 677877032 192285013 507054761 954439059 676053518 502733824 627911056 323171235 832473071 41207009 103026022 36347142 216014234 788759375 724386550 699098018 681678837 821679072 507910943 870441746 311910197 978217112 150220514 534607178 194247216 993156551 676267457 719255676 566404037 942241959 102860681 135533124 525665229 381806128 224338388 705775418 990056610 622126332 207246109 66870393 538471206 945575892 592204168 283386658 800031292 154670245 757831002 325634230 391187028 212001839 122594259 638079311 271965974 418247199 103915167 618559720 577861120 82345643 498837291 678600792 626409893 947238064 12891827 186192072 305048404 354240399 663155529 884575835 851854876 596987551 682613003 212796395 898657332 957964562 16595243 187913946 922531886 68604517 458321366 441672763 536313091 384041877 680936802 127846872 231913216 935433955 441709120 171349062 267829511 879099125 538175141 129590110 580453448 378727314 841597640 662142689 708879395 376423919 254898705 930828408 481317099 667381821 32006431 949406199 807845489 129216691 694995140 904623078 82207205 300391269 92529036 909316452 191152444 196356258 360037025 682076506 848511638 839340656 633067126 300929931 291813331 627362556 979312651 754270435 263763028 308113642 99246224 822273475 324497950 966081937 897691922 867908441 811839911 732682634 926503830 278598289 690955565 773003456 913617510 236405860 31093270 747827262 374888001 20904252 808908805 382554751 151326671 299169047 653894600 616997584 652646302 259924159 770932691 741332147 594504196 618852874 267233018 65556934 548442888 597790591 9090020 979480970 289243161 652707262 137800020 821765740 413913042 709741483 656460545 938902778 97912991 598819313 820439974 632059445 208488505 530124940 788789341 963367868 3815953 826287257 822683053 277592619 471641704 773522431 35311747 837553343 100382594 305133696 193612003 44026374 15245749 911566941 902354793 620551355 198805933 360866620 517781615 617083671 862804533 65253057 777890283 64777676 984428189 741531057 138363124 480295004 992665150 157963552 371910926 880431083 619163168 178055218 351505083 696694688 376038444 54157118 133170723 15095098 536168032 858679884 811746078 198840759 163952388 518471652 548342447 773598279 555151008 195558690 612154616 321366420 707896231 566465004 816864857 877663387 695977811 952692470 351999782 287832561 794611602 126773012 554458611 553415929 597003025 959698564 983125818 988529432 76944925 65562835 249724187 847336462 244981379 422875009 569143737 489563813 320691076 318054292 827954118 101233781 313626751 50158110 595597482 19410070 494743424 86293224 725277029 339638872 111890097 412333268 697546220 723984746 490420008 486874521 828607515 445754048 392423905 5302171 732159470 268665095 315615678 84754422 720036432 683192685 536757528 503440540 700642023 740333451 227868335 589865015 533628187 162120979 75356209 45051634 810133850 927794358 451440543 592534985 584455156 413353433 111588155 386603278 792411079 585409157 618295471 544696694 130124674 571317986 367506890 879271055 942594413 714211566 759621472 596981533 800836823 739025880 951198442 533965783 746123657 379770578 130571196 995529082 862344714 10098220 504841471 426471687 849405311 42259008 48913719 112635191 600075583 185608388 837085948 803264212 694497687 128493114 534307309 590307027 857017179 94152322 546004600 420344993 867573343 257821621 327365942 632736554 89773236 865182945 486215437 190538176 861046597 375864328 662553096 211390073 478533565 504376081 922986846 553337851 608991106 503142969 881491765 198351669 499685702 505571979 895255748 262308870 764941606 133007370 879369297 75604869 148208964 727623516 29186284 743559624 785994929 542325791 128640456 165812950 585207835 575427786 166002705 9997920 246573723 45195699 611664645 499075129 203547424 919978077 657891606 363899970 628126952 349710427 740230296 166155178 618425822 892412048 863470497 775711174 413627973 845629243 724065005 493067018 10550767 948401342 565099613 393522823 284062 623213944 143012898 483144245 147513153 15700057 751267286 524816544 310160081 396549240 882262242 877672289 550633995 704263688 556371684 691865914 101731873 306300955 767408112 838624776 543580592 321150967 358705099 303371179 822667591 48939281 214068626 510292773 679269698 528073531 968701845 226123108 68491821 341264866 722405881 411029806 749478912 743277114 569057326 963624747 266009165 34617438 523931814 507028453 530018575 436707883 346089187 233832833 282591170 723834470 6357326 229250015 175686251 589252135 151019960 539620371 43795836 693936114 856320941 183262976 403310712 766586261 490619198 248040728 593488247 79127462 279378524 556836792 629454047 20828460 5243335 348212025 970293747 115753925 197280076 974372061 189574223 565989206 764436547 313123964 924113439 172475021 52982991 603814394 225168391 624713967 437157653 66880993 784996849 435180283 539733683 706767056 228676148 955654259 661460117 894328571 335117544 33222428 764029967 981980993