1000 999999961
549018906 869006669 190718820 938710732 802744619 411091939 293967345 606238861 308131527 881032353 967910705 154766176 254556801 956606269 163482857 315550933 793669525 924665714 926838032 980113728 693064664 163578056 835957130 897336634 318653037 833215662 197656962 275306624 852687775 426197871 757941084 689532900 37240830 549545996 680134942 28067366 180214707 532156833 495136384 848253789 369663282 597332760 476374782 67225002 381514152 494735627 986525529 549755636 597820785 320434986 468509138 495349110 973229721 497540807 220471748 782067811 133293593 3011475 709595871 649389261 22410961 596675220 572561950 406947847 32359905 280779368 842946497 632253581 896644818 801400799 26877547 15611267 452229874 715460535 487570804 823554644 548099915 283738103 481240056 603782726 187880841 172109420 849505816 474194963 731956389 177588810 790176389 355461402 98645335 117737259 563275541 287310020 174443366 723727158 312563348 242454201 109260437 361100743 500762289 92900884 38693568 627710439 813726784 798395562 549150529 770935715 955035464 619928350 867073190 958011829 765342080 506542461 149737255 926176295 843880440 949016847 545140549 997074365 675579589 744975267 499571393 957635429 203559256 642466695 728397055 630835350 189573762 8080929 983616319 145236835 270213369 197108784 101272052 93435789 593837220 378248633 684698663 803527626 529004058 293815565 832671083 826913992 72228397 226059175 322403118 493502389 338395266 935468373 553939192 942915607 838228758 476799317 290463780 677170567 71634089 158989906 91652815 203064007 42608292 621374292 768462080 779105758 891116907 913539303 387307036 955503248 327342373 408002914 222873994 963253388 937704513 473103305 726849527 287965634 809566074 222778836 794597585 171882135 710297043 469190960 282587129 106013831 521709438 350801693 356960357 184797603 434904048 613536991 506013 89026112 456584395 755243017 397063473 206410641 676088799 646768918 619412647 218506773 773080998 96732155 744031031 794946628 763860938 376504050 904083730 680900132 36277884 140637871 723507008 194837753 921743426 650223568 417778332 87520689 147340036 582930915 85963181 908927339 46316762 416207053 891746350 587110406 313428997 678971168 630554346 64584158 281385867 723042880 948540770 237114052 819518306 525086942 771204593 423094566 734031947 592189243 992470605 655037138 748472811 451907385 261622911 683560455 769022925 27484702 956452284 876770435 349253546 778657377 78190201 484377958 71863563 17096115 884873829 838324492 378544194 892139001 888346174 320417113 672893819 376271349 961612082 494640203 691787075 883277325 934569313 467259943 369812926 744121620 623655496 834822247 906713456 482936867 458753074 307334610 321122960 323049625 986710956 491305479 296949333 254163332 866511021 380337873 695371799 186516179 63710631 490003050 482985 704817321 283421662 289718659 99900458 661472827 517901406 613164015 588531700 34919217 561793605 985757195 932022199 506434128 678762575 844708748 148661160 727067720 632394282 558902702 462775485 946527399 816293568 592445889 845269885 933771154 191362354 865787058 936455930 234522339 314628177 941309600 476151339 19271739 474206198 163862602 890469677 375180679 218000653 450750966 804946751 641915169 564930546 652226647 504499886 538715990 937971594 756724124 967582930 950674018 807480370 99576386 152266518 895571957 744046940 705426050 221684601 130253722 777850598 22179443 129470708 153503636 539284457 96753960 116390691 29377676 876539965 106496052 413633112 308814932 540108266 514729566 333796818 763460384 627089353 117857771 918419174 79116774 530475520 211476753 383487468 163794840 375849683 986639845 724580802 814916568 377651925 496042157 640021247 19748146 201537334 642889260 945606246 964287639 894198216 447871021 945262079 17816218 751584335 971555126 568629107 248300696 329868948 835462694 784806304 678440192 979362887 131147504 368812032 43844858 57605545 972275241 162130368 91882395 597370246 961413045 946599631 922424208 559927720 743994359 710885572 143466427 153508870 483637371 33921286 294531050 482060017 645465939 723567786 184048522 112745765 848575231 447940515 351762592 22631566 586406972 431276022 736269691 307143029 530114745 728396048 232387668 424586457 991865895 346349384 833660306 989820954 457656895 809752453 805314079 891227398 122679616 236156666 580969507 134141522 898715564 958934722 712745000 967969474 941312639 534194467 390527571 199472146 123632615 77353295 703258224 9993719 333027505 964820252 114340184 988171883 73997885 333098557 878113183 195441211 580516780 28985083 374796249 191234516 218255506 696226313 234525729 6351975 881300816 75433867 58038712 905540989 137316916 591337183 534635728 89214843 114055957 265754703 944635273 486441955 685604550 788014445 139868992 304373596 470306425 59330099 297585490 18217702 279589107 462429279 997642932 380632347 618966590 22586329 699055687 789357279 34798813 157291007 136044876 907555049 924411269 509454469 546246892 754192791 313081446 471699244 701842186 449005980 814557376 110048701 619235744 450189118 163613400 371242882 919371679 374618444 163088811 983872536 274747151 324775853 38130083 621974147 43661454 115111456 284824366 315862497 617073160 158647502 656486792 732459993 626027262 759232801 372715798 540645114 863876494 375520271 745434260 791894609 883417906 908290269 50280065 334374591 62410285 820708147 813044534 562354543 791559794 870435377 917525207 118782298 870223772 623431601 381070256 293925153 451120008 270402751 726020898 678138017 458594754 705697564 820801894 739836442 829263263 191049248 849395278 374589258 530055728 264243136 39805623 309954382 737822252 29431069 410380076 843119595 535790645 287399148 26981077 732502645 458857235 58022321 181072598 490391465 480283024 204976526 552237998 222746365 822670372 274330474 158040609 995629623 587175527 618976664 818607696 301712360 720002817 956585021 208434993 707526759 381402067 340263630 85228338 285811151 216508814 448164786 494276634 263363368 837715238 932489878 215485843 137855520 483695985 226089555 148957670 730817663 921860495 411380993 810605151 554662856 148747210 160228084 786156775 843467498 502732063 941104445 665943548 638440676 128199660 596406990 572834311 457600328 543570548 258898289 323212876 397001234 794055908 670059091 838137043 985299448 147935703 79259948 200082861 136296345 450596137 413626420 241318801 272160983 303234278 408478152 183251283 598202300 342384357 374596337 435417515 463349644 463195627 243211601 270970420 52964907 474110342 761795613 590583036 952188056 218575517 384450734 890801945 986720543 348487630 181438922 576794138 864390827 940819839 441240558 214653580 398348207 777536847 234659688 219205929 124351330 24873651 181000651 774435757 33933767 688913216 932854840 998554165 780488954 194952119 122104485 440735925 972901310 958420751 992714813 114742551 142682492 207712691 540459501 575384311 709293662 146571855 951460035 537345543 252971942 255873717 224214330 658481133 469761147 759089201 394855365 22017128 650649511 669346480 109187557 317758419 392794878 521830213 939111625 658459155 216123151 701044246 785883657 560643442 942276750 70808915 375037804 553092533 19907142 91368030 965916103 839328980 441858304 195823845 713917016 133185666 261902888 691394700 58920159 219357895 342487686 372859779 701471520 770011836 56057996 99371920 543844628 949565759 777180120 550074322 168697150 607178036 357644532 859310534 861160693 917192045 522413961 702266077 185262642 682378631 347429449 174217202 743505484 650947484 633762134 666664302 40888836 443062477 35853535 793430325 821068465 905265930 697580954 384459858 354289639 203037547 856255360 384121531 211056160 602551340 622834518 880634847 614745450 56748257 840483141 727181289 835198709 218621179 847534949 202386579 181992237 287999598 984009729 278572557 918514913 929691518 789989848 359449172 363646235 542218165 426061640 18781586 1130495 616635394 104883822 538555329 151031767 541126561 44713794 400827111 309389678 394052263 461707485 570738181 230632664 674504162 942961591 168822040 157086051 297937788 990883368 497269894 811664382 522875786 312634827 134615127 460433365 768569967 256257138 838960636 932740465 849820497 418294307 145444569 467863236 749775923 447604225 371948350 295854270 346716375 339694101 583867928 191495276 940931558 330944212 392347130 349851128 747389857 437711482 59412671 174339881 897664328 690880760 579217669 250123884 423420477 239423183 963862648 743571729 465796405 120345307 337581833 171408331 834987135 381855284 691949025 1470328 626808819 885903989 995500380 868749740 179378531 399804991 628452676 55466188 269807775 184249026 920234824 40019301 242517874 834862699 321243142 842941210 492839774 668787272 406790939 5760006 917300682 986046355 173086091 834529190 441256889 219249013 639907902 243073120 88134730 67945941 172911799 968279021 324545493 965825826 878890353 448143353 502114139 881293646 467926973 94572150 837696341 643481631 53405134 278167006 958038142 874827070 859180963 549188709 673546508 3353841 206370985 913196696 605087224 458094120 412434451 838610895 277460878 445293704 442716494 808525025 702579227 273804286 899822373 456188929 139314023 490378813 70541023 704848741 367077062 534432295 463009960 515290588 764578037 124932032 798605239 836574362 381841667 925985800 778927029 582204892 595283947 815661048 126294670 436781567 674422368 178470589 987819510 81102493 640824789 481309875 943154632 839935202 401951934 979066514 545433441 307829549 131877509 78808560 646931122 405188224 30848214 349369666 257109202 770726545 278760627 133364652 557124779 189170347 240969340 479217488 913831869 356985423 838425418 364963727 136149778 259747775 776560567 657526601 524788033 412518218 53979855 575625510 213631211 340748659 630166330 805804388 64120103 71719118 570898097 699858307 666093761 854723475 767551317 358652740 211626018