90 947973525 777774540 488559164 201356496 562958498 313651194 962223550 479526001 118154400 180494265 182269352 215121928 710204786 357320206 560788233 299476948 415271864 642907416 112155031 733893026 583960084 788033118 441445379 416637447 671066233 118102531 300421701 937435819 402510059 343144746 308016419 35396496 200931994 407029420 508013928 915010459 829138760 243477930 34432295 948340970 485379053 633470629 752101437 926825610 634054305 744505235 993025618 557208012 57238764 113948857 161742249 265094291 319679753 597636576 6227204 306689767 519466206 953856455 640634682 382281645 418736389 490366155 417340287 438583173 877278812 173218327 611901910 831300341 263502311 876143641 319645911 267162128 200824630 800662043 264642999 846879622 670162210 320758222 637763924 892923501 261646675 898774774 539731865 708872554 860631518 750025376 268379427 455808536 24896197 539956128 276086276 200383038 940723050 906213989 20512450 524608705 121552658 645663650 173724244 992513872 706308583 976624348 978686486 897576027 588309139 246722820 88497945 672467197 457996655 553901236 783070469 275070958 179088764 417117372 295840360 805489819 667574498 730128428 317834685 85684787 728857905 136723234 795147425 99348 830781977 58322125 551267253 784255434 378794918 734704126 618463078 195016443 186270958 22158339 204565187 792479107 818704375 297751722 817277794 445429891 406862629 142855505 467406145 114692390 429753110 470214230 452383788 259835179 227791275 534732622 218288491 448193374 832779160 67885811 667082071 652141272 975778757 937934515 160224863 705619507 923445427 790886264 765577463 228815429 527574742 700963089 653251760 990790661 837626731 287937934 527627637 115231653 647382391 714576765 976770074 798070642 720296277 382984397 78474293 762075267 716804476 169749069 973875930 465610320 390729433 595420079 43428166 97254135 727325594 578956124 309146005 242481641 917925564 944008926 182538790 670226329 376668655 131787009 23677019 707936604 438702466 809733194 190003728 110664346 597092317 5960026 746186526 87401947 279839885 311000362 133731203 311099848 119743565 736661100 254736706 449864599 828421417 8683914 433069262 460887106 192964241 719363659 283637217 62612898 349924528 534738464 203956716 355745095 539528287 286390289 569476892 125319059 779580834 296488681 695514523 312939823 245804206 782247571 157506291 229954764 903879714 361737549 825634938 839561882 7439828 896838695 23427074 291253013 488827324 94814366 838339964 994262502 925339295 127921528 193960612 526371696 809346041 914866332 416007903 574975212 651971554 76383652 315542203 852599046 125971886 437435086 707545317 244565010 308069305 631961299 29723207 183378541 966793033 972235446 428795155 189413061 99307713 939557317 812426594 533841048 848604314 746209465 301350085 547236341 682764912 864676504 120236692 115484043 387080875 669241950 221516968 985904556 245583383 467865444 964785753 465223719 34675721 32072086 550732470 669902886 636403459 965988474 333848569 168820497 243013781 2947085 796396920 284651627 171014315 459564574 650539739 192559185 999794187 774122727 837801883 247689936 423717609 152924349 681701180 873154571 588469134 260637509 652109608 950838332 311435389 277632498 504986854 105826055 76448663 542694011 231986868 475919721 399739332 359677786 156725874 429217514 159487782 762552184 178274741 822417160 551519683 110540929 452419749 366268440 622061352 653919735 980987534 16279063 606980976 580608230 225265636 207998183 265407023 495616785 197432789 773770175 776831245 716528953 496799790 600838865 113597024 87505224 873717544 149796028 395697320 401345415 609610155 958446159 974617136 652074497 583601786 793583140 508080797 990861944 907833787 69872715 895472407 475017965 455837594 708624599 682564238 802018430 677807298 528682336 296454067 367990101 163285025 302970054 568793811 880486545 36075535 519459646 822894300 167736755 760626995 795979012 708832487 297245006 928154835 314878464 957990347 27001882 467216360 309431526 674817348 741899003 974575391 837170491 853452433 932564695 654137347 739687770 439491624 969331470 742546628 133610441 58488125 28043937 23181304 740140663 753617268 493460391 129523772 280093506 811885666 452773419 394466780 321634874 951519486 671059095 63984435 302806612 502886421 53809658 269806281 773774540 101086231 5700361 541142995 124089898 6285610 438843801 210220650 577210590 451804878 585861527 346168610 702988732 863170826 254337318 285900414 434603609 322133456 826151997 910745914 206812403 171465224 390987566 624579990 366084453 395874019 758933739 65139686 343865980 796913999 897553256 998108602 983576592 422456034 212206096 598299186 353996211 837106259 174759918 785738787 237746681 505052370 606775089 284189851 584576360 251858931 331690225 869254683 556265048 76750541 301025507 590324459 645012597 489132629 696747359 491716415 436870588 804880877 906387201 152042391 115174202 988522465 289554218 314581521 285127458 826019412 174535658 166676323 773570090 759400458 250168632 675648357 193690540 795070896 629969244 999142676 489454214 683374900 863038005 515775253 208413803 698665376 577662398 758433088 653015011 460423048 265989425 228869595 174869470 218081078 518135197 21875880 612670446 758495031 570903172 349556539 572675937 758591526 497356307 130229646 205774320 672216772 679407998 43026311 505971208 593757531 838811524 25780023 803322135 697364482 538981581 791972122 382103678 412393502 519619802 356112112 922477293 232115793 524940126 853880595 536445847 467444943 519362368 756193269 973009728 619855558 896730614 145787962 406608384 170142079 477472939 262238981 308844022 858168919 45066300 323940003 955000172 888940064 193325678 629769390 621937139 708312015 873698415 280480359 288664700 48192724 840260640 453891825 359611002 640611001 733764242 335229985 115240543 952724323 342120813 638796881 565388881 993663985 505289268 801291785 913739243 510280817 715635735 164324946 447805528 649933963 191160515 151225326 677295570 405704898 223976743 493584510 441898162 494674851 786580193 247823167 911227395 22997024 202930778 553285828 662084995 451748717 360080110 63815600 832232158 517603437 359888127 115000323 862046356 991824747 353244523 740059910 490964453 363835154 486299 839729801 970052018 102183433 890103342 877780750 190365262 658873533 577766843 81609353 918859224 437446136 998237775 596758802 368448099 623732881 741477046 737006654 333049817 659113628 836584520 643688498 615565052 820446101 665796568 20558979 613734291 959713172 565449543 430261272 705483548 284396536 87301106 489617510 151001426 940296712 614995325 918903986 259832368 817719089 504323054 223257974 684080048 285971669 391427669 829018414 864066425 652210485 144144271 245938994 971770226 869121427 837166922 904134428 953716779 634915186 10113372 984630689 197321775 551534501 864785148 858143783 866112401 303222164 790208434 952067493 532783078 362146433 784577477 99549599 516743297 155134177 610879384 633452011 822104127 757184720 741542431 54726026 380375163 469512578 167298109 784207061 88417625 526984188 115396070 418870493 333630511 176942746 842679773 113639429 95452277 333046475 325564888 284948900 874732036 367728008 564773855 76182775 54576421 226019204 626887038 515316682 396835580 991613085 689759955 415763007 839799401 413092047 719001840 284122079 290527172 557720971 176858883 859869886 718758662 669385687 861924742 998683684 161698448 945276416 939863048 843358686 625986709 41752505 203601277 754768629 191730814 615883581 622286481 745814647 164097967 977454204 799272623 220474746 686823061 361380929 335492257 552589227 433071956 336086726 234162219 864624719 14286903 542537460 804937175 5253243 397002686 911002632 643936647 522191752 276590355 686034719 746163481 508721273 60488880 614110619 707560791 980994910 803730477 441796341 3835503 697968385 199360403 859429236 922302904 104508273 4380873 581339974 102623897 458572413 36970635 992174711 934636090 936973497 297929067 186203795 183156765 97604922 533834394 453638338 844270454 19151718 958880651 496963364 168620041 738442580 68077626 883266732 741926930 963238159 142016008 916878012 251543416 913944833 485026452 334872977 251911722 386586583 571889983 814214083 369747167 467146280 769638875 150561397 147232138 454268627 41491050 369919703 638847708 85322265 493861534 350413047 518092485 959220617 317079436 926474121 800351531 969138022 240790124 571682767 862074301 105895060 203176438 226988348 698029940 186365366 713648580 188653587 540309597 888342883 931401499 204017702 912287055 378965484 163319301 93066913 372946734 36507989 260235070 947850745 570125395 762415187 840574997 434893845 356282725 168816722 516892958 980403890 49272958 434163270 24194373 544553909 367602547 75423797 752606133 279543357 214682155 262333934 369331060 139023972 145794346 894184397 73327358 193819162 639740242 30802588 715177875 985859802 90944189 939573568 939082904 722946466 182383056 841440961 509017616 156239867 459909134 79977498 141711476 864217506 724489238 358484700 667088639 322776272 957157571 688695095 111435531 757040600 626433538 613685739 891849572 95287871 824481207 365272619 885510972 13157737 19095445 97459440 68293241 728370401 813844204 272604547 862994024 159620384 999627910 980455593 979620903 820354872 111649201 682146606 428942286 325595407 371387133 167783058 281161248 816102859 820435537 926539393 631870083 863694054 986652863 252621973 704682411 89184666 651310408 504197751 891816046 773121539 152483305 981643084 813791760 915871830 208188689 31997990 218321058 22070484 437154782 631724012 403650055 127802176 679796686 607379401 3564161 9403611 829787697 741701452 218667377 387151985 312624839 757880702 814616076 692721211 764701199 477639934 440950106 508632714 502157085 90205053 227899587 648360187 159127928