649 10
418654026 376440291 340139256 899357277 928630063 648477461 971740932 598170541 684776678 894200257 171383094 862524530 750224362 232504343 390923448 416863553 380456045 317324880 879590883 599297809 216622850 107967848 456748355 844079282 224291179 549882118 179294714 799312164 211646064 796088703 887538897 450407775 989866422 940265616 821702235 819493310 418610968 259734198 920367659 506067216 253584901 360527376 528282082 859397030 23402397 628590028 381073835 715034677 248275463 261206699 887622921 229776049 305955826 255417131 883103954 27935970 851331345 213966587 516639018 768027943 348543087 289007958 421053835 803513902 705072864 126757686 757328966 3899185 742307540 320386281 644133895 532368657 566980286 664610727 994155381 446936068 342663239 632723851 167134242 635853309 498114409 990181830 592713836 968808534 665765562 582074448 179003522 456366654 713571885 716843883 524185166 705857814 355012954 403711012 135837655 422200642 328291813 694569243 793700327 14929475 719111577 519791495 799957420 541938700 992281015 397249614 130188862 398214220 741268890 703011781 331437810 888785132 122891630 44163977 334600771 260326821 415041883 52348450 695563657 520819110 361270403 709580368 822969065 676709126 840981495 900976562 706742980 730574311 920512065 605708669 684425186 365874720 655298048 816025651 79520874 778982785 237470211 820905727 562143753 909729689 908059608 915887434 19409277 315162414 976078734 179986229 795784414 416115123 424300087 146004781 553068261 584572402 266299711 996545423 884736112 5411924 384485216 982388623 357053660 273562787 13206662 422054839 917756038 569228511 912865792 775969534 452088218 425027702 472848210 719152509 183024758 315803809 990348464 608104740 64804729 994145965 142541527 910229624 197517109 441311005 459333496 305144390 862476741 380454963 463637404 39923717 470700981 269698605 241255967 330884361 618820810 705767560 400147569 311808352 444950058 531273917 175616507 713353670 750667158 359909191 116056177 799337687 1332985 610442165 501939327 511503652 209773933 312088857 323856919 350787785 364640504 997410020 680297263 139614312 467720336 114457867 167224129 8012307 731931189 491578266 960102755 559962413 549727685 773978878 236329101 314959286 965138580 878229283 23129794 631161613 979542931 70434177 360627181 817522892 198340407 440853637 535097834 633478453 499687233 856027870 428091501 346006306 427294394 843491067 112423294 581811506 768112296 94578238 517512879 360624701 285279394 961667875 512632946 685755264 199136523 582606570 980947127 23423327 76341275 257594119 198587185 325908291 211956116 557618695 263397248 366432500 565325190 458176936 600155317 217407751 535480567 276822712 251126303 929215013 17627920 414186036 231720206 886277192 788389938 394861607 669332857 308561452 257311196 440965394 753975984 632663532 348456388 363524559 471707332 591251808 180401405 686523526 495189004 117402524 982842821 369002832 36039194 140956023 597590381 632391277 66098728 534875158 838397119 225741222 954463719 733863732 635792174 45037752 990530549 338374440 298193544 43981031 319546593 93676955 205083409 437533689 70701704 824195143 200260239 17295295 790985736 411526675 976313306 234184456 788361001 87787989 286869260 255012525 126726598 464274664 60932715 154539064 689413112 135787439 9401876 439094491 640101186 101890820 851368909 352911305 440639049 555782000 506999100 591746317 771347497 14311628 318582304 606586158 465886137 679465037 741485544 886878742 759963396 534759301 21316363 193434258 997344472 325508490 610114629 325305328 896023443 390339906 845935363 196747686 199322225 947995012 659914951 668640013 137694892 492465491 706133616 488921960 479292853 56121468 268316118 237807541 624385758 762113211 271929894 187202134 724947430 509192353 205454700 600400846 578572451 828736501 844098781 276933410 733311656 735833593 742660007 297364449 582005923 665023541 51795383 440768724 209196675 493853507 776974176 901413389 119301490 389187160 617209176 30428928 529134806 217187446 105172540 799127972 76891734 92734700 908955052 677940956 278427712 760696261 497481355 962866422 556228309 588313514 84139626 957608368 293197559 870705584 137194990 492990684 776342958 18790790 665055695 771683086 989077856 14579034 897047843 111444499 354941398 46855500 218622050 9054597 175811492 181986726 701574800 14447457 618620792 323660442 299523418 611579640 606633043 581451397 42786929 723932060 294884810 567146409 640281893 564572067 815435938 204521374 410064680 410063629 614484488 767128782 818949431 914553896 776515918 952309699 820869964 293679780 786334508 372151682 974996591 770133577 839743251 561965070 766509530 96458109 22400090 516606625 25105762 539846675 191042082 385380714 82705690 357581303 78984464 884865240 798850895 293393989 397971756 154938248 836496527 887186642 504191796 678700854 420097311 790012012 324714021 79554382 190884524 826831372 793152381 513434893 591175217 480101193 391767788 216186828 82813994 415037244 499327334 929091226 814236847 160670502 879001569 453352207 999700681 138954910 549763502 159294259 642035794 624524824 172208068 65942673 525628775 306606754 396979413 192514835 658132 838675732 816410544 589625675 399190660 64450407 760072245 64390377 238975460 897863762 691998774 722530114 728383168 276368245 181812277 29304760 751778857 407403552 67192010 612106407 990085466 88935274 296674544 230400087 28706175 267981507 687102578 990797450 915998586 245258273 523259111 821486138 231923968 921344913 215488001 213037504 368473795 799716443 374515034 829383376 732372938 608629986 584195411 309354964 382699544 584055688 817233024 150695309 784699303 35175469 542647687 474863978 684252441 381449112 736131389 381970843 810065783 173082487 448591435 369431833 7063320 756517768 102585000 895225927 415426881 950844915 3413563 158089932 499292591 80601465 433193594 381968590 711249093 484658964 70506563 61524492 807522246 748935720 408353365 109956140 456130965 274740430 73081301 312539227 178098733 270162894 282354816 422579748 688686378 429193128 695009235 900046190 911083142 989048109 730724190 541302902 926970401 735341997 794512755 937126422 60730491 374087298 776752462 721257971 570298525 139235524 758375813 213926735 691362940 460339779 303744427 444720775 552349169 965963338 732323994 118556524 561077130 977849192 581666487 347436426 688820135 297868087 333951210 766620754 650604228 295269862 6180354