4000
360102024 962719514 646811930 279331594 443284785 178986397 79985246 901129549 842371486 808577721 660473076 882275460 287295720 205622882 137122925 456795250 959137313 471396722 863652361 64475539 886847058 437383299 100855093 905492858 477754636 741064731 612238838 979699789 370731685 992355662 4165940 718112060 619690607 288514202 472663354 272030425 703068748 136034408 958664537 39693101 390734865 334452320 118852214 823977720 929438522 899054602 520103501 627371749 321783071 932756177 428218121 742996795 139192191 306121588 53525249 425689587 495166000 982094911 448756485 823901115 629084014 666155034 49393575 265671128 456620205 719125872 875877528 310694675 709403048 60929723 869819451 120660538 573552014 578632996 306835904 36315873 887174029 840209659 617067793 797555531 683435627 857159657 638803353 963843982 183609163 405359542 7497083 975764225 399959471 477320075 564549535 860402046 44413335 362939139 957887059 689493745 399396104 687975985 358388065 571789679 294892529 525771523 823141183 235049407 897291211 860997525 995775194 987256982 502205175 943707097 580448939 613237658 26133532 62609856 496564523 802905686 737843614 552816242 131480769 94498827 125069788 535129217 2100018 555557173 76267299 558022416 722019854 982621394 196632771 507946406 343551321 48116959 899145503 862083876 936086351 156964758 99340390 602685994 205886542 467996193 477066380 52134805 358235425 252360908 376392794 638072911 308624478 838980554 219663690 510175883 127165329 96565127 609957644 150607985 50241106 861829722 289310936 295172221 172895982 675291319 811959803 421043131 361408145 707191855 404829394 662303087 201212013 188393018 249902357 190568010 512615038 258151176 606819477 772195491 778144530 319983433 11826481 478435721 7955431 93151360 478853431 932099780 111801242 962046252 726369174 76002787 59706551 905250519 700304185 742117940 930605981 572269644 894128354 780841922 617199836 221628743 76776537 956410412 126709922 682145412 364069280 590846822 905772351 563359737 422613558 502694518 680134891 621118836 230343977 842357491 911879213 500778582 745155664 106145638 18207948 568205588 155184637 406730522 735580561 850669255 534902680 547814393 380995590 32573609 682119694 586369499 195728499 155757840 608001776 902331855 814954099 68225604 551214142 978608405 972601442 848774576 124118430 63384129 866833127 314643636 342337949 744687637 735848038 196632691 25918876 624335617 442595743 287689473 252806382 17557470 730472246 251324857 870343763 913795657 867110716 827404756 541166230 929620430 849751258 876208134 927802669 623480200 376897758 419821209 659254408 322785300 867519781 689833779 323842239 745538454 727517712 226936202 851980359 833290200 687176669 605749063 286498488 909148841 276022730 191838295 977030893 551773812 682006969 156825009 592414971 827671954 95333913 768858173 320846708 152919185 38031088 513275905 301201994 663466774 192420833 100621088 303839794 947438920 644077851 446726300 302619323 744850250 62367005 565802151 324505570 898310042 443184178 786929958 965085738 517353644 471315635 232857334 295818925 846211142 630879272 730140391 630688480 237092217 555867738 620410481 956861998 160127584 5761529 74758072 223685218 823454755 22223532 574517158 515322739 106954407 232141503 386447955 318974814 759177503 427201263 641457388 776414052 365429506 150443122 350696556 93290877 318597110 220285097 86424046 353570531 851547291 507035835 421693749 863511208 180216600 798658914 202675844 197104827 112303750 275224833 814901376 514544007 400037700 817272410 516617725 14060530 790747734 611856326 701625443 434424547 608331219 792039785 703237273 364435693 714289369 213797288 473853106 806179621 558080223 53092832 240277529 197036195 468028925 289812883 946235983 198436441 834981701 682649454 519583710 384507348 729087880 112436641 765332761 265420455 662664605 828518636 620142179 792665775 324209041 585916201 160807244 326539288 125868105 922070971 533022549 885475415 300734591 996796655 71640250 826829947 744602011 325720533 858441047 668011416 845060622 69044310 753234230 870088655 73785586 148659955 960680170 431412047 982261134 150943377 933491932 30927161 845529187 394638486 424240304 567601034 22585481 136160878 838669984 311385192 648207366 383523752 995726204 736765154 528290441 603096830 352720616 122346865 3687462 122239303 631045434 794647102 366892966 117542079 902064732 150034638 402135571 588380000 596706321 480396703 800829281 434558691 980431878 316717859 858297162 17850465 739085999 62914868 914581831 357501278 910921428 246195333 175676129 534667126 35418810 490840182 266112530 692210473 312678413 458595227 268781879 127439730 817914535 909463801 449517347 488349368 826450856 757353290 174591332 602017353 938978099 893844852 990000730 40239188 700607597 189237364 613027015 484829100 407617703 415636285 183794563 144973211 169585744 509539202 493977178 24329754 614615252 265017819 279399471 799225295 993849335 507996504 658853697 196447267 203546201 47873200 948207528 122270210 266657226 496024327 422118688 488050914 916598915 777721801 321634388 404552074 959078835 541138055 277036929 390695652 146592187 641741323 85856421 237344833 971919901 357045170 825519631 578515819 798648620 894791876 67305531 709543790 486660984 552939476 206237347 629767038 444587319 734215563 420125542 747108880 497379953 838842861 755630283 206178667 784213954 109858920 341614663 171896243 41142451 335862642 698460895 638695647 210734379 654182130 181506767 59709269 479753551 535350048 179729529 564101580 203911796 977789793 933041708 375144562 585081904 381627549 70994411 451966836 195076105 561644126 931804527 84018384 843305526 965207911 865668055 645930372 439991968 67782689 29965162 405268643 215177923 224305552 224929188 769081177 273798870 836698409 193088529 311479985 962315842 73530933 971451245 424360768 522663113 271309072 687748718 341771717 371416107 916584768 178512146 48607531 887986016 776925783 75712724 638415513 173586922 911032351 330039189 222492651 29785807 536452139 707239222 159088237 471183364 334669777 947535876 813253523 572506825 743596217 150400498 665070428 685582459 602418509 777095981 913029402 48742300 353058624 100575149 64146925 846554276 786448682 791590944 624813421 478881238 744079970 410130738 771558050 44009521 49259240 554498944 358480765 586799624 91838128 676030978 827325261 99875247 383686217 346438047 324847700 904834139 156792556 109873613 628153860 326742993 770039346 23491139 998139085 220297288 696527049 397277274 720002532 206941353 448406178 586014723 696986894 90092065 237438463 81937848 375458635 476275891 859061109 387965340 589466063 994261129 584062481 894358796 354384178 948872513 230745000 814481333 898647982 410572254 236095169 351300551 703672081 735968493 410119906 643397117 795524584 510040767 318235848 497449069 863540614 511814915 718745869 611127077 45849396 734974924 378275998 687721909 461758905 755673062 759133121 129276136 602661649 179109150 739345932 593493109 672835855 384234098 738048043 73501769 89796526 276576461 310809263 694216738 865210709 978744551 168522520 821571612 692200493 564920814 315164316 42320939 96628106 499586462 819482969 845951489 792562372 826835758 577217446 75713283 577993660 281854648 91866550 393694260 641784607 65462298 127251940 265081233 531623518 37436723 482393520 343813383 83124884 105738309 118988833 637556619 136886816 334917226 320576029 628749239 595277608 787192685 813328089 679516938 154957589 757736359 458063433 331608082 956428356 59906565 253016615 578842774 657996746 994032392 160371342 241083755 625362437 430010737 794346923 108868925 164338930 342350065 302794772 434956327 315538473 651589042 961245958 384013365 62348131 470271957 543722500 615448212 932874683 71750224 527832077 759197234 764358628 275221602 892981706 576556607 279910050 665741453 419852245 659372231 248597878 161208511 3932591 764746347 746690106 637303547 22712166 938968306 313916992 236588984 446179353 504333002 779435108 451164823 595282415 451452514 562972414 566089212 492515713 87496813 613341269 359331511 929905436 284726405 948258544 36084422 781814305 228760514 300124202 395148598 125509720 364051063 81392157 230454871 276620106 47374621 661013882 547174736 752909212 892198415 488569076 150567691 715224810 881579271 504343468 734243287 536949453 251707023 745999588 144929760 92712871 77665155 596932610 21710103 750130135 543873343 274483339 154566761 816549888 401494064 232883251 372039786 907449296 474304573 76410239 787728459 638359061 655930777 103589516 38273151 581569249 635838393 546155442 198803791 258173990 99938779 645588639 259360167 736429066 796064833 738667993 663666319 400868777 630420518 391506385 634318210 292593618 223136827 569992794 314963921 191485776 406800371 750804429 954708977 134436250 907038603 646146564 18667639 152759330 947566347 972343275 893952458 43904126 900999630 840503945 634704455 81016240 148645357 482937640 509479882 67778104 720687761 155487107 19352315 474993940 716013927 454401221 553293494 70734499 624095318 101483080 57411315 663909630 846375679 903801570 262258321 432567201 28880343 667071716 270455766 908362068 909968483 454369429 599059242 959133648 485376867 141500977 402822834 281060686 363541884 58271151 121288631 490000728 442350244 357026148 655647420 803898857 284228260 936867938 327045295 672712705 769265398 96080812 441174905 165806187 632840832 825292884 533290864 162368097 720105505 923657592 848993729 802795857 597989757 405355382 955749621 805589010 800558438 326597440 701324110 653405872 43334533 199539368 141517789 213556920 590485295 743728422 192059613 284954845 973224361 697154556 882942363 17820734 296018214 239405208 243117932 930655065 68437443 60768828 322871739 816569141 158098100 40818789 332568182 102120465 838961989 354544573 149755422 84244660 674868987 12049190 614329326 777333794 31805692 893494787 627574933 521303638 341125921 122411943 494298696 339348887 111964439 912909181 163984992 564346506 536024193 293474777 408013039 969087993 960332866 544422087 803740841 845191608 654764488 812178080 646040534 276135487 119405566 360856957 406864480 898185824 476749205 336066002 187332630 254780029 163397267 144666476 953059875 435061472 364189436 73345321 217057336 38098180 518094468 145744411 267969923 228762073 24350786 386407565 368222847 55420415 455425421 96066498 581790306 705769749 908795035 840722874 33182119 89128003 996814467 809544808 301412270 516748045 5649256 911560155 119405512 943541934 258728591 868027484 213094501 254458079 587062723 446068306 859303795 376240 581090162 287947997 509022947 797388519 822451464 223136753 131024803 924361437 722372518 320950397 140640107 164721051 425908078 293680537 154532897 286804757 64485393 887066752 264464626 339934229 131120600 700995389 579823664 910776250 893795718 217991423 367781961 946102836 589187570 455697738 433728365 214687249 286920182 49922535 490249248 827269527 72319510 147467199 642453682 876252877 235323691 308857171 980346741 819958536 434678931 305504387 980290271 940476764 547095777 551506954 617217704 563359804 266912037 23895740 873963281 533691523 877904014 318914328 744206521 212648458 726429952 904738437 415923439 660411531 176638452 984668204 323649076 334438399 671374468 593922405 517708772 382551255 702299918 791445410 478157443 374240956 381264524 572941698 948098379 934989155 197605984 184143083 380510458 892764416 808099183 384453074 765722907 297410574 672817158 903070880 154824716 350031199 167155590 32838540 530920130 726533039 421199617 949514200 88648764 549519023 403952890 246570304 794568222 320974938 787637122 263653871 335516097 566541293 33077373 785913515 357792985 725116987 887445145 830668784 129588986 739477992 485600081 639373346 624695207 805005032 610811270 241074252 602066787 753931413 353602666 222996657 981227165 362766143 332836675 704813259 537624574 897798579 594963548 923565660 504391610 634018213 325583390 753708304 608214646 880104991 798638782 147072898 313718106 294008087 118315436 938874173 285262202 604158377 496486086 33381954 793973190 26276678 611441467 844598650 612377236 302521478 461023084 333518658 921104058 321945404 510735478 206675527 144837641 200880759 824632291 168588556 785195531 835918890 228327955 721221726 181971153 311798739 342298680 567653201 992670778 559319996 13582640 635629759 398201556 596139984 128870933 509287631 886122637 571801154 795872441 923600642 507256406 151541179 303255908 602424303 269901858 25589766 872425411 661733855 932703899 676342812 226869907 53439900 218369008 350318492 341942998 982740054 935156226 311348939 119797431 655079205 34342122 964942857 169269868 2423387 111754064 915475759 547769841 140531642 295783938 819778870 923911358 970074573 161981747 826714395 664466567 950700329 586481527 958240063 917959803 928437989 717672139 286179018 22042404 386571847 514098401 527382559 829311801 169081387 244861785 243267135 24780685 452842128 271936663 463392154 707413126 394905523 533793649 781150200 691660716 727138159 948889666 638240722 466219326 825155693 408104988 971383145 159079857 763731483 961819607 677139569 592123288 641557920 776149079 673863231 885309867 92838379 548603221 343624311 399917330 500552233 387307103 604079239 448832717 884132283 455234526 649276324 285536522 254615920 859432753 727022463 346964892 542499432 986858298 469991742 324251732 878036206 494211551 618701538 612152840 335328362 356776899 548393624 436410084 724755702 408337761 381345021 877432115 936665317 864984979 72742794 458872888 277847040 735934922 479317944 887294594 801989064 578782011 311071738 788955564 851825455 292876281 785285704 54798755 309759660 441060775 65481935 564803179 657303021 157828709 418284930 131871043 135361978 808981601 12274658 905980165 824649296 622790328 821910220 756411759 751522397 185207925 789169052 912032967 476790029 483883815 732010795 564864927 823720124 320460 35886209 830923284 434321051 594217119 427257718 452797535 787883289 481061450 949166480 955893100 57020675 995404387 578304946 785402350 771474435 943908303 914448073 588529879 30691244 341280701 130189732 401013101 972872486 641805994 433847444 157733343 396709521 484174842 964013386 887632630 563565706 25407899 735702074 781727835 586973506 558400920 888591393 674054485 702395715 517856437 104446027 152988503 995513405 783811444 286511466 819567379 949321514 383294919 127852375 11877049 80941337 99848671 361835233 51383752 111538046 561931213 201071739 199063105 268866212 629248560 168059290 468882648 589615689 73303080 983139386 321053277 925006108 769097158 416438872 765253338 369810396 442619588 259626256 143952964 829508746 285602871 174614540 503128799 669485064 69056168 678563928 51854752 603039768 340267453 182193719 760405245 149840241 517818297 707768018 231989318 580332669 920748398 133866002 943963222 324375031 652246975 379268672 313235289 905435501 767981731 916091278 624892218 247612671 945763145 377698313 869321844 333313959 306874426 589115460 541613587 75251669 883662138 806149048 57258516 899385414 285905786 93960015 886545014 865200854 547040197 581336026 951307831 224028041 30077685 56366120 866000291 42319738 696196858 951338136 738197134 84592661 603568261 442506300 404797176 953765078 74901280 113141231 148608298 370151680 54172603 262014241 613495745 5069380 689317264 401075306 515187618 475179465 50896033 246745956 734932555 514489962 394854088 444327920 644896883 12945090 159563441 225432064 160227851 954220904 118197988 252001359 864752036 627116969 667536138 810710027 712820732 634343231 375580412 134788127 369986080 370689651 798694285 312003274 82129921 207489170 45984173 257429493 165410625 590846354 809468991 701741031 196934606 478396955 695494197 925751476 293889475 962638049 454615914 644792680 656195106 803943086 990627878 72351101 859370358 177508533 124785922 358394179 578322849 581995695 27421777 503995187 738702789 874792922 44670848 518083752 836806449 191282925 860368164 992250759 520071913 851065661 289964675 591463268 322947394 92156077 652505661 693280377 245410843 904148910 737545952 651652113 279660251 290933313 583965401 142929853 72392570 381795953 984281077 966572064 297457095 379007569 376934959 70037626 829772388 699670479 666600619 566876582 94529520 773857061 334034732 65436943 261862851 289658984 813043818 696615223 608986861 305652276 117127566 528591241 841915158 420257560 978916708 662115119 447748702 759074786 26213399 652034510 698209018 205811709 7760042 523643170 826104036 133891799 812247663 229605761 287275884 204401910 932149313 211146399 414599360 293174874 427441790 956660644 783544743 776951479 669146994 227050173 84053090 503249401 152005583 522867356 961539662 611931523 270345012 275203930 81946474 422660514 419365842 278415864 305318794 383635944 696930683 260301656 858677576 157030779 801879281 864290869 575947185 986719100 325523730 815808841 513784820 156894969 992218489 194770259 502955769 473969026 415058695 996380308 603325606 484210742 643387864 647325417 837647270 348314622 593480128 565532828 20344167 48031087 455446270 29755149 941101364 123153981 956397044 215657415 923749208 204248359 839516430 259499722 785606919 10487091 707952737 611381460 201944706 763165374 924258396 388440736 338600107 342132177 895143587 813256935 816292401 740123180 317088844 308102206 373653269 462985133 103113064 617484735 971631515 44457690 202912697 412655795 822358877 910153442 647397619 969685551 635419428 700943257 796443318 242221066 542137093 674716532 16442795 441642756 863011713 985255603 743461304 794979896 374981934 193788652 951206224 665371956 657771503 601717121 905878865 572865248 695867023 67708155 221771105 724332415 144065984 160299470 764713507 947765722 859267263 648376460 580111651 742664024 207526513 737437799 414141980 238819258 408516441 116350396 45501646 134466314 946256609 831748433 829358785 519864686 80456223 488279327 888985453 889936507 223430634 180560135 794558695 815870607 386850180 740299486 512769570 456351133 770098130 942446896 189807955 94121571 457653263 337959972 811681828 318652940 5636205 239444177 723954834 431479636 626951525 791664448 224428431 77378794 234248115 960352994 655927057 350885000 701597575 350791177 336001896 591225773 670896266 506915671 480030255 150829407 483186758 272227064 877063682 72995014 271404128 443728422 175078844 493241173 24520928 957768370 818239096 751951223 226379474 269587684 913755627 167192632 636971822 778324435 670888173 602887410 695011885 881762216 332540641 602346164 851084414 838870182 612257674 733809386 279515613 373145773 372453181 371967708 744861539 884810886 404763409 966195470 107649434 113412958 92942966 445962783 356765008 928617985 43164429 720177732 23482856 505976377 534060226 432510558 65008537 750337605 4621938 879376564 763797608 353331622 282636373 582945042 425357652 786442654 93274033 147588426 952432921 916365105 566043518 773796930 304917481 769736083 313806357 978543347 48603384 341875464 859960108 176405758 544998832 1866224 330021008 120409069 731003085 605107472 637393425 492384163 545315392 794507981 812443112 852173544 776302752 694050532 132839665 700076415 218344381 506848758 957470142 173779756 527177014 594404114 368280822 772998964 488655245 841030130 224404706 446542398 199995970 550306175 829184343 357925621 360069549 189499255 367320705 109503274 79794291 452562004 638434278 71621926 688258469 317434840 885766915 553279762 648269658 936188773 24163263 496946843 832500056 310518457 230051537 817761573 152536841 479473151 238608501 550881626 145016131 73217025 624642290 948542528 14007069 15278711 981050745 111394710 583658698 2124706 624878316 778390555 487134635 508050805 556376386 258577872 445805104 510576307 811112600 705033447 374057581 69937892 545571765 616391600 533459178 96882780 387769696 116199548 14047464 630384038 272926850 606574293 77646863 596699332 433002499 292615220 801393720 385496595 618559955 166678309 693737262 272168753 690296063 244127305 699148166 231903615 700018591 15036835 426070865 146237152 150987344 920394347 73978213 558292417 851872655 932267414 182637176 931747036 664389917 630223732 572370231 152095669 67426508 421443664 401402037 153645234 979046646 417394745 88603634 232044574 45252772 349028799 835435015 288435075 970649699 629028512 850445678 947302523 624679985 523022477 296230922 290200789 459947470 624886010 460092951 951895595 704250618 825145795 910281270 401143109 362458621 530047630 482531715 188353892 945468949 854742230 487094980 97434609 46868970 411598976 393212019 364101212 776738693 129544667 282998491 699959190 529291803 738536551 454501875 68119006 758753638 635591338 917449504 100748116 299805099 425733226 972200052 410761034 520233394 714349003 90695811 451735419 744467127 837550511 127539216 940661949 560897147 533512123 564153231 625853609 427000913 156883528 568196162 709496528 437836374 322609550 986473352 277794920 449899834 444101895 777121743 507233784 102503784 375525787 480015437 853995811 522375154 595026930 431320548 824026038 616512795 944213943 775285263 660585478 775963105 516859897 363949508 360928831 820001931 605848449 875849919 636001613 250871563 59961611 673076243 537933484 984572863 649899483 462952312 963782067 564493624 76536183 458309735 573023858 185555534 803482024 389056314 495167343 756890167 976209199 928776927 421866842 588321384 470208637 261543303 823873039 732884096 715083758 639841077 755374365 606447980 553252394 796699279 664772084 98865178 340534023 825112929 582904371 624052099 376709527 578407984 342415833 816492789 327991694 798530482 152464528 266351327 893117786 918182464 423321972 949776120 835336615 862146277 789613709 817971112 270986797 652431336 276723632 751071067 399891743 990964203 808874015 984760861 741504667 990163286 227068712 133863381 770348710 727073524 458175388 369981691 582705377 480138503 214756526 296361472 989681810 134500623 184094503 381298055 518012719 837116881 741829272 168359224 354939845 249524277 980543510 497646521 923452224 286826820 56988824 701426222 734997274 165528995 107663872 906851326 873848127 46857984 521967383 984764541 277838847 835074068 596085879 458095801 209020068 58803600 871519790 442935754 774973789 300082086 648305006 906981706 684797990 437122741 398811764 9568207 773317878 734720349 939494094 409343892 463756879 108620923 200656068 240882630 830864148 245987085 181241821 100488364 509506943 190972676 495525882 769984369 152912064 377616506 109834841 506938712 778463249 767605155 289726717 831477093 292181589 598562957 219441588 368219207 14343183 692719080 596427481 461404797 382828922 83038456 261933330 884094688 637906968 171244889 802500220 138625019 835106618 227784517 676415263 610877401 124981790 641123023 777193311 392330986 957684111 431693069 202037195 302465489 211695401 11445653 816955607 660352591 675399184 573690180 630485589 507631785 271780592 873799978 972228695 781136124 917238575 271530279 137259574 266525003 360045920 612254030 875944880 888655497 943786391 436214574 162727004 394592830 69155209 666612741 261443760 115028647 866680320 80268538 823145150 452334537 17915771 657333746 40949238 627461542 216164923 299482721 489312969 976722050 463765451 221311192 784930446 501134378 737343582 716728660 888422742 723021068 714889310 208030212 823166089 984812986 96084965 372742040 967518369 434960961 712517461 845912406 407173762 45751816 408431405 311672005 714003508 425528720 989424768 446907723 22191368 234125175 329824036 567047221 847152375 156469271 984378584 242812926 885811801 468261226 168415832 827130838 492512513 434106271 3066294 653135382 296843473 986815426 582106562 519314947 517283845 843177867 539293724 294759368 358329271 218890193 311931314 687550956 181948571 596483426 957109135 187068862 627370131 7745432 621673052 263255450 273544007 902957629 440074157 853750160 196444091 152793133 118490381 313659592 351248441 411922229 872707468 937842162 638212560 362344141 21438481 935198686 627419137 716087195 138493854 363979755 66991528 553643023 512580136 275390703 919764243 194942689 260727976 572183466 210326135 400935002 332019326 975898634 834572970 1803419 712997614 240974946 705399075 867617630 971081467 423691413 189466728 981791972 21333696 188466543 687357649 364676592 266712731 920780305 749767480 760913971 177147239 590865981 235440410 990163801 648725450 759173733 120668701 55434261 90672448 179399731 283554534 833978146 966547237 553030041 613810190 312568120 506718063 58043596 519241756 493269061 890205055 216269398 795663792 259526696 709053316 696053783 818249718 897268711 223860160 201881917 154543119 383486325 888750560 445974352 447937579 477335860 597629638 824154951 771684439 992633394 797379796 48923742 35393792 831016921 571419098 514417450 74806295 692550323 366874005 926952149 650832660 790374543 907712313 484547549 170828469 607637892 302549740 599187741 501492397 38428377 516071749 459777272 936393624 823144326 38540272 765189791 5898940 468578651 951348583 292744393 269567081 530939346 236397146 527138787 447927646 796618239 130387839 709077035 257619541 807509053 91645162 902077333 499819716 967396095 774744340 921138479 872462389 151992029 211498537 945463259 712415036 700558344 876451286 926978119 876464048 505065626 636561120 240772811 184620873 774323866 264101117 867536754 491290009 306453530 471840202 881332708 928062934 344367377 467699952 328669299 989002337 572729143 512479 955533263 371316092 695680994 667145035 735654231 55656883 850123577 464550776 618326303 35862930 385647985 963971645 869064006 347269046 207299365 872770657 952241765 357449683 460490081 434077944 341842329 156175532 731766801 597712336 958216792 110974326 925955327 251288737 480471527 652672188 193166155 399713281 905857948 26022020 843402820 504541991 994870146 820149137 897189868 128760764 18511871 553100831 247282867 884131519 587963071 886055461 597117500 626069241 101609295 241780155 341638356 830995905 17138378 31332570 244919078 224794505 281910225 579418903 87844924 937207966 118193297 414785116 256463350 765975484 935428925 823416826 572084796 505639623 103237405 346610624 363580106 564226867 190203568 247465243 529992328 508247773 945268116 950400731 311919865 504206815 53117606 35659705 492535589 800139604 809588311 940531222 916729804 100996192 188976571 778371019 776125547 470553776 745404105 945944946 54479447 502972155 941608139 727701126 202047611 551173440 381455649 294252589 953072761 326703190 982833044 160048096 720364071 852448251 547318599 346110654 978663457 883545975 25767259 707351350 278179076 771817922 581807129 866199050 51614752 151122791 211711533 358556833 197108018 185524383 48808039 2845982 48260868 768002296 942080141 871880978 867100544 272380258 31554634 12502416 264713464 297907980 164573026 159861196 689310554 546592765 532049517 702843891 402240604 692400042 80537249 19581829 915098209 645216290 839157600 766578736 354320735 895881925 253233796 357319548 19788686 50668533 470385305 993534423 556267690 931926430 666554606 509189712 486740489 183208641 834305264 994223793 865674340 751848930 33832763 306909927 512908245 37302476 74504863 479190246 698697573 202713079 112025257 76826685 929018893 496798601 589394306 747858806 659150379 984246998 638161057 526007075 59124899 70944134 382751772 911000307 198394397 515670325 487917849 58171068 33498332 122834043 680329375 548106767 858610364 944464047 803448708 463116739 923996756 64544619 240025991 982312349 87817610 790046685 17729737 239676514 104139760 421074590 204673071 712520029 221255948 783216641 789063364 779771385 831787667 367110538 557691950 294560923 421704351 654182952 408725889 799425588 170596213 882760954 328810364 696914056 612958371 91993982 938237283 507676161 424729796 245519896 707865547 971602620 332474611 36118681 144928176 909440782 159875324 191906213 533315183 440785339 76739926 564564716 443698652 753608631 582958667 702797900 912341246 962838200 557496419 357683936 557340855 770537384 548790034 410931420 461102496 728568661 708217174 111617329 934291231 889541127 761834773 868271672 656743806 587179227 687566226 479399023 491029554 766784178 975895194 626077064 284539837 967069134 431782957 388466733 752519138 233538437 607966729 566530030 278555383 787894368 802076254 66770808 906111728 222692187 534243159 718605241 574851493 735790798 50695555 339265380 62229383 453716196 90168571 364049584 496882715 267970488 930821362 793869515 364966 787699273 617727618 331999692 64722873 415115540 53925399 753479238 339512682 493068532 974212629 1064419 5813454 373620210 366049093 519347343 80309731 840279110 497842290 858116836 522566734 2077832 916868411 167902776 451724972 143640004 715160509 268700705 679706738 460428631 406251451 54244167 655963537 464155378 934469371 866959143 342426701 961061446 571793663 65915976 942484581 558466694 530607445 535586353 346949339 848109722 29103419 468963419 131505640 747316453 503105407 625074850 501299745 95984542 69993390 326371385 311557859 285982813 517433616 543964774 37522284 715420035 948706911 927120314 211251328 19260158 246340735 894115968 855064020 847893103 810073442 363356975 492789733 188533694 516214103 908028510 170104364 364067680 66809267 427590927 643671886 390563366 43200477 622537277 100517779 75709910 433665440 676979114 992442540 334784626 124193664 717436104 208540899 54420883 120557644 668103651 298691604 32120671 459658918 15876356 18151333 773824826 395856092 825664017 774246381 571464836 545562103 145897382 676638004 723207498 852289930 848099253 824559315 282585245 686931468 99244243 432556352 853283667 112350128 938340379 343782928 979549003 154722724 634021295 311582015 136334898 51427716 544938007 85512669 605700922 88167310 308973203 606492307 648821698 630084698 883229512 995205560 374426703 662535342 818615102 208918246 231378838 820325537 995517628 513144007 117282129 312848518 564530780 952790676 477006666 134421075 113533770 347600712 880172874 386208935 610887471 895713820 37329625 16725598 160810702 77238817 304875587 549486441 614519756 300132358 666153172 12190996 12995661 22580628 790271282 122845023 918329987 933797726 329413582 448236513 910733998 310830007 976254028 670775119 155237053 839542947 818144486 266704035 452731880 213329854 145511244 934703452 66805569 278971271 641045285 151044281 495492714 857885833 986211747 362292884 492504069 224542546 866761396 640833649 905304746 888706518 263093335 887595103 972072117 91138124 473965624 966316267 468019814 958867204 211783404 324110666 625281729 746085855 282691632 992757149 10240562 685497819 598397169 935500623 6015093 654993592 106605175 758077050 275173698 755975427 525280617 781031806 889547478 788916227 673114836 445530226 781410701 900761363 817269797 781882320 545564838 82873896 44801197 748738640 383495948 486548641 779405816 692046440 472807125 143878538 618889591 275207626 34137633 546269283 134928366 224676111 626692684 382419371 620182210 896994587 505646912 242841644 811691527 826754945 889130449 864117542 824914200 130724900 412997237 125876314 733812478 799829302 399148186 963445749 408870856 304779866 323397385 792215122 321269003 235720328 715727611 748097600 694129234 460746120 442801380 354220769 143987922 875597621 780072421 943567052 483894824 231265592 801125914 956232673 418411370 73918066 405174965 205528486 63268749 535426655 993146689 515963779 646925561 555208485 580602117 687227215 323527054 328489978 467188804 343648757 268363823 989169861 550573342 379327873 467821205 689148000 924580837 482021283 347625001 839348755 420377499 389932163 607164244 37543240 158085602 403085390 907905319 546803124 824925509 625783713 373645124 815161319 509855583 199941661 622119985 619964163 624457104 884707586 69556952 963743073 244205941 241792900 492733082 588541314 690923968 213428614 213411113 568950423 247647186 641377825 834405442 247786893 398203586 281540445 783348691 582786170 915631998 43391231 837140342 943572134 357123353 878175512 527874877 701266789 95246860 878903192 198086407 996714995 577805164 556833359 423093273 695986618 34558415 515067792 121475156 758074229 66830270 597607834 131690060 721667204 537782345 485838820 395809328 969182923 556925906 265832968 874879799 420818627 576352512 662880074 290498689 433657944 642707776 732719989 83561589 489651477 657324487 512158749 491540358 617355870 844331211 708360467 655711797 127698023 972703545 839682802 925620671 675970294 279679691 124203949 812281781 875500603 107573192 740353734 89172619 446485724 743918428 205602950 6363198 706876771 442145017 625154047 794816472 517558842 44799733 837148614 893816880 535897767 943329136 449640402 801256068 539181136 435888037 255224990 283751489 702556232 748586372 903789192 670781016 779389459 600907676 862442414 847688517 763433020 680733070 539816320 594379707 533448260 314977959 756602503 557233874 354585214 252808013 839521120 880391608 453371187 182034164 138720370 614072200 569552446 87967709 505518226 815948133 29276585 86705109 857364378 793689272 642054470 631456736 7535923 436438679 200271578 501942074 12021699 857522047 561815952 727919843 691277947 164455508 850367726 330717638 514602871 403897447 174919418 231939756 369727539 685925781 822140013 736017259 424315623 463387049 512995784 803172975 734254131 38295475 993453901 604687779 739504489 816025992 632786119 487682236 455793991 265606592 219346949 371387629 386601284 908863934 781305540 411274563 339876336 164621958 935841441 820596371 322121455 264094460 244981794 764922587 547047682 861116961 954517737 858308801 231720391 824935947 512591388 223192923 707322201 72419852 96914482 375136487 15146049 329379826 55901238 275517397 297334023 456674190 827883905 327371013 425824553 352557118 128250598 414924137 396305658 816195155 292040563 758314047 952380148 242399976 433191704 464834699 256294519 945603657 197408407 104961523 531004959 707560347 982297457 213189281 58325123 173406083 209771243 91751609 243959425 734953715 530208234 116365582 196405210 127516928 636906450 946740666 564515573 980430554 422799631 707201699 490350110 125241074 493823954 164214538 159267223 671235965 840786936 559389075 35193271 679502957 605330262 160839836 118251263 621829606 958302066 31682278 747374956 696851043 39983779 34857513 851218926 909402558 445369405 988179450 547852037 474359299 320829356 316396409 529969650 294479638 304023816 125142375 685334861 127885617 701320031 287547601 967828525 754041082 555534461 752834266 648995465 797155774 836023105 930153982 479595267 1746966 816299641 912609826 461287607 290442430 419294325 31094126 119537710 337453114 991980966 349858179 823422251 292630057 33878346 872702794 523073211 268725811 413904570 155387368 329735304 120873281 987778525 607644120 511803243 68624360 124799330 589392181 895866185 565782486 137779801 420017309 831664270 234330945 444378147 499716502 687404670 723823206 72213752 218306970 215615817 618221552 243472518 447187116 84909110 611616466 122930996 249418542 18762542 630823643 432051159 81800650 923131949 558317233 155969225 964979354 193477996 737764577 501244523 91791434 443085207 27489256 850248922 845088954 970892283 870824114 859100623 146791401 660749702 474618029 37629274 8379447 336125300 408503220 343837788 941225389 333093384 222247934 162502564 758571325 679621765 114818685 146009484 730443716 243291924 228936392 944695461 25830173 10801573 235917651 345441761 461176211 631847990 905235184 906215171 226157968 770064123 17303522 394138003 712451903 614216968 684518392 812876419 729140128 979376563 244946219 205611313 225729126 279503659 449635254 754170728 813384374 696408368 570407242 943896224 567111275 843927404 369528326 492639281 775735808 472137332 76515956 510947794 100431180 97412053 385216785 61868040 13648890 890420676 1319314 505851823 628045428 85710091 715758425 611540021 82276248 266756579 48214458 929938195 146623009 216173474 854324654 670658705 817108509 377696664 809983768 632216308 120337907 655196730 131434111 243512968 628628777 796751492 786278044 487495659 396049482 130404274 736934979 346959839 603244115 606364528 360911409 118413839 862452844 281589466 785534433 520488940 279755040 395834738 208901352 738041353 702888898 518234597 575398400 973330271 144723383 177516120 546186957 157237534 7523467 862866244 661844783 45563196 650273125 926672150 697689229 113065329 2353774 976350981 692204204 25171206 427174405 7995444 987420289 489891165 656986833 724520614 807673758 301110117 132683734 707485408 46150488 564580551 122919779 101788154 460901063 365635833 587174637 107330707 74820062 672245256 266370584 173870044 32528798 586791315 441885701 728093495 990577894 8884559 591452347 29719947 448647477 443684884 163323327 610007648 88666575 567702505 187545570 776413279 868290966 952224802 328426457 695365929 966563385 150297240 330229220 605503585 792373521 799391577 142072818 44265078 358560332 771090053 495341227 513289739 846665852 206504271 413114865 524966492 467573232 92142297 30673853 469119681 489815138 410840353 445603749 297856334 61442869 930487611 934539976 982725091 996520786 797058209 529975595 306994473 692865179 695904299 867631374 491907979 135771939 274647247 247449778 448014704 468694252 836176540 824408418 693378709 115176977 421220987 674967070 863666401 17391147 193713402 597775899 323910462 223340951 106249016 727856003 91718110 326531656 398508544 160725357 230570455 973514666 706510773 262271079 212871125 778370667 853569206 99473616 886976603 510617093 385255086 224223680 961660220 198200173 420632391 377263739 903978213 837431459 28668145 781014600 326530005 565928499 255086693 393666634 34529724 71019454 334085408 38919646 751982004 590805391 661540418 121173472 874435283 154465341 40724434 840067447 411172832 433170965 425111647 396786754 576606547 866796114 595248644 554034536 338488537 380420280 136810866 904780460 264792670 759648762 353323427 192888962 894983445 955102331 382473600 891904973 312876593 641595540 641820783 60565279 989455782 235587953 486191572 619612251 931955964 196251171 140502081 881403759 267913891 216852458 458992971 696060248 594202594 799505890 879923929 397741829 902531338 217218971 57183073 565509703 119641037 440754273 841456652 586357177 336922795 586515625 726741358 130750839 689632095 593632235 126327288 479750941 886826388 98151296 286543242 988943378 37002231 181942072 107728195 862192659 690206571 617519301 394596008 128268471 224791449 713920009 310367559 762600929 64318948 862916613 972949221 156309551 244465992 290711283 97346948 831542520 519902386 99064535 424876464 475737185 974565020 302573779 936454930 483218659 28875946 942346541 140324119 825145993 693882408 991256583 114649294 576296947 602338573 452437092 707838332 692966182 781677067 939441499 124379455 821689312 620215689 957451772 277924667 890102095 3125490 650652319 486685657 120081353 480253713 363876490 232134040 49373282 101030234 504523824 492458594 207680430 588720837 222077504 744417069 67374489 939456260 320526081 97889393 24547031 479111768 781914463 496369548 571551653 327990220 171588543 462933461 614395686 187942383 653081869 872138231 719077252 611343673 474797238 45231732 687500964 94064666 282044046 966945580 263228948 661859239 710652120 311335498 469984538 111393056 642966286 305005866 315017222 186449575 775411905 153164163 469140373 461394626 178259466 758081935 426644957 76649136 867072903 122345789 615140926 454860730 278250802 226968262 128632024 165066598 50397323 895448864 985258548 995096098 419859046 194967391 915772700 295902552 169743021 804283785 162438772 365806959 399563847 177681066 193743383 24596427 351886121 873681887 53738905