4000
299370763 450577124 933027790 339949783 205309872 884117268 281251589 342210779 570116589 628187571 290036775 504828970 26017598 420004609 426641143 958176924 296758214 245668666 750071082 285341667 839439153 777767740 355841974 664294419 300420177 831410790 564463891 943679421 453426256 43539101 769992425 745161306 899957424 289020983 854580679 383746175 504240257 910844514 555677018 764971548 347793571 656707908 908110798 164368878 90111453 72024963 330693730 770664851 159664941 975899242 888856833 18493169 575812289 925577801 835881784 108954656 682172903 663914819 288184700 544248779 111328905 529681946 916849971 780177864 935973370 559579040 856625524 571218879 140477026 443420581 695805393 49292833 503014682 827293322 184236255 293386244 721843241 166504242 728131743 552712638 450463613 823872988 112881252 435560665 384560502 689043476 208591080 321435604 850138868 280488141 522965230 494818778 498299228 129068090 646529801 809607716 593961154 37063167 503211410 744601566 729286032 221893046 626775890 596627021 96779349 97320586 914137098 93471997 603127278 794871621 166392021 299786281 940086924 663702539 190804546 593758258 929456312 302392657 590644266 546177066 525865331 664033407 121146055 592919226 269852349 911526263 70237018 564505965 404502193 346362557 715251603 501672924 78458585 675695978 26223867 802842700 831041076 737953250 516220282 273913999 863946847 640362303 576269715 757163549 713269213 400762322 592173609 902608870 431653166 533042854 490023297 688388797 262036225 341305701 589853671 312780022 43858722 963732135 213837274 88104389 825243099 234930693 369180863 560410992 33368303 228142301 167954543 803281772 417444269 26484334 387881396 793268540 409721493 11581085 877455195 499147143 166926677 274144944 511020716 435334371 574219889 310343963 206029348 636696092 604209717 392409696 811112276 306428021 312535276 991013189 512367583 767684728 603873308 312119539 35660516 986409938 860931245 24387905 863458363 804080620 582615428 850446276 608834097 936039627 395462281 576522771 586096750 522130404 44393820 98804910 71989029 186836856 531596804 443410056 145770292 68384584 835978351 514246658 826710871 880591307 575210673 842101076 211257189 186799622 790804825 680806547 968073516 563109804 604968351 290020728 561770814 691084134 984429650 969162956 587276855 742618621 354984115 444156514 986440927 540612335 409033917 369305269 721548723 951108693 448696836 607495983 440029312 760145719 283830410 311712192 665596207 600765477 352387576 29929559 799637697 221674313 586164466 729066982 249555687 29128761 552827930 673554782 737739656 591107393 232154393 185996295 73291085 572964914 264844818 33180120 72720662 83356323 894019644 140373427 420314302 153632956 26986515 499741361 736414390 572245833 776733611 457163554 394321654 920630696 873718805 488964852 669521140 581055205 403472074 870360151 850751518 820920670 401729626 645536921 629176776 108571698 292608343 181521010 98117675 612672408 112418715 889974463 973922453 75719274 769143387 489890722 655082239 456530565 195345178 722822426 685354212 52674238 997096377 553218838 258736099 176896950 108164751 301802433 760063867 352682883 451087443 693672448 905762847 818669428 2391683 808818961 290738318 818428735 877120572 869952919 189537053 10329292 675144717 482364327 465148558 951835911 11833622 332083938 688918111 111004528 678999561 954498674 161760573 570133412 890566085 52319979 441510905 146026801 982871617 124039396 845530737 505019798 452929844 646560757 410637531 953346627 136855088 355088768 883013906 886167215 995353082 903926542 582965603 877912725 829410292 650754252 739755774 220025920 173764799 764031951 671793652 595673251 582398100 182624059 647568209 618440914 472531545 642039089 756327499 961178456 66210145 234687962 197252441 138777177 712324206 957271005 213049636 73863310 967018137 491345322 592219016 427150932 680256689 86726989 574368976 309031895 978725000 962870995 718200251 263574488 109140228 275979677 987683694 255243938 274105497 152765729 110396892 566730742 309005126 745044112 99234565 87523984 191006655 516861113 457814874 743920037 284754805 668028549 804884485 912288119 274255349 482791888 711925847 382923624 930100681 167053713 842483882 136884670 419856521 613049120 804908883 438966469 44933993 610645588 143312787 394845285 9403524 770494217 758573142 687326513 240247714 854113794 172371080 68147542 845713182 257137260 558440412 621072539 931167367 509979052 878514621 802095912 83272947 552940890 574980952 272881134 22700221 933368079 854986644 631939282 903030263 751527709 93800890 118312741 436385384 950115861 895594599 245859210 918143242 365917623 318615408 38916289 815041109 334770428 409517859 50056786 589953818 677799042 724471166 78675379 496170354 983659365 149210035 883950589 944955601 888058203 721015541 315288437 134442531 959554890 237327555 140042227 56410739 710790704 345296062 614575402 97915778 579786333 830662736 804421254 761747567 161411235 512810154 385338706 676212435 13275806 809171645 840286540 694286638 24213313 183741025 827363946 484937564 264035 80485807 538946516 797146779 182789199 451851614 918251233 853501053 620865951 41397947 670083819 271320891 388213941 407874079 801242676 403326136 135461352 283963396 202037862 298564646 148843797 515067619 228645209 812515527 15450718 781099380 515630211 895970134 177348198 360089044 428192839 594813936 774475030 467391276 90533174 768765486 338277810 542404282 964239372 836030169 768821938 951034181 572634993 883441127 354457768 10131071 711688186 181505737 499913661 375451409 433704509 704744169 982788551 546997007 423208522 215883939 291805706 150929962 868561393 258355890 950213708 285888901 27614206 873495280 425315342 715527695 468694497 730145044 615038652 102903005 903260911 717026486 56752946 289065743 49187191 399647760 127301308 194784708 791653801 376148567 158489154 638027900 657158909 722708994 59438742 447343710 496765428 104647546 834599784 585933384 479685812 795697787 417898959 750993494 392584604 122697233 87506729 249773975 646904512 586173609 531874030 453208125 101807730 16060881 736703589 143348666 590323206 110615205 840504049 255691765 559193644 832849134 7981278 236756996 721473604 489753346 960442028 890536104 933279794 963097811 11498210 865627460 747142649 839619227 667080788 452090026 478211388 235075058 991362279 788440436 280526180 128447415 257456589 869711923 460520911 301937168 724202104 901985491 419670473 210598837 957879347 916074592 80937905 628202807 765703798 462195861 955441412 766779998 916811716 468282505 771266388 878471925 486021864 484817607 397641345 838714211 688236863 436468608 814204805 455972847 761299886 51731996 180492612 71417498 529263375 738989183 549112242 713402155 477560121 945016616 131012160 437580769 633990818 207036223 474206287 39493836 260543739 516220295 72700998 757068610 712524986 447801699 344704310 991840179 740101915 382359223 821754958 675229448 460091349 593420989 687408611 433017550 799400633 375795477 499258770 754643933 14130702 941963446 334388822 942707974 434478661 791456732 162078585 572658337 418832671 942992911 681103327 598104856 37808497 362179972 760241953 594513431 690275538 504669112 174844018 760539946 884653596 207845525 91913130 857868108 783430623 875498723 546151606 367887280 719052587 589548512 250757981 678996898 949037424 298018406 65578619 260683952 139396331 407562751 285699026 74104549 884046783 6058507 754960345 236473226 993988339 819221865 126340646 703730655 33343857 15620201 486178161 70034629 945026173 138873909 535474138 451405971 338609392 222659930 930633741 786785680 258892910 530074292 101648650 490982573 361472434 117015725 132013401 380833672 423075139 689005684 596684428 602489729 971902610 838824181 108498549 327632833 151034373 760759097 248389814 364366128 253349858 9206236 349842118 787825433 242240292 834953758 417155609 278960110 316693998 135615599 590940663 168020993 285096289 277166320 582427584 537789376 661485861 907506422 725420517 817614337 979055774 820507727 214212442 316641203 454041798 711137023 93932895 429696098 612247539 891204790 520618331 263292392 645187220 972794163 934241603 899410406 222727859 473049881 95825452 217440000 121128536 763324025 957544449 81601683 231665378 906980173 358616935 902853037 725315711 615070587 456745122 397298072 401736051 764573378 682210636 791605310 684395996 766103287 731742051 243269230 586809 543671678 567265830 792818508 593370643 243860198 262220656 856864556 155485899 90445671 48753123 671326620 289698892 980500889 152976901 533891424 951013268 592341408 868446485 712496869 579551326 207604975 668992011 328900990 520556154 644199918 341658120 542024454 189873412 725942704 736853669 503684881 942149489 542776365 76910524 245741671 660700910 671874621 619993869 825659470 709765087 458106348 490028761 570704017 110458517 509898330 447987986 692857575 326752911 884751970 395848525 562660510 732058088 153529599 575620267 446168043 415738286 496499595 470475073 223070400 869350497 835892158 435729909 238334485 281724973 68852514 669295454 211143292 977828781 41938683 421274643 136439308 581318007 161267578 745582872 515509651 59823716 351746362 716120109 576447444 171366996 38116333 79993140 840332562 126924988 178527864 665361491 171121754 244472415 716068613 361448968 802398689 305658684 488976982 934002775 264236173 682511512 399920389 176651121 19939760 885247120 909677469 268039363 348203565 9481806 887952960 614016662 605619932 490796272 406263911 745286569 568670844 102280727 487163082 354487583 188402008 898865183 209072725 23525510 218578200 731593835 252139187 619672706 651264999 738623189 962780165 804556505 53597812 943468080 990609250 748971870 641058852 310537059 374336416 723608681 614909222 660663893 510801378 670614749 941032265 986573821 361658642 25542132 429395247 938486563 583164341 260147526 322288954 176545006 537224155 712187517 757161986 703052328 541788500 195804623 45433838 292637631 785947515 837099951 937359340 630674105 664873313 146984034 761509061 134880033 380391002 445391906 497136633 676580724 833375837 415824576 742525425 160549905 909312066 384091029 471020901 973588674 77224937 384288673 465517341 170959946 451972810 613415834 874536125 172284639 974384480 197657865 933335444 691037555 402578975 359667795 853137469 229144234 749399167 234027359 271286553 927505031 109890499 982055153 430500604 427250283 486951650 419307956 472889451 923222215 401207913 612889576 372135006 406199721 236360130 990672901 112624810 559406673 1449881 109257683 261021272 584165464 794198676 557294746 21598977 253588090 48773665 594476707 213628765 614491887 25688126 396435561 620717822 489149017 711961830 571680022 850273572 356292692 731672606 496741297 992674009 325340486 490233020 775031097 256736324 151137355 700911918 816660935 696416630 18704858 478988196 339483127 594600407 593010196 525875326 788341120 379538725 693293140 683094562 359145188 400874995 806643992 439565886 534785098 205414781 290688579 440589797 274467152 309385136 393027952 705111959 532717786 253766258 812145995 804867354 664149002 855011806 606674257 115286817 314504567 964873018 645095770 567807406 423583149 111385761 41893529 305699189 885119116 626634120 956194421 248706921 949025474 131384413 628523342 599939190 349821102 153877652 815239980 643654280 18450662 256419206 716001659 917089711 953339719 913374112 300068727 725696068 627475355 740010515 160537091 982831641 214107961 959012014 7373957 25443140 51080980 927009512 413814519 903439081 134847168 141957813 724304655 609169510 332005436 486063469 9151551 763320278 743402062 780105610 783164121 18506253 343064373 85089788 39217098 23668148 643572164 394653717 799066081 368434078 776394158 856842417 827670625 249258223 51886472 56657586 938324566 140918872 140906752 320140318 643733129 145364911 449427179 380407283 846808437 864876005 841681074 339121415 902717260 496405630 440393690 159553101 930806123 130615200 504323980 438134946 808869527 292829779 600137136 996577960 720635156 444684029 513932706 649725469 261962365 829236052 948252252 188294381 550005664 596503212 630299000 129825990 533315427 442326153 893480666 907551023 435019438 532864978 434229273 435804465 696020813 21466991 217737570 555253005 944297447 608315153 491786610 857154711 847067105 990991920 29475856 131745957 682135117 542530020 290757514 731673629 529396911 771453275 670429996 913666291 315677042 916817502 56292481 789887408 383910435 471636772 605414898 939367383 633390900 531600226 47144185 707949091 759831009 737431720 799716762 773641820 773220138 666360488 840027721 430826202 30319464 348513304 657670155 37977670 553844471 342849479 131210278 333141762 392249035 996388927 834840461 310999164 27598327 853061984 211509693 477819294 659605270 82693526 237690315 723382485 412830729 82755361 889728779 24532957 859601998 749275879 970271536 957005884 428781775 206786545 521849928 970175339 187507615 74753230 590362712 25569558 421712795 201798190 134116103 797950182 100374588 342060453 415110302 69512824 252379806 333304274 357033470 907487827 870008252 941842225 500324998 685984891 67032074 705373707 665925295 736575871 936431523 978219348 109394524 107117959 228049924 618892337 26243630 124934965 34332019 660353736 756088011 700346019 915859720 346587258 330192937 421435957 145810030 910640570 176162278 220469676 945846957 826283730 419388089 746397972 120798042 535449246 141737816 904917764 436911791 176643059 92801192 892644993 743368935 416151664 884556820 620458739 71044284 859156700 970509124 678673777 597434396 511006955 864024084 61271940 789258972 821435268 229962644 692158125 430035654 722958099 133384036 274391233 667255183 565282738 64173727 257991791 646083266 324134270 131127656 699613824 553320569 362919591 521398531 839628451 283205947 930473967 730740639 725010042 107264388 517344783 221588022 237767289 629298257 199226535 206006154 708467827 445751470 888404621 537398205 4548719 980174024 160133274 408243949 136963759 915989583 732343784 651327331 244429777 351874413 833588690 650317262 463769567 195922501 157412323 701378616 495562966 474158912 955214698 840499708 834142791 467021022 639747075 43854461 93001560 219929563 855636522 569971570 704955428 238064635 640927685 916940573 71743660 458395888 301490569 58698838 35567739 457116027 482028541 630896028 529111715 639905372 492897666 828992115 751151459 450846384 546850476 200019088 533733383 415256241 858607782 24218168 236806705 261403019 931816534 564393404 961212912 497400884 130228236 378539303 112437498 993580157 706165328 863169401 783325280 331116046 543999911 668707207 101140301 399119668 590361161 701785017 641172767 376808355 250534707 946751398 178940818 175007715 844274182 717983758 743626459 323073790 682096718 369585281 452198889 122095913 13095743 459042980 333142195 995230009 524539451 437528207 312547531 204307988 274635052 275577391 830974541 81072684 994368024 215149118 186575255 856988046 230622247 185768032 896957366 577535469 96049413 242855344 641955415 942660385 309694438 112618292 890514521 392997835 518840900 104501343 370589471 995950511 937804498 291496053 913594172 61806525 689280523 753204000 403224876 400905803 262444362 292525926 394857938 122868610 817747289 562944265 214733215 994017644 977714905 988722613 792562564 725632652 885282940 963325273 563288930 904864408 400865019 8407659 498210117 678516963 990660966 470347053 613808002 968773742 617336609 261697521 95554151 55103589 132245730 859917554 953999812 942082251 644938542 883577646 249354259 270133188 410449981 463632867 66315659 620325393 115346381 188815047 455040186 27422344 952203480 642114223 468712231 942185850 670071691 873503531 337109341 507667099 935980840 780075771 144124332 355726086 622544756 785440287 647308122 949400137 933693033 27483184 932614000 157783764 514025759 368942092 984432273 790776271 526727121 246472811 848299352 987950115 827285303 410285471 622573233 612211821 741505076 805487049 491839062 985325017 495370726 205429509 656522794 649188638 940904107 633339062 464908475 115717557 605323795 577042375 236608179 833524281 746925452 529181129 880618211 367301335 719474858 302395392 798293499 103549300 908186915 309798836 705075004 709316277 401447347 159907544 958951814 874747621 325955501 778361348 567450588 637844452 942386068 491796750 322870304 990292531 780940643 422093060 708732242 995344496 114310586 822019994 509479498 752988240 426076531 228932874 789479915 628444933 849851661 237404248 818698517 564020142 475756782 291878196 469225256 474114108 947861186 402135670 792329696 106528542 975296784 778211228 586029244 568336056 230662743 105881554 936644675 189439866 276575145 249621600 482820228 913025172 876874109 165337661 587429530 792128067 860939224 455185911 605967993 612292542 65702902 625932316 233642466 172755258 652131093 132604948 378318481 645809526 106492028 295889021 676929570 669157024 964786317 606222319 466767718 205449579 738382739 147468687 259268356 575531053 782503311 405983797 434891038 431945716 701850054 877885004 70402296 63189471 942066470 748570073 745316294 117383969 650089675 822842623 544567220 202418652 361540184 379285887 855142650 425284155 556383651 331176581 690254897 639711892 803202096 196153263 352366100 157253409 594890480 735335970 995414012 929705562 547738406 117546451 4015733 297475973 854281550 253385179 618881296 579478371 409751484 919213142 368599878 280866832 904994094 821133081 539702334 134388324 695904022 427094733 181266049 586159384 675293406 375902987 249017388 661919650 414343966 245221239 255765846 961080791 902264505 800264659 56970633 277871644 475481208 323210083 314748857 383507554 859019913 50314114 390424127 117161432 303896209 3085329 789916904 196400298 603681491 938511973 331310548 580123791 515276421 496448657 579610155 645530449 652591686 222490630 728892031 579099208 287256915 501198314 872890654 337919821 347489255 332345726 83578406 866849974 519605746 462909690 193798827 266890208 727364820 497526129 986669314 918779196 30727074 43889475 837639389 842180501 628572168 769319946 373935852 351827427 846673613 721109294 622880955 744131374 135947245 101815687 352634853 529278467 181719848 915939953 601608622 649756461 745730995 780339787 521548182 367636430 202192193 444298196 978813268 415260228 421683070 441459922 969566647 76251361 165301147 12915739 669123230 285822746 206866056 570021435 688322535 187863063 487350872 26821311 203827936 744337385 918055207 307979856 886336552 824556926 57344304 134532907 403299021 835330995 450859906 913590389 728725536 916910031 559161087 929565303 584008493 457550294 754458643 707817743 716216916 513720083 474487859 414649463 200849435 429667517 985235999 187386118 110314919 491147590 165791244 954385948 635668330 548458803 13755176 926484148 26308092 190052473 289425925 374078611 801464724 679458409 699781420 972655112 391478838 463365758 16855015 694055037 85221642 309413263 547267803 461843191 369090367 752464096 136143716 324023951 656272843 627628153 41655700 633099702 936191531 458535957 872631850 644219493 640295883 666796443 876037596 605693668 108111240 861057065 268325967 958260474 340298023 8765735 520077266 152649212 654043264 823002978 501956800 412791068 764222269 188287084 891023619 988352305 902943980 253635676 623273164 253756900 771724413 736741726 513891860 671691330 418065602 959404801 317581323 548814820 346107570 777439648 525720320 928064293 216974887 770757299 201656707 395725557 168971537 309559317 969565575 174881514 249572507 15311589 876573728 910309168 210038105 248831470 167923613 193991159 334225133 494499610 775814534 488439757 982944736 101511370 214379963 422955383 542679617 736237918 934907835 505669577 954887679 645865074 650610481 714071119 95363074 69918376 832265801 109833703 315722933 755101188 529694193 502317231 262520701 802923563 669868604 99939548 364733443 778250879 102376571 503286929 90112167 947768041 459406082 245433553 385510883 847794653 78600660 785816115 728229360 823398783 401534940 983713420 586462606 620737785 453987055 241904731 212525177 413627096 283842820 225935990 455535930 693224741 889421618 30089902 658441621 822336579 621249579 545615343 48697519 89024179 496811215 545705323 550996543 522593235 23106107 945787773 706032493 242831401 953066003 772847010 6073705 503402384 28142999 285917379 642501062 226194950 927386517 844927274 25547760 736914893 115915467 184277901 158436996 470691879 540037821 505497017 705878057 446426258 424228065 292247601 684861904 713714209 817647521 861006304 131995290 758396788 819896019 588285599 303440634 941624394 499467357 881123150 216860789 371635451 360666481 347343519 555533456 749423508 516787063 680488504 991820338 394599616 919029794 290987777 628141737 154655936 26856180 970376300 919031982 65420823 422477942 167176586 631290582 910377105 877191485 453523790 631360795 924509595 183271954 591148996 468530861 622443253 641221830 462785210 945267427 663593013 383436639 738215313 253181125 615023520 874694332 610554068 26470243 303450389 601711778 661419842 131582358 369717838 963585861 532445717 684295109 104400804 743966552 391179860 535335413 131775205 671935784 658161157 678080774 34372461 187668249 280218201 282632334 615400821 680079318 174915458 412036230 681137385 8999550 491333855 417204323 938259769 224776307 765760867 631778557 766802238 308111603 860309801 649919654 750761804 819481799 413774107 484974160 419115956 709218163 979188787 587154598 443091170 966163052 916431194 656957911 877397122 528654620 362815846 962127760 939155001 510897673 936910338 320383360 495768290 283045536 828986514 970148549 939504478 131887371 459502747 542289813 972705173 902988313 744532789 88690997 905883946 468215380 793614320 113073503 449699863 253087004 456112870 965652554 237401065 825938864 419023770 986760646 936374774 291988315 184517116 384491927 703279331 708309579 901899315 789040815 337784252 416364574 634506467 213140735 847106273 35200761 439689593 621551959 117077242 6621845 114836876 421721674 630095692 189738055 186200161 987338734 434274630 447956167 727252889 459621831 787077975 428796674 561578185 309337760 639172458 586948157 763756212 385451680 655850346 951708522 915880093 495600608 465425411 949604351 912337539 324310216 895950337 379195164 560182797 276906929 918247362 788728 35476108 776883138 445831435 666274726 651233112 164673402 901376347 100861373 118232767 888378536 734970865 860929425 244334833 37616629 708423709 442167046 440324710 922183438 587420375 558934523 899481400 599008004 209907429 788952269 841516025 883191379 7402684 285668140 139548486 283613970 693370824 195768211 919012698 582156982 422750178 525790915 408474024 412589438 439804861 726300687 229298370 808478936 361162886 790072701 349185153 689756005 757110150 172455380 260118704 225998965 814459323 886868460 868692739 82202969 589564303 636644916 624307124 897256554 896439253 788243536 288099096 536844998 73007185 168708959 551782736 935319976 220586116 856914452 16533015 107964275 818854928 521516896 343300227 805938038 513863352 452467342 497217325 857611621 56651818 585419849 544689676 975736378 101590267 974029003 637913120 234067269 16839276 274873562 99628260 698205385 912590602 671824092 426290600 4482351 828604783 183795336 357676948 314549523 594456964 316719802 980479434 671769324 195667949 116094605 678809355 393123606 50857979 714127823 357171749 571577546 848155714 538013429 225588202 268196662 484753539 570546951 154216464 812665079 957322707 814830368 797058085 185828970 686043036 93562006 817379485 13042439 94252927 536231946 400082451 909201686 449018167 438904141 129297062 969786338 991019320 608389880 430900583 868061321 786105509 856659628 637222660 371929034 31039195 318684697 365232591 615126091 997135126 830202271 567206824 907050476 413581775 663482003 381148001 270276894 63510966 355511566 750536396 10073658 834177636 116674622 146980579 946424559 962245676 747717714 545873152 572118698 499520262 761851117 960335823 719579786 91300240 56325892 159909736 882028261 92537580 502481813 638602865 664907174 352243224 443791013 518206946 226442985 978639564 901706552 309053399 669382275 84559360 904391804 909469773 306263496 998000497 610673795 77883710 181162560 703061549 67945639 64304488 57992098 253680081 129259240 87278311 747221349 556839757 218594963 767462119 875986207 310519140 82467818 195585654 496409486 994502753 713459415 57134056 659857058 470512080 628247263 772763428 509382817 809331235 26362509 936297329 75905927 394744587 228358228 889926123 213533940 181267792 360017903 501565073 370925731 800705467 522436834 707288673 345526476 295927003 377510871 560480547 822206342 234151083 586535201 843039555 975948489 202029432 109694997 422380658 718896151 677144857 290188281 327054763 653884165 667814384 381793292 673664413 647530613 992072208 217207535 727026913 120150015 618486096 643627655 707491883 772839016 524804648 622505080 112031563 118246772 803483459 729153130 44126813 115855113 170061991 102410241 139876291 771238019 218145004 552057099 333313050 496574159 572898539 615711181 289532159 639861350 337959086 416843005 490728251 502504864 862640319 292839917 177449132 859957469 818706227 613378179 607635381 75172491 137868484 925290476 573238293 510223591 448551907 711461556 359616486 894193285 95521360 41160386 274266267 511146021 701569011 163516726 39457115 611124321 864951880 462427345 931765598 239534594 832485221 298633584 286341570 835521692 577922325 1079212 122256801 786320131 598921384 487070210 434352638 585355382 103946819 766659002 482103462 780021943 600186413 411035983 575406984 932674270 133756687 335162369 361262472 327326461 716892577 842387622 181706483 721970063 966042744 387782968 977508007 905356663 761228394 683084802 101617213 54203549 820767284 183841189 948377881 905689261 872071330 429327932 716162184 297411941 364705225 11337608 98870862 752061392 462257286 191298729 829013876 496173473 602688872 219209194 362101859 736043002 335653925 502170874 74873135 768398123 665989008 132737911 472089881 170789957 76554566 690911527 68034162 771164079 300671048 273123894 748053667 35455279 214307364 2676290 538954975 182755933 816171071 432300612 215064380 575475716 568889569 79277141 247240071 672739038 613509331 82644620 401441635 945761264 703342195 323479874 243326269 222572447 716999692 493116284 899301703 170158969 364408983 427654572 13173518 22268023 909609588 847770034 808217486 927419723 85004169 563605141 351962489 326396553 36227650 378817308 441363201 786419478 915608931 845884313 912854233 980393808 732547628 659158716 89269802 354287467 432020228 207620989 854177512 439683756 638674181 272923455 805941235 739446943 376827413 159324922 777978820 110596506 531105825 466298509 6119236 171906946 767360290 498545466 894165822 159909542 250179817 508571375 310021436 874242902 471939313 364156105 657017720 881525875 88626869 303308303 2358954 343787520 143902295 575136916 328680624 283892709 679814527 300716344 724276952 519633578 867268785 198834318 327274369 585211948 218448960 745258526 685827271 989849242 272944811 96591443 524966099 637100303 606169261 460321438 481063733 638582724 540653077 591859030 60697150 567822490 517705412 849236222 905343659 963433455 422805483 661552465 758142804 189016489 613075188 114841813 12534529 480837440 432433729 809583629 349103144 646512147 294617111 195643413 833903213 890556996 651769101 397261968 104310878 323102303 89132646 321716310 968776320 733468029 339018145 478119947 737457308 858828134 261903012 942352224 587570216 181808585 583117503 627312146 736989563 124654087 431902631 334040535 886675663 523605389 89750717 329814129 123615544 958657344 244983719 451804791 389355071 688508716 445832861 419574522 356132266 278887687 283747585 631198234 546470409 268986161 744321603 422596620 291359766 845912418 776463776 609776246 609323439 394126015 930285614 333897291 951849000 729755248 332285235 801997514 231124005 780893614 390790018 265602450 225520774 655378670 854470374 787396217 658615083 419434251 661360763 468710650 55206366 963243982 406422020 88154176 263066583 51299767 792932877 683764613 371055208 642684008 803804525 344732618 179489589 60835393 363825866 258783177 992422998 774344233 191367261 428476233 226134429 184665317 561990332 365817110 893540237 339109976 937207322 967238090 423858271 959832490 221530951 481417145 996164766 263831776 811416449 756757110 804596472 295245344 914612528 65003214 169997838 832245058 197182889 620449664 711607253 585732483 877326638 417208506 635187892 667837371 883495476 246015980 908014616 280998830 121230442 613128271 507461409 755276272 26262594 312139931 119337968 346487160 665481287 924866151 740578961 933280620 454304082 950097207 315773458 472408523 989819044 166430966 236467880 677076184 879326334 973082680 360894825 170670791 439720040 413438194 521104848 941718110 46499511 251369008 258848097 306959672 305651694 157938678 127821693 796925596 690997897 216796950 417356220 260908639 102905558 121939502 481275909 747190022 220905637 207867597 148987442 617488473 649654147 380711843 748788529 847728669 548212805 451309769 886886513 2792635 103354943 694310447 199663035 55746289 383768861 78991245 794051217 739186581 86480103 56224977 11471319 589942221 770363177 306679503 677380062 304758295 211515196 418203212 984271294 483723403 199999980 200560380 976480303 756487121 844859557 523520312 651828326 147910468 990192229 83235929 726728722 815020458 897842858 70272644 889884796 283908831 816672356 711703941 487799641 912902086 832865391 921934323 328179565 399476696 591181847 653930772 17250315 184911213 355405294 628144475 392301558 100664618 466005668 240380296 581720695 22862374 16065219 848031807 994673303 104409181 162546876 505144142 739381896 592099810 28163477 490806597 464300212 94677984 531651030 939558114 367525163 397043895 943402763 85784940 237570958 609457439 901529998 743770565 735996373 5534709 399064699 10291441 280953434 503061266 946727903 160034718 261809420 188878812 15319120 387808459 950099631 677330229 483670315 436421000 853064321 934434849 605085369 780025525 449137925 784742479 37835385 902390774 300485170 806881938 832267743 181974336 833351746 482856540 909408500 492260010 344349726 158550275 388904649 449722464 148577565 71664634 466419563 772715548 912562769 157846269 441963291 540165671 831257769 112193413 26133139 300583062 28246400 625610894 721961761 327763352 708128918 208199540 973240624 907310939 323031001 619444482 269761143 259341520 375471999 738698172 399002157 38559851 241835922 758880723 693677611 166802469 136137369 81922730 40575816 920567323 617859786 551160322 905142321 926646166 162917273 615715313 970431818 518350224 165286123 925517375 580598404 184848449 487412902 277769914 148013268 385219360 517527815 705151596 404687839 55680032 312511805 14471917 839296010 444489625 944920961 200930054 483204958 552253641 555618740 903489279 728467366 529899593 263680070 671666594 344716280 233371469 558220691 336905269 599097863 132557856 729390507 455248286 658840642 132749825 803399210 669823794 420023108 641655974 878350651 171238220 375325083 167739003 956528432 71814912 102167636 369362125 982110698 745766056 574159988 243057448 850836895 647673227 109200545 293259595 155512550 738276020 509328420 711019541 618137903 105310634 42496860 187539127 532179128 236601189 69781447 76872791 903851571 700175553 34369333 202129248 968948753 483496796 407347263 584309982 276985990 872306277 538884063 389030494 730282378 241584817 434796121 456581736 294774403 903258923 50791306 589632793 514013341 70930818 295430958 179356811 34182006 712673762 740481801 997012546 28864165 841664776 749059614 112524466 661310005 457892073 402851224 32225791 508116816 251526397 193354050 424692483 78610833 966832590 826251114 145415913 558234558 142618683 250360982 654190086 458486808 380012748 898504010 863030141 636088939 660441192 485140776 560827070 228502042 459113864 914736275 572475191 911861283 574848032 647811800 824088794 682839522 61432721 617275952 697055943 274867634 267420825 399963569 109870651 625709241 737429964 635382853 278203574 801592865 620469183 509990516 488484142 754446740 217418862 972906877 102374963 229087495 330274290 37217270 766464506 395650762 705052514 682844438 862385241 227289761 873162747 268067256 700255634 561718141 838583058 928872494 600400815 607281530 246232120 541406651 166537247 131628906 665313788 467701106 853841374 446494161 374385114 123130467 822710612 94383376 551725234 568799942 235217867 621693183 660544580 358482573 859900784 482188813 162003204 646131004 128540862 791354631 746835873 634909101 570413420 582542087 955519970 493204840 306897160 476770988 435501363 305545766 295563563 711508875 193563700 607961121 586390413 927186236 280830080 550163175 782211641 164509639 621564647 582016730 765368796 578803547 728583243 334031186 26499359 721607644 692414353 45245434 996428273 112834349 217238376 793299434 597980420 626080763 535543231 111218028 398822319 234367687 865058509 254850775 918073720 868707674 133045815 584257205 690518967 430924909 295880667 373373512 947217756 663221961 720950266 272369819 834185651 585684680 481408000 61638718 10860195 16609297 445615579 550136952 178847697 29206564 484093372 596121012 643650885 614622060 120546121 891034159 851043262 98836050 798006227 214832345 180433152 726487411 493062135 256785949 971789599 456941838 688330075 38444306 172430235 899004138 266944015 125969742 313408916 648905377 632000549 272781053 85507700 221770901 911370752 930192561 810332095 854742693 494788368 820388133 244292686 995747027 160528985 866366919 861917478 883166005 193420410 345373448 188151871 888570222 117677842 812875220 904703913 641633771 170556214 459502385 913351755 378432051 945625736 907976010 560873915 545521571 911560934 329725936 951948411 648080082 758384508 604249092 215627362 544933638 317755374 704664381 764064235 896027805 683197777 61445288 996424530 622078908 16592998 72139355 401682479 782166989 565282931 776294432 375215045 716636189 920147253 10033851 905493600 353420326 801830552 259025835 352084062 577117062 770880317 98684256 217707778 187745346 502943227 526046688 365493759 688641028 199366380 547572671 881583826 483303992 56290219 290257548 469797913 86753813 325731898 388436565 491471265 58785160 694700379 352729802 826724826 741643086 631804342 462589746 909665803 39598224 926762586 393972051 773886941 951685688 529370263 45790906 261168066 412700262 198575632 176022076 12644559 25623594 928899377 326481475 756086163 23758058 295980457 245874060 527726492 669984170 920115354 542773214 405092195 263895409 357116678 721954669 381399935 231262504 332985827 22790670 669650356 273501020 283962326 195474532 297129076 476645628 513232598 916477202 705161181 632757177 772990878 683227346 839077067 200848763 527895186 849754453 713504154 953694961 594361561 912625412 375344021 476853690 34944725 366150927 230419938 343153159 386933439 425635940 724722433 967641091 690069342 51309793 129048162 286409036 698961012 555578280 88703468 210383590 653628786 276214516 847994492 78484368 65142314 267588959 313573006 321067499 753501723 470491920 735720833 706344426 697706225 203971063 861931862 289569025 481517983 389705976 664773831 714774287 912646090 548484416 684177657 259994427 759051885 871210494 598487709 709143868 473827710 87016750 159297931 338081229 853024789 42875678 139561668 316288465 649522796 911446475 564030056 646250692 451577829 991360116 767659643 516096877 30756988 225697177 192888819 400312518 697974999 639461766 36678355 223333379 525083629 418026495 308714021 809496354 544637145 587852622 718656359 663802433 270583238 255022496 660242912 520163636 627674910 679570100 338103699 579880666 399812766 408011007 109048430 963230375 832277728 543718441 728868410 650806442 505705632 700312463 251577503 536081825 939264961 432160596 146327520 61018669 551050995 509561036 839666303 31287458 755803102 719851157 877010867 875972083 257138420 101731494 439738959 677076851 371080706 134074847 265889248 799757741 418849687 25919588 624315274 204928361 570319498 826548822 738558930 236317599 99090485 368750934 847106145 18115470 59366862 746201227 30653863 820783594 69256110 755789466 19520479 772742620 623745132 325225393 70534900 236171206 844676507 189817385 615645181 345400542 351852098 578496579 54805939 213517170 704158569 899406801 76178247 195879506 36104517 774178049 119667325 686001221 13141704 4328303 299717296 531882179 718957151 938500906 47096914 636553780 709721611 521749405 698539244 660582678 552324364 316509207 541675360 309720265 349748813 986279500 10403533 354896604 194814694 850266228 979170309 304901952 505474596 963210626 835557406 826344666 137095793 316530194 15838825 239211854 760652172 262850467 212099779 799801411 924730048 325172945 106574473 927821923 722796949 51295617 661846387 189043713 493189310 657813041 907296574 330566396 653097179 992686766 210812838 421160926 382881007 849112174 201714680 633095019 301385687 651420926 905218359 564549440 489228540 547118854 487494915 178769229 864769345 652231363 102020347 406702935 744093329 928204268 650886903 105342484 193231404 378350103 584055967 605946355 961170304 493082838 769105064 664893877 995254105 6598727 974410273 682493623 396244469 733062687 189413154 611574130 281083422 397586972 458070021 192056123 725554887 688367553 652256246 50770441 688740833 108666985 358804558 648539864 581415924 344626238 69427066 952224315 265852610 832377345 249770426 933115606 85284800 181549357 18874898 762775268 86678946 544026907 753259165 747937739 130859797 250016111 763535989 251119888 852967520 539744743 320125118 848701364 426055178 882416476 415717349 794200945 418622498 690155569 518766182 721242616 492743224 65098034 827471067 423632190 443728758 362971595 449916471 220292874 263722260 527209356 968150264 244216400 310869154 136651714 831086990 958012589 931871870 613963577 554614212 823930669 953851845 158719118 356755004 771338811 236114522 740230047 142933965 9608906 22046378 102729643 883020521 941301669 841688278 158538424 539956302 99895520 434142579 913574065 791252244 266816519 221092599 445142869 139855073 246684260 753985946 811343880 928019706 629830987 282978504 266189717 780045411 428571310 879865795 504345462 703086418 262171673 594868630 689130322 684967728 43779011 496379895 761806223 425956381 182607953 332772386 565080458 534660882 955872060 764312951 766239714 762696085 957323603 761565760 836067096 462071755 583552893 400892219 954533935 715179743 635805245 3118071 435814630 261836137 941556716 43335134 493717792 3939274 379511857 585002126 242527963 158608502 769706981 768117360 793574695 398224296 68038965 832928229 690789449 576766590 337611028 483091225 166542865 49850254 978388990 679506568 108156142 73090428 589643702 367271546 377083796 977240969 297035169 767272851 538922113 774367194 242111473 100414962 4875551 792990293 486822809 514825274 878513629 276548273 398642533 350145035 714369698 74959043 970129589 333060135 901297097 339655531 855474109 504408518 357060492 410665875 548892808 229947203 129270233 384928217 588930557 56387045 820046774 689022308 229653821 99338673 890985097 832823270 384245154 771465048 420233743 228334443 384894674 616159560 129206006 250833188 62691883 884430533 648921644 441732381 414854991 494563861 285100013 292922813 729106305 462448724 955058476 69185113 311342550 476527972 518827387 890838208 191047741 584968053 15628538 995413716 943297185 662001934 994481017 769823628 295051174 81041545 486505444 704463617 686580306 845967777 498644998 338099999 723183559