1787
631969902 434109637 204175341 471490984 395693906 876570112 774368016 131325054 423258546 253677936 19980130 967100292 967917584 820881578 420699987 587937024 536083067 62605100 341007164 814886270 996151677 7131039 135421707 162550561 284561203 760095233 217202080 42594656 480824458 691751330 167475720 227131691 883976980 499999808 849272687 553451972 178484880 454045507 557953662 587122520 292972658 47465422 200441334 516758435 418156813 369710071 391356131 520519114 100581854 121135675 430413960 564078934 357246225 176481864 30151505 722119041 300338783 345363225 987100890 869418766 543904522 864257501 736907226 284427524 197898293 965423502 987696196 115835954 107508535 144492071 794016286 752293368 278823229 33446101 364579323 856377169 888763140 353618716 37744117 174495418 480364350 91105071 825482688 809343308 432508545 449660495 377336078 315270922 766957314 109564389 859695999 208099822 301938253 874207777 515710840 711982153 697926456 656662729 654492868 909710013 75754659 562683821 951327536 342130660 419108097 194008704 541591848 625809959 958481348 191390254 65455264 7809351 338565961 461711362 824975627 505022502 885547591 58319385 626837253 771578541 102999451 586864095 234803948 445707382 496460457 578766873 186687477 622267258 915249737 818052745 990863932 972790974 603578237 72459486 279561304 710634119 701942741 524469804 662776039 681066931 733180611 358950163 444965769 106079868 161779759 123388700 436733234 739860612 390061505 177354234 579466239 711052963 805284349 974207192 323292726 39319434 316737455 614594793 76527060 817399554 548045098 864653951 854516105 734158131 85638462 687543552 119006430 70968298 334822874 221566661 716849240 853352698 384871755 656566409 773618596 602782245 195289758 356005220 835333042 209872233 239890076 916602491 272490826 990275792 329947794 831481742 515550604 562919919 332215467 131627056 13774535 9908613 337270844 722871005 494185119 434108639 436625750 607280476 667797659 500036933 988639075 992221173 250045253 156123852 735626288 557074952 449782067 812701502 557125206 217318908 538947534 761315161 966280435 401529058 18901861 129533965 553275215 198602549 263292776 211815637 967666127 177672854 474823143 14165314 669770869 100906571 275578968 821120302 611541420 839932419 873270513 472794029 667158618 771997333 939349120 631642224 935934815 618995473 530675271 243658375 826647652 711497074 498712935 599114450 206452106 146766488 870595802 568172719 537247913 490676626 193948647 235861205 835765053 311379196 330041397 429758945 293867559 589087184 320398582 809243859 612738872 348974205 423653660 996659468 845405706 825157682 881573081 350014523 734164157 53134600 131260971 889239411 943629985 208218650 844643356 489483666 10937847 329618525 386017255 688752499 416670122 734175966 570266382 944799581 665706838 372362586 835457149 943670032 335343916 531337520 901608206 484973352 710717749 86809239 561868301 824912883 789956223 145784814 10001366 40104337 453993326 515637924 182693790 561701273 954432051 554261980 480506313 304573425 932434663 214929148 178400146 945515060 598963710 917851246 389121569 38577479 463359580 415408866 167896300 379255290 124302196 239496232 777938105 655695243 378626890 140045348 937462475 866052262 684504319 882329452 979418338 382744776 170275013 417715229 945532174 591556234 407720380 587236535 353566338 808178655 582805859 222639097 438914654 854300108 99120823 988425169 759933461 509631559 849952106 331538851 499835206 771038494 447630822 301358531 177866307 477989838 370956549 369775861 883748854 484622382 776961198 650135032 127483612 261533476 546319671 608294358 514600979 839438476 504030605 667994095 654694493 35483068 477113802 5199661 422491415 964492862 630505187 841010477 480974368 995106174 36682920 110764056 193961840 942346496 46582365 277784431 923721276 240078600 10620827 313168810 494893937 740999097 335225892 105569530 886197207 979584131 650582802 198231044 406427136 981323223 745594135 868347525 496909101 508726137 574410984 980965944 719881901 927797676 795056194 10260728 809114762 790371144 626558119 529268977 477502568 108387346 930598774 394419946 106650919 904056624 710482830 68168055 881500352 655765515 12337518 868194050 526822529 561821213 352364526 948767240 11557788 671840036 246393339 506808856 909394665 693489170 715068879 367855419 252965161 266352856 313352547 219364998 401386892 879275646 131410360 565077404 428012545 103858813 213976854 82717302 915090322 986126894 349258778 111165539 461952953 262315582 522607049 226661820 382275555 817507480 733831547 844102982 780802131 860763701 943388124 797892092 697594852 380327592 960188019 658596458 591422628 735439736 740767178 862433251 386500695 136252815 711454160 592928113 741642123 877512832 584498103 88576615 215478973 615159363 425495603 884067963 876961005 402381993 45738685 484997053 347739997 812504760 436210236 712424693 567123092 812026886 834595041 443893444 733980889 856117970 776878906 597614548 103235732 623353020 358703786 223720308 175643184 647737870 334599181 681357826 26955863 612146806 870173966 346418909 855073400 662666208 693777731 63135698 916165861 643988388 507284843 910303364 71356406 944707219 561742369 616085794 437652099 38883388 77417354 780295487 828013037 835592300 923540475 447324295 919076989 462553709 49383895 667667874 207911719 948654530 715781616 772675564 134940880 401774224 637455221 429168916 218477002 126965771 949928610 877566989 101573083 453264159 511219193 617364705 289222694 656057625 69166076 830144843 187491080 845035621 5997929 557556244 390905335 293086654 436961092 429044898 279926291 211722004 456636185 931709349 525472683 824238648 318561066 402894570 751919176 704267245 241480468 339572886 737968116 213493039 458823145 106726314 58126984 728359539 414195786 676491086 670815746 159125290 515474724 433478988 136779201 55831932 953593781 357001236 572707796 303487144 873109045 546098628 450805 928707882 919431117 73756015 269574093 651813928 315540733 720276148 380932557 225132415 743463633 302004327 661224396 562136569 696663589 585015506 682976154 319501947 202184432 305598513 49844307 720401207 652817393 873962555 103396975 686377190 785288996 38984889 175168460 134779477 714657898 535850182 467943506 96316674 90485893 237659593 271190869 85115246 753727816 56646831 604251306 914886916 904393174 760964699 253067872 785863521 614061725 110861800 385932808 606511204 433038647 530398802 108544712 319255774 199230090 162524256 737110597 375514619 296417916 670345606 468840359 649340114 488728835 795642725 364061341 607215143 994050907 230527431 493774287 408358615 449741320 962544919 295005877 997899644 390130964 262216138 648849625 417414195 798193205 718059208 205359604 917860708 112386353 830631790 787818790 918859669 131769393 652296744 885517118 292132827 399817321 467434278 353280733 444275982 254204584 959322118 652082023 405943971 809302924 488417202 270799931 130114947 161637230 543703602 210847204 989380121 471962503 666092849 927242893 300345233 309354322 90085624 78888539 311777365 417487304 82279659 609861765 549251759 308045100 559218520 88735340 118376147 232675534 741690011 945932215 320349787 378592878 934373401 67293823 902965085 751814252 200624699 208673114 955754065 340100706 479689781 418375799 817697599 162886174 433689839 638379108 16590866 540560902 629980045 659170075 619314585 958281235 472143383 151155434 435444330 732145831 440368423 400180071 68834972 633019287 963581292 297165649 230658431 931931109 351076847 859514855 866923557 373874095 962713932 201448690 229118285 291208911 719203806 266723667 900357741 489246368 740423565 118726197 974432586 948062030 25922684 605086714 822071904 228822838 125123679 302860457 853960878 198509865 977135950 837275686 775237858 905182224 985459667 957867741 821776567 919972998 100826453 103252586 843525269 959314939 818046251 11620332 979649415 566656943 670566521 915816057 126168926 586089340 214111491 260288640 651445856 816810533 971177711 836525521 977258185 858863939 343435137 416052067 285728595 158668390 85301253 690854323 96890785 13007207 410259995 978346163 852047813 282686297 380853155 52789064 971749620 349674946 734286519 678766222 278844323 683590650 239322250 352772366 594659438 130469961 643082092 502165690 870657610 51798384 895107139 872364997 402634357 836126219 375531508 617226395 114594701 421513023 444739471 886489134 500969324 178286954 184615123 374073941 199900393 20392149 363340951 311195717 233011767 309415194 132764599 967630098 121272307 82664850 216308015 349190396 9729431 766358559 743862462 168905563 659501052 232262849 512790138 341573896 108869770 869387779 704445028 263907279 203906496 252426571 718454097 15106340 733638113 252245586 801248661 652961012 843582598 839518559 927340751 315217370 395126803 844497584 8827971 214116587 925345328 113717166 312611833 604952741 442616100 265711350 778073399 196408671 374884496 189887542 136841283 884621442 376909550 73919587 818116201 385840157 58974266 374404528 615105370 898329768 108731741 715854621 768261752 444139422 798829117 913114229 381057715 429062396 596622700 98439093 467611228 346085786 491069803 763065983 16613887 866600156 668212466 602162226 487274303 904038529 405328550 264856486 401101354 798470843 686316381 220692772 121100930 943696473 427858564 10150544 820468363 581434902 430438991 792010040 130423933 266641145 365349928 651202039 694651871 949068056 645204483 477725131 302919040 284721775 796612182 556302157 463620463 72863423 904037617 169898433 456555058 16820222 837809225 91400763 875375476 762967551 6482358 955497801 699099519 780288331 37457728 805824483 986245386 360124681 785040563 563097189 142534836 366495910 455535610 840970986 356228549 402419188 324271377 752732548 575535674 588245548 77496623 461587876 287176804 544012114 798180590 855501512 604289240 934021828 785914189 931799754 581342657 18504717 219264684 569302918 518112925 392012946 368632231 404062012 379227322 801260081 642670810 889382174 372541292 759306817 427958131 218584025 706003918 188438069 839747998 859987349 423588654 37337632 73427932 251742628 864528476 945683510 861123086 673427688 623774882 526519498 902840045 307520277 398892881 790919455 379548165 849692011 950155647 166155114 241149764 510946614 886270153 995150897 527055233 125888584 654406480 317142140 927847165 999621746 957921963 917785563 139808747 754135412 767989611 276819987 929000192 456573742 349441249 966371081 387420545 134822978 409951470 894191491 125758565 867448415 646566054 589490552 454076715 43812742 572915095 661744008 423554107 887700344 154021283 997142747 650791902 835702268 230630514 741918643 358621268 77197055 220397727 633177209 745699590 96035097 131325990 917846834 311983587 376324285 484093270 913521482 726867457 776169943 8684633 79673312 508022928 624601665 562393057 568775495 956106437 434859594 657018365 142208489 927006845 962148561 357967594 926705580 357417312 855481805 191178202 748164917 673544299 455355243 80681494 464701852 161355651 278965340 557604659 69532838 314564021 797692585 74954056 820539640 739397088 625095032 679785 709979834 670719515 852576275 942656206 846539649 491103177 875864361 695074333 347846607 993283839 505161044 391811685 782861417 834340033 297095332 83864713 540622890 214860198 765523961 524495237 473837882 380559241 753494297 437699201 271126840 652820394 498488312 529060745 526677605 182766940 995805862 203883995 873179964 275951141 211633239 699566481 743140620 326282367 261449361 229680521 91471626 909155570 316919843 464879125 859958222 35979661 210051703 987504260 382048364 870066418 559106430 894567665 836147091 677809974 815681500 196594061 282868202 679590654 239085519 448704451 910182636 885980851 248350070 255455142 259427856 820390682 696872184 257496223 936249581 570324463 358241933 968547483 632458678 633184899 314125959 436342903 699226078 843526796 519771992 894634375 833433764 110184687 438893011 912282171 18897793 142056692 294179719 986542799 447172728 766791731 565262941 12762892 585664853 191739741 47720897 27916174 140810432 571323625 129944645 623498574 631184860 320667504 632661497 640518728 28941837 717054145 183629358 233084125 309665170 694236808 762922174 236179591 202477759 367019929 117475776 86014699 151647289 613128462 831812968 902704109 117378087 567391929 538124850 451484049 698359235 200648255 344296033 507261368 448009667 687741398 935882934 884020332 415096294 927396100 726777665 715812239 741014750 276674291 128254361 698836711 153402403 251429680 166858593 35897076 657834547 357068860 435811237 993926188 59413000 448317132 376163314 498564769 178461656 521803546 399013306 720841495 36270674 527363630 255151578 647265838 732182274 250261352 441381320 618845908 597699140 524507154 383588785 519069474 291895437 611936561 554952532 526169974 580979250 203850548 228339677 140444641 180303807 300263712 794615417 84178689 526826709 530302740 226735574 973219172 880546973 105385867 712856401 155931903 623620116 159194923 592501174 193181491 154217167 979605517 977758590 722448308 188819519 938863869 389764719 806882386 522876882 974810185 324737718 519546099 724043426 499564432 765082364 642738953 134399773 360603139 227424366 842566147 428081633 62171720 881666126 941339732 734402339 701116753 708023393 859686749 505889055 665344278 318178357 259080471 182316012 94399284 612580465 29612262 77784549 608885544 760602785 938006824 475959789 40187002 7030012 578180255 934752082 421103534 314137353 575877465 706957026 905004814 565854558 228932576 531236146 264989513 956631983 89140434 215180807 507422171 373258187 338365388 885365501 827667894 116835313 80709740 159831698 54299970 896341949 568964392 928155588 901645078 604888294 172678185 522288911 396149108 717992417 92528571 257782766 515230215 415124901 20690501 328286254 990323406 868968638 220120736 366349060 697657967 488463675 484142946 944987083 535388375 709609099 347540084 348526658 179782882 6698730 978231441 568533966 554279965 588280397 905057188 844958582 815502 945835362 522030423 55202785 117788194 86511711 176871341 912106390 403475056 84567976 607897972 649499995 86728784 81498208 312243299 540777106 541623964 295848253 624764181 647863982 445279307 630723685 134745467 928995265 782641075 871357926 200574449 206608072 291664594 492535351 45674992 584174941 599819461 354845679 356227093 78648405 856537483 463518285 783457562 567944320 863647880 435522809 627035410 245871471 488207136 146932892 917713070 636811199 308554703 588404379 472674080 32018595 579629946 193669046 933294355 102148358 943369540 112214595 640318366 530826629 498187990 670454982 660480797 769672779 929660352 817197108 101430293 169529030 9358904 540300395 427927497 235283077 389620605 913805076 921851498 898178992 91326232 638088395 279673033 425600629 319499159 722976816 567850708 472766096 929826415 259091259 392425069 422012908 71059608 390108280 741761956 481838194 407712312 847798100 876361120 448377762 524795208 381591604 785386861 929403737 809571082 128060562 554735130 665655929 573510576 824428443 242792090 826055395 587289109 931429674 714425345 22892216 102735630 273158547 812442333 1005096 969086912 869828698 186651837 276318698 881170559 676194033 376301028 987509515 727607034 835412891 532318727 23898989 121801601 955369360 655502110 596039817 313019611 484574018 13302948 766330991 676335689 205783364 461141286 940470614 470394788 224166397 390237663 949070835 577732605 257238411 575128045 790127695 849268043 48970744 961285001 453654791 165724515 343269618 726530193 637056932 137863882 182793606 670160316 963686522 118603234 558366105 796294033 938315923 101468459 862792848 771234491 426755586 728671596 533992913 3890837 903694435 757612025 794190608 539420681 384623690 225880582 507749377 238923582 931537110 487674326 591994019 331031780 983514674 708637088 479950832 543979207 244586944 275983350 808854989 237197425 122959853 592536851 307188127 852386257 334415637 983109654 424891110 356237568 472439079 884190067 921759649 258396806 302846629 719285351 687192305 113966684 915543050 770773095 591323066 533953610 70075655 212547141 89390791 974485825 16757496 621238564 198779284 89893802 722023852 923624300 48008447 573200540 10230739 228013813 611694192 485555092 194300734 713001715 947660351 79998631 495327682 567947840 318385684 523357300 397122653 151753655 812305948 564908624 604774885 881871708 938746862 223479907 636867348 861181039 488904147 561133730 987003426 298453533 913747395 688915018 181758829 411141907 31352277 528575594 138092217 22664019 375851460 130397203 124278468 356069117 740044829 796465865 92016117 399394701 762574453 610300915 591539768 526606098 452929435 888276880 54712576 633939494 918287509 487312560 67446185 321121125 94070473 923691317 810378869 150688367 510507355 452400468 526649474 362142028 969947993 919153325 935523001 583735705 38911873 820059255 126973258 951743311 119891563 827966121 22673780 452559116 874155997 800688221 212328915 11262158 586851077 577513374 909852835 279471441 160326915 524861641 714544263 922163575 739808870 83129072 605280871 998212781 411922215 25456796 448837862 320075272 495090116 670023757 719671771 152892041 463295091 59558658 501888533 974796432 731177109 420359104 180484962 673781207 499793769 319800255 621197203 217485987 59851152 703604090 440817056 91134396 183177593 276653467 804942485 373845471 760021853 760548454 25867455 502735039 80742801 297314928 218623469 306967786 370042290 342316234 53819264 880443994 322172053 300065271 622295419 639507906 868941091 785764520 533605547 966434275 842922168 608679623 317774648 676951746 131346007 956888979 486608584 815224991 132197880 860879519 386802659