5000
628040445 516324775 651645818 306770716 739937415 721822602 833826079 483342864 583950391 224091616 539944766 439555902 254459059 891683131 31517414 267846738 592410373 701354037 686367217 291051231 411421594 920282524 829800869 661871550 242807112 569316494 753844918 841093571 812784753 424504574 200774426 517452141 749747665 452872026 643308996 139858231 642365401 240143585 642023636 784930393 947045801 544731634 984119326 565455587 94623350 517714152 965416830 818110433 87268575 118617623 331466366 438690268 85166645 466057331 259684390 489788706 643617603 893812038 526178579 600364596 59688283 610786903 99607155 734375270 604786637 807741081 574707316 62265052 679992538 801873049 375509361 661782491 601683316 674276877 463551540 827450257 747898833 898674788 205175104 907407924 32637247 603952551 567421687 544916768 346654526 237002868 558636014 147097020 587817040 105611287 355294446 82152473 257504332 651594441 245713669 492748027 381929506 340655379 351914335 167630643 786339967 672639561 242116540 779698314 649722537 104175041 831913061 961325528 907320705 241816706 993388333 721911228 274217013 345481411 119495561 591339781 225668198 716276692 422444447 223744795 692167243 163336141 288161893 886404996 990241263 239498246 368599719 730500382 909151390 806682269 279552498 582830828 622367435 866810356 219626151 217041705 773991937 9968234 182918722 15625725 239696203 875035199 755120970 432939647 826710175 798811544 595682515 103183305 998251579 521265635 848825662 40488475 905245602 252121293 291403801 142857415 956607135 605042347 743726337 752436194 493823320 905059999 168403528 681990173 528975503 286943186 66161197 201470489 889702620 517878129 896133108 407057844 694446505 198616148 148426577 857936996 767244375 542501430 416869578 449317303 619563185 327894403 469957232 157522768 787606583 298641082 974131282 488375502 736483741 324718924 710329748 783778571 694277473 89089929 868830519 783199714 170269999 299157826 610959816 591070404 456869844 959547004 614294376 141716922 441494123 821765799 38652798 10417231 428498718 448410080 343166837 114820926 738073664 5256768 90770930 969420806 651700502 76249888 68925268 783674612 250558670 689982891 113059877 434969273 496016078 919606334 321543053 278465115 31906105 207505712 26930286 452938167 938187276 167189760 877113085 2132169 116519435 968022371 885877981 373831761 342253381 474753525 739517725 314598070 147023688 6651804 120445415 456823513 797431704 96377320 655032530 749289795 673411046 876726823 201522128 396367020 394241442 989112820 564255799 76931456 118300627 273995973 251299166 47095322 81712549 506311867 199691102 882242195 601640151 569890161 972873335 182340244 123449509 174822666 889039696 461768240 713812153 888936156 314921974 977140057 840505641 142990647 71618519 240687107 700451084 994588356 69587841 134130665 121310317 989788455 190413679 65177419 302488099 148832037 832332630 156203259 258038082 413381471 516347140 397628357 417287423 492028938 4933090 432592542 283656682 802875550 314337552 911443327 795209689 129588247 890445658 329501444 340482746 264714013 883086408 226244227 406846627 541442885 461781947 949868604 321984005 324577003 517869347 136331822 632075874 56842643 542558324 231421255 720398377 500127554 860380275 807642230 818465165 780905905 479474388 698961275 720896895 876489847 804290349 391044590 41624145 697627877 353358341 375266511 935295678 568896269 801243566 579131648 614149051 410486466 249600830 962452353 474922875 976150224 255766360 160970511 430316479 433252933 865100837 264282547 523729569 373713136 132913529 640540107 434796200 191597942 681118254 207926676 927107627 431801169 328557384 297180756 125523702 387333084 163020986 887659667 82995280 625442762 571157531 336260502 979088399 733332658 293013454 873321847 236723296 956905494 868656376 833162785 141453414 915763363 55006199 660009901 861305448 866567651 622039748 555554977 477902125 604230618 991058497 921402870 859849524 398204223 865416848 169484907 530893967 627546840 842737655 154488415 624654604 771795722 541937016 56069244 817948102 727040841 394125313 624215649 822744059 820428543 737183096 157123137 560346069 721569732 721574275 744850414 435354110 575790077 649474178 605937941 274925250 907555422 562436593 855294200 196490252 105461264 924774898 14535246 325938605 920655027 60519894 313059599 825267929 157933562 998546043 325609504 844840417 676669227 593970118 856101345 978376057 874112574 977006189 424187478 821406185 539732809 33641131 38950686 375030806 618608036 917305633 676348866 170060992 353560402 260213423 880691604 89880133 918974459 907874458 678421265 835477203 241326637 24617661 841886920 301453956 460336012 96875241 603790093 265790967 389942104 593433849 982449696 154903910 534211121 932343580 689050669 142351953 813778961 512904755 900252702 389785793 747690374 643514473 951746623 488926595 626682740 65378879 837499845 880424254 974815073 650632413 241653993 326141944 120018573 608477386 976312108 628899786 119223072 617464967 226359622 965326557 516035404 901397051 16323102 757021195 690794520 40313373 451350072 153789632 614341604 79290097 817238757 448145872 863256087 854406695 945338458 593966889 176077852 741077414 88900619 165839323 401110774 400620642 877570416 463614360 632507538 548639600 281910431 970790741 423344962 496057496 145661359 504136928 613098312 359335438 744696205 435770256 51114336 895685455 509257825 25290467 317320548 356325088 528960859 322365173 219953029 808885524 28877502 857089436 983906787 611344836 519369172 531643075 502112567 960826490 396648849 666548877 272664555 932134337 148714429 590880116 951086143 66970511 769862937 367142561 25995340 62918294 734401845 188103700 582881973 773383286 260228246 82831477 755144603 528353317 432766175 415531021 75355775 516239006 623393510 343669003 93334346 658973111 119192484 242940390 661050383 691772060 838239642 192437078 913767729 107294960 734469917 755927460 336432697 410377879 515846573 187560288 510641110 437489025 230936548 712419356 228523978 628743313 327874672 291998232 260952616 675539936 98981885 812555512 103352034 73843003 388054329 131500416 811687544 662676532 791501799 859027698 11393096 356678294 470650328 278179766 352998996 886143779 370655963 425397099 512382335 971202467 579769919 944721656 390372558 593084421 633236697 828939493 249970759 472359574 500285638 208302017 948093286 358860266 540433251 961446609 839171436 82999025 445999853 159635895 81882986 519968087 730748422 869698712 514094008 337768247 561083890 251854290 177986325 328780156 343867014 245053520 475360454 808872356 727551425 899504203 18343757 164440741 791976975 548392047 104383623 470850997 919116241 763857316 530435156 157568053 135503866 607929348 211377137 524740099 238277241 940643275 371566296 645470860 558768994 608075291 529332548 516260394 700840471 248581068 829194835 914519831 931153887 630858025 63799285 657522692 171656463 534865464 930358520 666932470 916260930 860504097 827058929 781534514 885465949 885179307 807363886 852293731 767091141 253096409 309481974 124284109 640491850 839437935 71694153 296832825 572007739 347543134 930376162 879127979 735036558 565682502 648581203 23320179 349351489 151160033 614113768 494556093 725989666 7562340 132843832 16699894 578189877 319800759 534572857 437197024 24460571 640380764 278121627 754467050 272252832 40349458 329208663 412061142 807109164 198712953 391964105 404470345 358735423 276881524 662184624 869703358 456494857 54025078 444837462 623387379 25697360 807682692 539175994 413622417 888422782 248477768 680195862 574616223 49443648 436644307 444643379 113444124 163685999 787240646 874272513 255686933 548855507 481926330 442382413 226459661 174808543 21356620 374946044 87834456 102492865 922624227 174770705 120879045 317434710 347406045 936473719 306016759 446991046 73669300 49648839 508429886 187053757 210366728 153367409 574709396 727697077 920187413 520910300 786258111 627092298 719701488 31440195 788211975 121065636 724643902 325363424 902460499 756308411 413502852 79480637 498436770 566287179 511336946 627607153 979054264 599982723 681516661 886768686 612019581 491676936 655039506 818030201 168882116 615333948 711511963 17700966 155049424 968456727 54885326 329810841 858877427 301988536 8961380 397562430 782311082 757876516 206284475 478676912 890054239 1361433 489133502 391073267 938114145 508433731 189590042 629839078 930529836 424889387 282479090 900796035 665499946 331354806 276732225 223298376 437791830 138256553 154452016 798787152 253310706 402077128 267297472 500580117 1776110 522209625 360617990 308202459 31505632 741613409 957023748 78602631 623421316 44575544 816382991 476408900 828021603 122845685 2408558 161471805 496083328 123433808 857860460 622657422 125035671 773920506 723676155 324531968 991318176 327028183 837841191 840877295 608460613 195275879 178511522 255949879 679160267 12843684 558701491 258613535 264647959 519742921 711130222 598340499 612364994 162581351 375980051 837495151 785458138 49025280 233455647 876676188 375517034 371658726 892782517 311818417 82721076 835257398 37602917 325488871 358677666 552402294 822829835 269902768 880521 420690659 586397863 356822875 784329065 984861107 746216281 454458470 232127242 637071966 188928579 759182038 364175970 192567304 51498484 314511980 648505729 155685095 179059288 976931182 521812842 581071291 729563316 694520306 307151525 39074128 925147678 256657891 887290840 898390081 47785693 695419252 24238553 437224949 209300677 178362537 268440075 538000078 331559104 403567658 85944635 491456871 239278225 51259971 108891187 613052763 421308587 518208069 308914455 539368913 677419449 693980252 898127727 824413117 37460799 228674010 542513112 748667966 887210198 74095590 30077481 135389611 695450944 459420744 866085997 309698264 49201843 477284226 617873707 173163192 833839939 917585436 58674280 306844545 944271014 401229769 996601069 417004694 969264990 375894162 110016108 433991075 456063269 574948777 105771471 297771312 486406038 883034100 678098603 600621546 454957947 49219082 681203174 735781595 753885737 850931028 559053688 680453780 839056450 110458290 350818715 69120742 627823534 828281976 253266329 652368216 921443195 359925740 890038423 278178443 8828148 841182070 247685083 584587413 82334201 249569209 783925200 68073700 75890084 957290843 546673927 242423994 123115704 5534307 530224978 846854358 287212873 482586070 175899450 181349165 93341388 807835135 892644527 496154800 366002556 819563115 190904330 806910218 964528190 183994257 979175157 146420169 667679050 536332437 679444441 523086050 647894709 217599862 362461214 60839396 221470381 823545614 457698512 764274241 493738766 206031035 935407523 644441037 321170432 2169546 801686068 968016751 854481233 293244421 371910752 956549852 844059103 518040539 704283964 246354250 3236376 518938930 15148822 513794961 812790263 590833445 746642700 126130814 153903906 78611752 574996998 814511697 655762606 369362948 130665186 782853611 445993418 210605048 571153939 114492826 928940342 91072682 972132692 554098405 887048535 570848343 495518652 238112031 247446489 152534526 617279034 421172044 51287568 663620161 633808241 890085085 784169835 975644041 403331918 725122676 257494577 67008812 637149131 626838428 280171150 871889580 875017311 358377612 821599399 495566939 778049068 800581822 196481772 510983838 840901587 355463439 463255182 689898607 19586886 731557590 466526408 529452992 443822610 166584817 460647329 489164086 803767579 874969111 699212192 871241369 267198976 731102497 857031166 212392231 838443120 932356211 781706568 329891845 571385244 586977161 518104477 595352654 270386280 275197282 836471898 303058479 4916289 233301790 905634699 594989713 482804131 936967875 535974374 167774607 49833110 754864710 163657678 786191826 766065558 952269810 489386708 477040914 437880209 339312117 224450762 12069621 395475818 402214715 384794647 889960702 745795865 724934578 49376572 591687802 762284202 474804097 733719121 698431260 545542487 832262745 246987915 60279952 769102589 378622868 601043921 413632726 878596908 821212024 35504387 191659210 939076950 953880437 912376062 661785477 281761728 276122765 631913549 202509816 723680526 640975262 804088451 393558544 473944465 255760562 808895522 924325813 153491981 114539069 921548078 840921759 534115896 752678174 272691533 112478747 277057994 185678346 322262222 590304604 291573780 260771009 439557161 970069692 943440390 685675488 740303883 114556664 714083810 638107404 265309838 619814620 345694306 241740301 681415891 736111398 191367932 301484443 614076593 717946855 518913061 957630060 517945314 754759826 294233251 163131817 131462163 915516703 156338669 339636424 695895827 439238688 738508166 6290106 57296592 153782084 144277016 543930395 476952648 780330068 649821302 924416307 301410664 362067429 41337876 717971880 360363163 920377206 844353573 57693811 482788900 914885655 881886441 300976094 600606216 676058130 152158459 867970565 280383343 181840450 295490572 449440014 527907050 878737406 938644661 321974284 626828163 607588650 382582617 171238190 737409165 5666967 751500819 913823757 165665094 529858113 735371248 853168945 470612143 63143471 19357585 763955596 486528415 262032260 118511633 41201377 485694328 885261959 159579937 634653137 223321198 384850215 293074308 737891955 600530743 366087599 767600198 834957791 650733783 315184854 127560001 464530976 502181627 96982989 418018136 900934373 521006320 290057667 322268442 400115294 673937893 411919382 308051099 237927972 354909052 885927800 83512600 944092593 976921997 600177000 983712318 391386739 456801477 202827751 903666764 311414308 807416649 392031130 638573801 845996704 12474451 863169797 285770035 875143233 839662116 901436228 99260608 895709229 234858975 232225947 391718800 427970730 819451263 61069659 413824552 34927843 28772179 279367023 593592087 634138198 137537665 865870610 783534174 289435187 118490317 281512239 371515335 712434783 754493266 894488732 590059801 345713737 727956802 538308265 822101693 264822354 121590251 414555200 842976804 805429502 241632085 76213709 609669025 829738611 69386202 337290815 756436018 180049075 835949746 157745063 414011033 667233974 95531197 616245395 936065777 948475072 325796422 517202529 912970806 619279181 239548427 601530946 873058330 779017162 422852795 695499510 992820919 122072213 959795082 222882718 814946001 532801829 370934876 325719840 731029115 94618728 95154075 216558281 917556984 191463846 436086423 297099257 395055838 666415071 171494529 956992971 525340250 489845365 671247906 242896894 516881331 967898963 681664287 686698167 218975654 438505867 903570844 768511705 896004970 678504062 280536804 208323944 742290417 524138116 918113797 709819655 459297545 962304002 754684715 673540930 308531424 421429449 213363883 173346014 919947796 519274446 301799678 316091927 202842889 645220945 458699078 282250539 533725796 740215687 849765924 554024477 537430537 287210347 171086767 33260155 203112499 912763187 900446293 537728393 388741633 178154762 883610798 730015658 957094746 455043021 518680067 57173011 23582896 714227953 806286397 698198539 380196312 187676745 502286121 406833044 259605396 588394132 625808700 252964967 193518706 491828936 128826357 156906575 271307725 763710123 647045611 727868543 960455048 451545023 783221774 648483904 397806347 629159284 45348399 408549953 458647834 439311436 795009133 499771429 395939949 86436809 279355690 904763025 976052641 397184226 4987400 699802237 623623859 67968730 852872317 408531815 998609383 592671646 592689311 994525689 738251993 286543380 110758551 343498654 92847159 185310244 435560681 696838420 883686918 164021344 43512382 989403228 138083811 565092760 625293160 845669110 24611730 861046632 515956571 494246700 113139753 180694788 918663831 459096269 815242617 929959487 516013487 481922882 183665102 674766406 310003902 909796461 797450702 881494763 130006916 654022073 284488792 616429355 574294915 257053835 375695459 110248316 721357903 937751754 955245461 112026472 613395768 969464598 203604277 538400780 543462816 329781370 360538704 596540006 382587676 86661316 454379908 127657909 659248501 386413476 194282907 827182579 537372812 611695873 723395230 682342979 623416853 596279869 856062201 895826710 466179531 858897288 937908683 851517260 51018884 525615553 368751163 731101243 16405511 444568175 797536694 780221431 918279279 269983029 549215198 110414991 434152011 94837859 245751635 115422381 715637096 710956337 945361737 746446785 834871290 292615866 225928457 570481352 279903899 91704384 726739642 226012523 112628571 372293785 236431898 119762960 733260736 286074708 672224513 789486875 618689962 413879057 428387325 270171472 299565827 647793242 235234584 895952717 960168697 49811968 310271817 776962156 175914453 940991692 436910290 825087558 613044605 187289597 570098901 246197488 159367548 973650177 902552692 513165721 583074262 834255647 39995181 234542453 394202946 807227228 695392964 145421225 249918554 563321179 595626398 643410600 944047108 302971329 41147071 69837107 914794758 220170765 853105874 582856005 700063124 426032690 255763835 965862758 521838052 829873858 659102181 251997217 510982566 997289378 419261090 94142776 959411704 60698892 10519589 368834905 277231636 927914362 893889462 661771910 778850372 388140214 433507865 677323591 81156212 423356228 369749644 833502581 793678717 168590827 175680498 557781272 842045555 663007103 763559010 395372832 483381359 514143815 394264687 714072658 838790225 194128805 275696118 35857631 835490116 824776766 825001570 309095564 966462615 480447806 801692082 382846254 847376740 827665764 362771227 54731665 908853987 207581882 448985453 696433956 379777321 458198661 331595402 718718857 761465473 734157452 537383644 589014426 612525294 836792595 162384710 965659371 906259812 91957080 594932381 490913663 152608106 660410322 166086252 248306053 455765665 434140603 276901457 899753975 574586566 934624093 940398317 10607877 611279830 977879858 282022351 530357671 333346992 280226765 170288519 337232453 661782647 148762603 537748757 959359088 369697876 931030822 293895057 238989661 632481797 960264416 945026704 158430440 161698398 798601679 476302389 766022748 932064879 910096266 890312333 258398550 49798569 482550368 496189061 65462246 124384381 526908680 456062912 136294592 823124701 980960659 427548806 216684461 520867309 398660992 281943014 379923824 29448065 303718252 332645086 860117829 782948555 712473421 684040077 97255427 740306168 6750454 560525930 578883488 202597985 10165937 301636904 555274592 250205910 554329768 489772978 960659459 31656632 279943132 997332664 750094289 395951285 298594356 787890694 164608321 433855081 77366438 529568956 124626768 483196863 839626 606823244 389601223 427726536 415856666 460863898 414924772 365471256 255329458 79243600 455457735 790407632 196796518 8199940 543189208 450310683 695183058 719250563 49320298 867013228 492249923 441046466 654950960 274946534 659392449 952659204 284542677 926718456 3940884 524480753 993340843 604144230 236197648 596708757 908904105 285464245 332359528 133229099 475150086 630508465 974270156 232255073 652768127 860816895 39464629 833225865 87792833 988509864 183924330 980948388 726921053 840655158 605508799 599572707 627095671 384646358 277409022 25311261 377879374 227914716 310599300 342854813 421640336 944868878 853672595 774571330 103856876 53980661 610244922 380867249 260309829 87840207 566356313 88651627 125801394 972287485 575404591 147734222 295269245 726743966 845199277 348661438 264936117 938761798 35049589 573994706 134229966 575582461 524829458 125781530 494565486 862241236 495974531 443121342 460224472 455951369 395974153 585121301 142743717 322934186 733279527 46219834 692402060 547737883 597727635 541718108 474827369 603493023 228272674 100873758 413259122 768345097 222694730 980341805 129650141 364971706 506962477 187306882 938463867 686077523 405775799 330778725 631840873 198330539 578308834 548426498 592119348 177110598 60484661 400119017 765688668 439419043 193231494 353690024 634765092 975146214 209424276 21435718 84800042 145336905 630745753 697739840 572938536 280182408 903167742 607307144 251714123 190221393 478439219 818779609 126430473 152206082 482835434 532622019 543996497 121519091 310896525 522304051 89624980 287747707 433992497 674377685 680285166 904863474 338506482 687678136 728738806 505983452 549161565 671271860 189452875 948405419 396275839 317098542 723689947 650838121 621204465 821745043 775445876 698868749 896980780 45989974 415721668 680540556 828929777 887633575 466872741 558339143 842554157 243155585 494319060 398798701 65224838 999726617 230419180 106035696 294276966 536701339 554560807 369234132 958031728 647978349 659894761 749909419 374149266 795402565 575414166 626871150 729397147 589758409 234319728 275014852 825821513 130151842 685871067 666370006 568758077 776102057 556820325 367411039 722570611 221430241 497278096 267746567 954699819 6489068 481113203 161832014 308073879 679290716 469653228 44491255 943076303 565533894 537596184 190142127 372522766 374667968 326194609 180080742 678333916 867340839 561515562 544541246 846604849 568680661 480293835 904979956 379245944 230867286 854560326 461834548 938940042 822302482 603689393 958713864 914731239 819207537 970443347 944014260 561439026 258072814 787244469 155689777 633929933 287834680 411191848 722897712 658665449 411739279 571344578 612557628 91455539 60087273 740121060 480138077 754734833 909494712 622825037 969996718 537355895 616910018 521895061 407955158 502129808 794470724 593624748 31413812 558430380 794773135 301661773 625460094 295576720 65599990 57340164 211564553 897054233 448904634 882626457 507245791 871031890 777827896 808093934 798416212 432307377 121326817 409776864 846495660 448328136 36745484 639780018 606674986 405649255 820300769 552486993 319832001 939995459 455366560 808962010 665990074 687024203 179382586 404034715 655987434 930725859 775278778 37265182 175108902 269053781 890138306 858777757 263236140 803897303 335761582 161281120 19805448 263209475 945791867 335335355 456772121 910480518 749821197 368172984 707596677 300546012 320172034 197984236 530591599 581405815 934700559 193354867 120174632 142679726 932589592 569342097 939842480 213541972 20704075 145880270 468579931 893213683 210577259 822664789 440545386 976740412 720387276 949848469 488357083 104458289 620070732 549177197 808640173 978063437 599644879 772932921 89542510 513476688 582888921 937357849 979109146 502515719 568969998 719735814 435567160 649176826 209332458 43923461 403433050 631606933 295875844 385065420 284752258 305298201 548990036 817407160 818105914 189422302 497119174 518835202 214368127 853214706 616310853 967189817 730166396 224540166 827054049 194905523 405167578 82805968 273948452 877740251 485837440 360806086 176011626 913757687 702354042 693281820 312893503 476823043 245230584 296884696 273935356 497434875 428936754 347027387 779200237 720348667 381131205 357428885 829438343 172659600 451388023 162990445 147913557 997703280 940356297 414672168 446911996 103385437 82255516 171586091 19424167 210561086 230261376 637304631 705899072 317081353 734460820 395772546 259174845 932948260 121828109 19138022 411261267 61690961 134749125 182838130 183820814 851431427 286140472 979476165 801777085 304952306 409432424 341427184 555180700 675050704 350852057 911155975 957025574 500194266 568697355 75790027 481051371 64575357 83333699 127417477 153100765 976629344 102292183 723979444 702861121 708614286 603255010 803596214 264292251 14639888 485719981 618851286 811052874 584216485 436574014 794720594 323887552 445971988 581262449 969100006 946354350 523103959 677715551 491169547 960942205 991318582 930052634 999755376 13409868 1300090 965774845 328977475 882181624 851172013 775310167 107645197 533807024 761696755 780435144 880261812 139920505 133209507 121283945 598935469 457083133 48596146 675783737 746976382 370868421 720687137 901871477 128621646 612696893 590688386 464500470 380369772 59932462 942841401 616417259 733439593 244353916 844619649 359866321 268440411 481162354 437253995 368456222 458137668 943219918 205881292 179265426 664576195 519052747 408152042 330208789 426679535 327593119 109431208 260897855 745703689 522872134 474529046 174268055 646866597 76935906 941358553 867661432 502343633 493002347 353712260 35503779 746495393 203079303 752521483 2754319 521396209 407053269 780067561 375263057 667541288 293638020 551003028 670225076 116269170 34865270 140359363 152066566 601273240 417600900 435445570 623762033 735063494 564070839 224760480 273098461 763849945 605925146 627521575 8196955 418431240 271894786 818917149 869773548 673665950 692337654 458427139 372495032 599527274 169368509 55587283 994056011 305499626 711586504 535788621 585566840 165444806 748331753 945634148 848953939 117497318 457730596 93208930 754898548 103932618 418981641 409053680 391727846 979254189 364626597 771021977 43124173 975703499 832476055 838683117 270153786 533759463 519081101 150230247 836814727 226153048 212595801 726319659 441968809 60338129 872666865 752952215 215967931 438783799 317492448 834697540 919672538 868030309 423540640 78734068 855908450 885405307 663381553 840294370 655356442 849702266 733615342 548168067 610932782 291771813 913742511 435268315 353810871 402520637 169017984 817863309 920613002 596669009 659045016 117024123 759000839 237296203 352256820 773720744 130197757 899501976 751423886 376480986 864550603 275351114 229744188 975502429 985820619 691562760 719529670 990793004 640027134 687156002 619485133 954826015 85546588 900057163 182977989 287848701 401630289 156333579 255668850 502878997 281012679 431462181 378981178 581387488 756155255 917812747 379687122 198715758 10729681 258348902 935601156 350676985 741151522 3349250 573870517 893149323 664615436 88687003 80129644 913824874 196714449 502779164 732163285 224729598 268890018 815639981 43925991 957127277 76661613 126960970 183652818 267327989 239675284 934428875 706668992 347197874 880838576 223516199 946008287 507937637 597566653 829916293 215120079 622330277 340403943 476386903 665625255 877008373 285375917 257158598 545242817 116405565 305799774 832345026 87736275 322083377 391756293 662668156 471200828 143741238 124207354 944406688 132294370 305630049 710597698 387365568 351100924 417466184 370386861 951588025 509598595 158616387 143720264 274838633 741267305 546180722 418831892 133539140 667548606 511481912 683834221 104612828 927018705 916171816 789928354 935788581 76608837 618434609 956439559 122990558 305908890 133017709 875451706 643182507 552522163 902175241 569056194 791990490 327982254 180511599 462548645 882728126 501039198 488842961 156130503 70065772 989529375 897984992 613568161 453561698 385118346 179537090 81564074 56174068 251999415 357056687 66140157 748756896 772397076 148932386 769995393 516020575 327549971 348167654 567569733 984739096 640401279 349972405 527059866 573063818 564702069 959211280 439734185 783006300 481226691 592025665 322566804 430432276 930964003 402214029 726837189 245869291 872228498 885753987 386292937 532017255 739107278 174911223 354740898 178481858 361490847 618920606 140291390 480331471 689111289 510891534 512895151 827550377 194121425 971365448 4791975 63840910 979579540 956309297 443719622 877967259 686449872 547701359 604782376 456984925 40015759 85230260 470755501 883431620 718178553 402509305 585092067 655778954 190487637 530186372 602201907 58300662 964732031 698306409 908377339 639681504 271749028 910667466 797894427 8430880 720614827 498087795 391181410 989667674 892148667 660841068 387401318 432314582 235212415 922137729 589984377 986516693 455153081 462892622 364317821 77165367 618171319 85303475 249035232 361239493 894821487 730561665 299072377 199674516 87233959 658654914 847860074 618212335 625826172 401305781 400169129 929931061 360723241 289966681 25061139 23306231 351582882 95260604 646316965 253453561 623904360 805800785 17088662 689276329 35344760 8632932 494641405 439700237 800771813 48363997 463048198 833680163 933284515 462450212 190786783 779831465 928600527 338200167 342209968 773804049 613759262 413685053 374530557 48153246 157171013 793294059 743763013 374102322 994983963 429358635 776969619 392690800 958765069 349824191 79125268 573442030 86578807 265674954 373708563 72407227 131793388 916519587 983230926 290409487 723130139 916403697 676109907 273221474 394523757 264390271 543474561 72440127 8877183 998783827 663511728 317646393 27037740 971562747 648470366 245907412 217797263 957294470 814091936 926004210 601681696 397391361 372067149 89035895 68768660 377202571 75817372 24925384 769565076 222521090 382334432 315916074 337548285 570295891 973351781 577221877 689025765 48877301 759175621 612968301 253771709 902180923 507315259 379348987 143594550 698352713 978856391 23699021 306207750 629944337 699194637 418493640 550171846 867266428 865166318 838864266 909795207 81300713 306367439 721980690 790100687 366547901 786400706 843853557 78746034 157365551 87560316 317837371 366143709 8741668 156418939 303110603 925404153 5314035 112631467 162231045 30635135 38654825 289808590 251538322 353017056 988846722 184290927 366565704 913264377 56963622 502835128 875815039 709140876 90842133 206986365 670743357 960014196 575488257 805809130 260655532 207686925 795553425 762022055 225080436 450449454 84902103 911486908 509951729 154724214 889182378 358528756 559094853 221022717 401528669 264761084 729524911 727911302 905247755 551538155 600294217 986223655 63052904 869463210 454186479 158339900 7477523 463032788 636159374 725793209 551394389 75151481 766820943 313199031 795273397 164149389 218956511 86657111 103438540 595160833 121425440 374008190 91199438 351728573 497837079 534725505 1751851 395113245 23949558 21939554 716061624 395548857 802506755 280308220 415791424 155071086 505137914 425348967 43566044 243793181 600262673 745013649 994944487 376943670 839669757 967919146 974228621 649757162 7838349 363122249 505600922 213718249 304461754 357441808 567488959 24683133 350687108 34851157 5365085 843983559 304172735 281836151 202594569 887714379 938750705 745900746 467386077 21626507 617262677 338214119 344321246 982630083 636704268 87194779 957561798 286528363 911357218 422740264 659434568 244601428 520203785 369260623 856321993 580836294 920855229 360156427 807802776 791804497 143652317 965177668 985179043 232443053 792720862 139498470 708916661 395826506 186822484 60389330 21733797 796741505 917761601 457900410 191184457 702964843 246618064 672303921 669305889 104620218 446693007 85068137 168540432 772119968 811258624 622467432 547298065 329762617 374076030 207789211 336556682 311328405 116888270 731444374 795524470 786845078 22451141 968425997 965508464 686863782 824325774 611718451 974057589 177702194 22901457 359308787 648679257 304603103 702225444 249358849 618473902 429086725 533571917 969867203 240965380 969648010 555072927 552846449 485805044 281854119 190944042 841766794 384820807 133071004 859555021 454103465 106322662 205410233 803803963 280221957 51166168 483997857 145201719 587347523 704938841 205963082 502868187 131114016 73701657 543255196 90038370 730691493 603770008 60580703 663288193 607275453 515957847 683132741 950062230 50709757 779265102 414403679 485498197 105884985 987856958 345416253 912806271 80834090 171695621 607723210 950996287 655356787 682130043 615396984 911438945 203925562 877497189 660215955 155028110 788084456 739531197 57024339 678604880 253078951 423527529 99011669 804767281 314087778 100701090 781074013 296441877 621349368 588289901 102060096 972310364 246140048 372963935 467565781 698368004 257668785 40479461 794588756 247816156 748076658 3678181 439187138 521372109 764960312 514852794 34829367 33172180 488382969 900857524 871841317 433855327 516875378 268523724 318427050 203231480 126528454 415214050 474338453 339478190 899852185 92328638 58617309 484630377 689891584 642225859 899264419 485993673 608929793 464002507 366821701 474083039 868652833 924964134 562689026 990552279 196184441 115823712 39308995 350211359 642009921 666474361 298755016 834979380 738917058 782518960 195681962 971547197 51859908 563522898 915498377 339517533 321666968 708057066 518370870 673716561 427079293 878073726 438991418 129334232 734553479 719318294 734685285 436426310 46990277 302768639 482691778 537735327 383991767 966400887 837118094 428026762 74435900 139152056 667102710 656083369 779380358 499564541 435770362 511431434 100899963 923069488 313030824 762694596 707133919 447055393 998220925 469899207 74209121 331105802 473918478 94281805 399527010 128120419 699620029 428208378 58716432 621615558 53940686 740599597 140871443 16704212 106898905 886927642 997958865 966854394 314271688 830718865 693444161 678686597 933334603 945537263 772791147 113718997 520552510 233125208 624416930 191662353 667177425 577244063 154838372 637759998 637706419 274395703 670188033 882297824 369182354 853297714 898450160 40468749 713106450 389071828 453445362 996055114 608330769 432432718 907245397 951408513 318840283 165621717 227548933 169241388 552317096 283278446 936242224 719180551 866451637 351486124 727299002 810877315 440542404 120482966 207834918 867522530 437702310 761061684 402983526 948772579 594038506 251747800 654226805 645876600 989910913 928592385 583379555 492727433 88557834 729934478 261531183 70033538 972048620 828782498 162781370 774273735 816988488 450970338 656082569 956633472 895816679 396405405 511366897 335049208 98693876 924475851 293793987 936705368 426273683 215989924 328387063 853078614 287114063 531418332 143046 232361158 571522972 759308143 790444243 460060714 14644512 355026725 92250954 129335866 577100378 458839272 863840914 355725634 789893418 274448944 921013733 833272325 901499640 276547109 770093284 450712851 272259144 444432887 448724065 427271168 554926921 363579728 502919579 103351465 358499493 664071502 647865813 977745285 753109507 577389452 287256845 333678970 238970597 491926274 987106743 361949687 352421732 632837243 824430844 69792253 41226749 498929778 734081601 365036956 433641814 761737688 308476897 358643493 197255250 175533406 879151296 856094200 811385980 29684426 879746773 608208860 284436298 148802078 199081595 512385224 323660698 92055967 796346509 651159549 151020354 612976872 726862151 849598719 562618818 939505711 73535375 447127539 405811486 792192810 873635353 805873979 404784818 959714457 672727435 258495280 378006270 80601987 428747283 365132051 578752504 480373719 604897598 29361325 155610397 210104969 49375565 107012728 187633973 868134024 972215523 83188494 601090910 552509488 138688323 963119837 936983638 203177869 332538363 877499310 97500273 165117778 453492340 410454582 912382121 279010062 898391967 548311197 584442474 748784283 117751163 816966068 352321951 237994611 93921633 808590673 302245248 414833817 69275510 410224776 865580513 994473588 321744089 394022593 969375789 577519182 873146327 782014324 128889827 494541609 196333219 982446091 872899038 740163901 851610291 782505905 991436030 663650753 682747851 537232451 338216444 316597120 13708766 58751149 407258216 709870969 871376534 363552973 289508968 596348194 374101760 363624673 601471227 330496062 985914511 525523747 239989723 957762071 783074494 344017032 201664208 35070795 111378978 554315972 12268176 511280279 267767112 623856065 100672668 552336744 956791705 440762162 419490415 260782671 39304573 415356526 508981138 309500979 164425211 862558441 193241796 132838835 809224293 694138210 715901283 55174518 929870437 286741584 369572316 746729951 817104190 516100929 221209709 929655772 605829512 688147 684443269 649046875 6189625 268468426 843947846 73633228 214785636 44293676 537697498 265710625 284733130 662759860 335002845 602622808 990178211 540109755 779701092 754868202 304437174 998583178 955012887 408836234 538103285 498366999 974061178 982514635 548795549 620561391 781761801 494494150 684579120 891460614 686143280 293998773 438974756 628472499 672929600 956722588 582077443 776108868 765176788 498978725 660846342 122356967 973904523 327458353 122555160 524252081 325140316 757825009 1187717 88189179 95497572 258715798 481121858 876720160 707743405 218436814 122554366 890455234 773767952 373771930 274300071 481178121 565374878 157768453 450436194 741114529 702499447 234778007 546956639 521300589 945803111 675637588 756131264 10773855 554365163 642049933 327972497 274144819 49871212 928994050 945816604 566471641 475911543 165861057 335015605 830016693 456535062 10685692 641122741 838738991 771815994 862448117 724082670 505228484 749112790 493320059 949927053 920988853 27252548 588376247 655299114 262160049 317507258 269202619 763646189 938743961 971019145 218851086 600189301 204360591 870092951 393665550 775495878 150448607 406119793 412840819 379451605 971408008 80899213 17858008 521183969 637942096 398033158 15358040 828922468 153044366 109418058 194132952 490174231 175009983 730134539 302801992 978169851 266618327 940567066 725612106 381856234 132899690 364879019 647349391 466299434 581803443 792072901 995585680 832080454 371790467 52234541 124584251 150931966 47699596 213664376 88927299 905753456 289930787 319311001 138631021 317018032 446693021 692648153 371739238 42362258 581752645 28394653 190602635 73827804 650461137 893680679 455960173 749410972 935938866 328240857 892616740 84997882 721852727 451196374 734573430 663569519 741444499 839165646 470284650 165189338 345162116 544820458 377997126 877734774 322301411 66607620 88682004 440717699 78515631 38155607 828809298 482166063 626475010 18259052 327285044 123275349 568161542 215495074 807235777 412493724 523052901 264903855 524551261 517064361 197687495 20155798 268316572 468595334 269477204 817197915 872099401 73712881 192584657 802714356 834697188 925016695 263639539 195179128 399102225 745369284 532361351 344414471 407688947 371925188 244704677 957323221 8609128 802308346 630937709 730570583 296230298 582944368 302104986 268431876 144218087 679577631 655213394 439020871 652905792 944500406 833762620 130266662 583936554 170416314 70939033 825289161 972006721 259400930 526623544 633863400 113334799 786927471 836914194 735894880 1571760 276210326 224618225 747398167 816098072 917584502 16482550 661478039 187896669 157474870 44124210 6205866 385272303 665852610 540470784 22607230 316600824 975878830 992186853 636966373 977039058 694514523 939478926 340964858 436956533 676387238 410820498 736773932 378515950 774051311 332194572 327672236 357858971 344802330 944459220 704552771 392030107 763277864 373890941 101401308 294459715 135854438 422771044 541255020 593085772 34603942 402856523 964413681 89937873 234403018 486948311 390373251 955592572 32111126 36262656 220241646 931051924 642004757 936139327 605967401 935817744 725189997 486693375 927896934 202209655 97401196 18202131 415414805 401083765 542186835 64650318 415675278 498433951 304638206 464032559 809895964 582117714 360568291 209140353 88010614 793018311 713727762 437364813 838519900 414384712 875337404 181084381 302348744 658704809 685393106 398868722 648272216 142279097 608550226 820906757 269135954 199180651 751914732 539094498 60590629 993639343 806816634 813409972 652696030 931740000 221982620 223351810 705262800 168348919 290077696 180312866 244171456 323628673 188190676 234593947 991420280 594103477 974334582 965943749 291759345 716457189 631254788 124160910 613301955 385899657 36404133 4681197 655038 552473364 783534681 699754872 397320555 156288251 838316452 25890443 82174853 570914240 307398602 619117406 265805880 500313212 549789526 154070616 102873346 732644149 375073982 762239631 181661245 854984629 712704219 783574589 615620183 369714859 465515543 243780177 472221482 304690826 789136082 655999275 687142778 427876514 806511768 756381634 909698376 103869850 404296129 64568448 457896601 946872349 556055598 83017125 273382076 569030806 158679845 636524694 507272022 936464511 215356081 891428192 170813696 906957534 703005352 883223871 394178276 797268669 352932248 935996139 803247888 536796621 63134857 721045096 619165923 779631805 725374261 413458075 411783962 100943199 548929403 953026329 190348779 60698459 527605409 71328101 101079497 198272875 647716310 125854247 102744425 479604234 388280343 145762651 320071041 205559785 174369826 19527445 73818934 77629060 804275517 436021114 249591617 187825039 471171069 375023967 252682366 335759222 721520017 688818589 181603758 408023877 810589139 937990214 940821398 77311246 773464334 174913897 343037561 946377955 105024146 677025933 692504567 215434559 324657847 851885267 489400936 746548759 718347916 262576951 274674482 582068676 7382523 791374824 915230724 91618677 563011143 4294032 537868862 168793943 230764884 615534037 280160333 661684676 203164709 443184939 370545198 308098690 984545271 330504329 282142893 688396997 652575748 400238236 69607097 861635873 108236797 698509054 746123264 989557532 148661388 257001864 82302618 100791581 858608198 786147739 248742199 426654980 129167209 458659251 406080752 597604985 6932032 426923824 48073568 510205597 485425947 743520052 758818507 500106478 253456136 736104668 388546740 159584812 699002759 902459687 25059591 587893198 482730166 357109665 458770882 942541250 996354619 126107844 164634258 479892385 759695086 147569334 830393482 619584724 811970798 700646013 211348330 159922912 913683218 424013183 389121778 155481492 708059492 566053869 643107461 555258893 639030167 35333116 131649064 961056406 940898537 507110718 91047388 27131034 551292424 161837785 476702820 506865079 578487058 601263204 264013708 220315025 982373218 598541064 301278853 468856579 178703911 1218178 253272733 743451910 905420807 632157322 17666924 853357470 285455715 677718955 404549850 250380986 915626119 562255207 477389518 945269147 867492060 791146094 764357213 659155975 812374459 814767221 217436531 295918872 497664501 712698333 611689771 221599857 484082099 450212824 422552564 251592112 668044734 362779233 911741583 649320657 125265936 904659009 263076692 49709602 418603213 940313599 749672817 231758028 507672292 394323998 263125671 127208729 855502051 405741729 527184720 190519362 356871746 768279157 150185432 712013623 962505230 296869129 757889877 657165522 809407972 197560904 46210447 481080880 967533685 296814979 463163766 703933258 62966755 734211395 380284781 866590899 230280360 917455788 190044410 214523867 885641333 206309879 651901314 90979562 707990350 334717128 984505845 312820982 491247426 907463794 721441447 9814579 973268809 677627454 886141774 36824229 901336067 624170570 149964162 944142906 98271448 550791977 703778844 391703785 339007915 165972902 69794766 613862020 730493079 23248679 236796167 745496435 871840138 511441051 524947461 385661370 258364871 525118147 796586713 7069362 8644826 411181437 402377740 565529286 746884344 537221366 583131967 760310132 237296378 241353757 718685563 370242354 986862547 816230724 222728251 824057970 272336588 963011396 256663031 72941096 218459277 813261502 479174602 861116278 108536317 508950978 114270967 114617905 334588078 381564489 153349459 867250509 54937852 589463987 328781415 336361044 395099801 461308620 274946014 123928050 846977821 750445275 587978599 962009435 309618726 35975381 20092190 976375540 965790891 268932671 200667605 477711454 211021607 784982976 369546167 619640581 942343911 914811833 88780674 524993219 557040399 243226926 655158455 704911260 75304067 532128173 331827662 980999312 277542946 363917191 961510823 971335847 598795887 814965446 696147262 284670945 441183286 929255826 207964994 933321142 750584799 29660106 846569701 901268231 770489459 598485725 331390756 387409098 861427621 422606560 680518989 932803777 118373036 103431705 686818801 550337100 212950804 172950184 507845318 90116460 932226063 883540069 929945447 591104258 960791931 777981147 897940868 950939005 703480151 431169528 359369960 481025901 489689285 772008457 997990984 228562603 984209236 324272326 995401678 862666444 268053702 893369956 216926855 344699891 468206305 918168935 451752552 961319285 313753040 42202967 116363710 783021113 209625683 56902246 235641432 577021830 796219100 754563271 185745344 346944529 698307917 208926539 370478457 372181306 501600450 880460953 166884004 797198865 757920558 570398073 852725802 25727070 866184897 401337681 110656128 261828001 18073487 550897017 586419038 530955022 649264628 700512413 155615828 891394162 917842580 924006941 207459268 956834097 186400917 192632522 407098907 633521635 878243327 61390597 732307779 789951089 168953308 987754549 309982517 890521741 844984024 297153484 104016714 232995940 923548503 427597900 623772411 101234656 219361632 855009925 552712813 869039870 768991287 919397660 956511722 381217799 332023430 782271856 131114345 723742049 955849150 545662055 531932919 314816677 208440929 210056112 827075035 414512847 480823670 363606175 892917012 637412679 391108770 565770049 429475051 448779060 118609497 908474749 596650196 994050712 5449748 883413520 608625201 710901183 413866405 699472690 817672583 611260799 838344450 39192204 318041921 833991628 225041213 463122221 990470039 315361264 399862509 498422011 62897569 684410207 653675106 487170447 883446526 684220608 570402028 237973365 485862559 724538918 852373244 238888835 97744405 730441869 611409732 223340652 398023826 48672563 355745151 615831087 529919535 674035279 936425052 398158220 477365053 510757952 513493496 259606887 811499819 224129885 147625917 987315348 728846734 956837864 592820002 115974044 87434420 232623544 126248700 579850702 969936114 745420645 876581797 596728397 72571283 810819881 969930405 669632026 729775555 847387284 140488160 830123905 616754391 69302300 890531998 866965933 643550017 130938836 177732975 833435321 854948313 80109388 832063377 97526007 177364256 272595919 901228533 865788598 556872430 617146500 690990484 456588824 747195960 743900604 704544558 69495716 678414217 175664698 651533704 374578374 997795649 993150031 407680573 586907512 904944220 430409440 721725356 78437977 731895192 460962920 964985646 846692664 980253631 821348047 236631660 232121530 838654195 796460891 629455847 860429563 88482475 809538645 105168865 65466081 816961978 590204084 294218917 81039576 592091501 91213033 206830893 30966613 7117691 877553771 390102274 664763617 599461003 14266019 17317704 4658035 542348012 990830081 504915359 459191091 312730525 245276963 248437232 498023499 132366713 980333290 256415108 65520563 920931084 331032562 351948001 361939808 957580980 660026013 492054136 80478086 586359172 878696983 172836146 607059556 994903458 502452934 184471857 395004553 981174926 447458821 263985934 688146810 521665800 583862148 272935069 820770012 206046539 147577527 438030339 200818406 411242281 744364838 786173803 343567635 641943177 761635733 315448107 98452475 704981470 279728531 233306025 447520922 840929413 486039186 316651504 1937354 877400995 569457675 297454489 724680347 124561599 584090256 376205540 149486792 370303013 58634950 609142442 923467283 798475351 129427835 218176354 248804874 374887372 153864001 300427745 959956887 534039631 997288003 849994320 808984264 809104118 803149885 547580757 78056173 761258214 250826491 618585437 709670383 202903611 786076962 303060998 266700770 426732543 591141008 897386536 310546647 178275426 548779066 415653791 73763365 279160738 348728354 510129851 970583627 756019913 642589506 91480372 912759337 333447490 34804750 124975142 161829840 502565139 644881908 952954340 295063566 384796264 496004573 389275351 408326001 49808614 514449531 629432032 255115649 697519166 466606788 957847367 259428373 143262082 995479629 464696893 649113505 945392998 679042733 785175580 335442721 361700593 197963961 70048831 459443211 880951355 781525629 655609107 122548698 740582656 159590677 674959232 785077736 357014320 751461483 462253963 918345795 93687862 444708991 564112767 30762864 323404977 141304148 562817646 161575034 464528663 384539531 206586914 857290466 536187139 975343122 107780604 375395171 723631616 160085208 471135073 71769897 95016551 245958818 490027313 653965547 403101752 832173169 533654412 155187321 207155146 365451962 849057232 251117274 794377241 989216832 149158755 369100606 351224857 176415139 549326955 124370907 248276517 533721994 109968696 592540927 840474551 721070322 168348304 372985115 772882026 133052783 181238960 85351576 153944128 197355949 634611042 554216839 224349624 121324409 348381712 807229955 680045155 674175337 563036579 497703070 320030702 95097752 9675538 606328486 852722009 755590605 317039830 73606995 691328122 115701457 376419714 8622586 373198917 641152016 290544287 908711788 349475073 204910360 216199235 113145878 686249275 41347524 753039239 257093202 469945973 729383564 722090509 962028068 466407862 237476978 958445972 852822515 850500696 223281053 547519650 305333797 422100034 84598267 195248105 348210927 8071265 294567522 63964942 290562595 918687760 705007936 949340678 89794080 440709394 58749174 240151299 55605980 203449733 545238564 441556986 327644104 137815084 423283317 908198739 376779661 416686215 915120880 41203701 923415108 711447308 82458061 817423590 936042152 502442313 394435353 983212709 223168866 682658360 126664389 674787356 530711349 300062172 650691552 675133519 225854170 257216261 118667075 77110658 904899136 924476073 780632191 371713326 541425223 59321611 848132550 56093876 731003597 319055346 111111099 676845435 309620907 191984151 85023495 222304566 608539780 782837897 511499287 991044823 335467181