5000 5000
218295224 457122045 283065518 490316503 237097251 841258486 1059115358 874321536 73922921 706507882 257059186 392439543 1019467121 1007262075 704862219 547173733 766897334 653643132 1056331039 974737001 881946057 390649974 643741174 170469013 448433866 370042532 170030510 644015855 585711091 3390711 387485111 249252210 509944333 97009042 910925400 829097354 172616440 826129487 238544681 887950491 885256743 916890424 201985943 209557115 709995298 184084239 887308131 314244595 721740803 55266246 1058244386 755264835 666850809 1008204040 861968574 918379163 125208008 142171822 373247988 881448098 879850567 695036235 420940501 261070579 831004385 219317921 327307845 414719643 929419285 367753769 76370559 334272156 432521205 706347407 468984719 190461037 884704426 178571571 191422934 716106871 568578799 850538666 533436041 576366234 900828817 1053581114 577826866 315636390 78293750 471705698 39734062 1069792482 816143251 1068744784 93030957 191601289 1040913524 633225321 35864246 968853064 823548600 416185284 532685216 1002124481 856941842 18293679 548461466 43641100 1067584586 1001274409 859086244 454709552 435325882 969597030 180160915 280769198 168268241 671471439 19884689 419587830 569811091 496695295 2080155 112240624 187022870 329768518 840337921 84814965 462320903 610987818 1003358697 455283923 855254307 310783329 1030857421 922298188 541565887 406674904 467611128 14474392 245640257 1052015664 300323085 916241502 986816676 1026817852 159983232 248023487 811735543 543452548 1027339803 603176908 251316447 965820869 555957627 670129675 395453969 367566702 341297296 521667830 28406489 1035523876 438508064 595681915 414353813 1001634623 457270340 809889405 553909818 741098571 790614250 885192529 90345167 341280136 756980306 802586178 203482093 26112363 97481617 320889870 341877061 814247450 607535377 776201575 458704410 1017199092 386441486 572843891 160095682 387358727 32424986 472486988 135561258 105381016 381818266 427444096 501195343 754291102 382645319 843172498 350762693 428092231 470956719 753656184 662543924 490214514 712824753 426157851 897607638 729406259 154121989 878918106 27484666 17884498 599734705 311638023 917207684 325702860 863043221 334171240 883912555 131185745 813447904 518097591 643321658 850895812 189522584 598662179 505432464 518872255 767205654 663534541 999608223 484812556 72819079 402096971 412353712 435561773 262219629 636389161 1049624222 1066803412 1028290332 691094371 600462935 446603115 158699069 193091564 815237214 176932494 670706766 1004885290 211821899 951685260 899656480 702634104 874238537 396939498 828286808 146700450 353704344 708413664 1034221807 449217133 883493641 317721562 697203634 75957516 474426500 724628473 36415427 671985324 250559109 579069583 733903382 137001193 108345498 634497190 49982708 867149143 951898599 245793657 105267323 951192058 620562851 443513081 117003036 533179854 687815576 700139594 580667932 793326911 509504679 125518403 70044180 915414706 1069968193 943975922 760708977 557436667 372654063 294190358 129775349 308538852 775908811 417501347 1043154483 133075629 356778757 726289729 502121495 96256134 515471711 744144845 1072992604 150090519 828794545 1032950231 975745300 53836537 480476518 1032752674 413430051 502196794 899374333 257062184 519234244 92852444 1015722633 696263059 290595587 1018104150 167848242 765361348 99808065 932238610 69151409 122864464 1043702196 1058900206 467103703 329750910 133120484 474515899 305029383 273182667 648328495 189077697 91965111 314652518 80610118 919236665 111626740 130246324 756384430 995078097 913065179 979258829 194466111 844110124 714597152 591805181 924818600 92773471 457740939 1077060 40876778 171258997 405750646 846455511 360223448 609752044 97417553 663378332 245257373 838050102 582691614 118376370 737608246 1045152569 350024693 714999271 1015695348 1025932751 1051399040 486069823 428975355 235658822 477216384 557791348 666461126 126269409 697089863 37031536 543122081 174305365 229369404 696226005 584231981 485530701 302991962 1055232886 227925983 238955495 516544945 261200348 530311809 559802165 47588 1028504514 562794160 10812093 858421417 902322584 385629533 954815482 1011813452 835690756 934788684 1019383256 55256108 1016422748 821667992 801942843 956975420 49098797 783330093 971156857 80432772 713809336 750495052 576937179 962564510 826882415 271355658 862882080 308874041 341714556 143110609 623344634 966635417 1067876411 956444894 284247951 335781653 81743547 700735937 749953786 389260951 451365697 19395808 236263111 647532576 620803269 83422709 901888378 951042881 34501747 599026827 581221385 71775651 601199147 97174661 757925470 901753728 775813377 652076696 713728982 743262248 512756670 922818764 401588164 1060335229 985139549 66780926 231829998 185168248 142819727 713225057 992271119 116921505 216013112 260189944 681742676 570055834 320954096 559235613 67493087 673001365 1010364290 554327294 860505159 801031642 368847472 866150426 804120854 248539714 979580525 994667721 707900489 403999422 919016929 950619570 878138067 543201489 992152425 873844562 904102427 198916626 290770517 785870971 651996282 591186091 475696936 476484306 319509950 823141340 529976347 598766417 624482217 653447289 235697563 676491971 980577906 181594471 564159174 467381835 1027970371 741433380 978982386 386852829 151237305 559975740 94589222 991903427 352195944 214307028 763853470 452114457 667533397 706282275 267571531 744593233 310118265 597783796 1039528273 24446640 871300165 796540966 50407560 162074575 66791960 886057003 875076348 455894044 649962186 958581388 123811693 69039446 131390245 360832868 851573711 600727061 1033951079 869321185 331647435 201529919 881076162 335837382 511970108 707891091 572699868 425924332 352216755 952264226 10705999 533072828 106054644 944615633 300801321 416828342 369188982 820045274 720147565 827750637 187577319 993535816 114035088 1045353353 668951718 302308221 574311165 845347396 138054727 724014511 514398866 453311213 164285458 418729575 763980321 632959720 985313668 863202305 59680752 760840108 286747340 160996143 334551865 256589635 705678160 445708150 329748650 147497166 288759846 385188783 78452454 472139006 264066203 706146951 155060995 1039576732 62547632 187875071 1058551050 175342339 1063562135 381392109 582792314 43850400 810968122 798329210 984448197 294150521 248095157 676766626 179184081 429623203 350026199 881177783 252048505 164626890 1036913573 568131806 1069346569 988862893 222319575 428423055 467464645 349851295 511005017 694598681 1018351459 1002128903 999487947 356957725 822913420 89426913 1021345281 808034831 544939360 909763387 805789316 1032075704 915423215 118384313 122834959 444353718 371223232 835336465 284160019 791212282 344053837 116721040 909003059 668218184 1020039301 183193747 46081993 909807547 454796617 454596622 871775839 449428031 264945392 456901641 268966455 903919381 716732612 715548446 88926148 554812243 243600770 561663741 293373742 274763105 466801630 367846632 821326034 998489469 612731644 696573495 368044479 253873720 654636792 509263061 667879483 638956791 293096799 878288832 173246524 178936434 218755507 243196813 752906223 1071539000 287670763 538448610 565871668 312526889 1052455665 570894075 1028263200 856932091 58326306 268343334 1029171834 365687478 85203154 767770182 944699454 487394360 343853765 342557012 343720734 168889009 690946231 127949273 122752252 910224424 610155989 316449141 480026992 343418357 474404674 783102811 97778248 977628484 795082899 770792659 826946563 824659864 531966035 857284023 695784021 265296710 905553023 761772278 1010291879 459544566 754233099 506565908 704813716 817434406 615133788 639528104 490149997 899064998 497083852 442879709 693394358 301367069 1008745001 571699185 305913766 826556546 326276662 457427385 460337579 194891428 958751528 140905499 525821411 924052387 541452586 91938194 779639716 15113844 1017445338 89418670 918344181 248212321 773125833 383273873 850381843 136797319 866716159 842869363 549373422 122837590 653874805 239848991 41466025 316003348 1063049882 1033790836 600796957 514734171 489565903 333621477 710257238 361282966 487166442 320293626 746657301 705067656 856573366 550254796 283708748 804736710 236665713 56961677 898018981 1033902903 51581005 660014077 519422203 351750811 1792496 745014518 800286688 350464513 131646197 988891617 660482070 847188304 884242280 555588671 704101397 978738111 68739405 942248737 254032011 430321756 699479322 295961520 963117271 798923401 716000824 749617574 896207757 648180346 16571270 859484115 557217526 360945081 110189526 1062084761 460680589 684322723 681601647 675219056 984930947 334189032 585096073 402093155 212135483 177413390 46606548 674295441 492171983 31242478 852635121 129534636 108818569 966090038 230438135 665673854 111944299 226339301 969134831 817908319 547240616 243699666 199824472 7599552 40564520 605358374 858716581 777864100 885851656 893231581 735626170 425916705 308492823 436817994 984420467 1023229923 116133722 347151760 808797980 242775721 378077065 316743209 872076538 573559239 754787985 922139234 399096257 416467874 887994128 692242141 854680603 346187063 924991195 826666254 92331560 917583509 29637499 385147838 596298232 606359390 396295852 200570764 677654035 326264649 660562653 484270951 836899313 564387491 181718963 712603925 597617282 798199498 238096005 721656239 842192552 120515248 1061646049 862617122 914009016 146042718 80493318 143511471 148230653 536142959 1033370728 947818604 610496820 26406033 669192240 1002591170 306605329 809756167 277449657 512575213 484618681 168663849 172519700 839321983 186568774 495567586 754889604 93017565 597879622 119755057 485362691 669284800 941224763 374740905 435822011 814751413 946778909 988919282 384297614 285139613 236006612 978803269 413013903 768753710 1060193726 750277108 493257094 1951600 436257583 39512543 204284272 1051174465 670308076 282402560 733921532 254247122 687995823 676339424 571080463 1065851432 383934886 818321440 996189249 119721116 810527476 256236273 968279902 268948059 205928494 321636764 736149990 137780710 893666528 728340731 215348366 987693715 210375685 599941374 720362429 833088778 895118482 705330471 388658191 501541833 137946604 459881742 476180181 165562273 237765742 429319390 1050031763 302902327 66889188 673119702 36193153 643817603 628407826 295532233 991707147 326209364 10511150 352425118 609647953 332652491 286141025 449589969 1054783399 692493787 588141642 844125168 958278421 1040167631 1056131451 384959006 505444312 233024964 475064058 1030324116 215111392 399154219 490576577 687720219 927145553 381563465 294801471 147512467 702879234 54182838 36252885 486370671 449485824 476941281 69049434 605274423 15276300 964118154 336539031 270465541 861422873 581441607 962412236 67249416 277953487 851822336 829094441 414292740 766468363 4506227 584819285 712323280 229610844 244153520 416689898 774125527 548518535 121180830 105068791 241880728 188123140 995378292 286013310 285507877 895627135 748437057 626920435 67221927 574181720 515944549 283598531 855736537 249774372 816068630 639093706 611847816 434739754 1033476060 660725468 518629914 846701542 111656980 981065789 908942084 261752457 600156017 597061929 548104530 797003639 1025373046 145717325 345943587 515753416 206270718 1019174475 760525866 126029511 631004340 318904890 409708591 149332598 156302235 976653860 185899404 371134472 1020920712 534590343 1062374064 499585638 740053922 460822484 960090527 957936811 313359593 566962419 338806895 590497448 756325036 1921468 405949901 944890208 839711506 527853184 386340214 1025096588 331388818 266396030 294439103 768413209 151969147 464056174 619869966 361810085 516343405 580733946 1073239646 766301702 283754717 1028517440 540103614 80326851 736946325 676136274 390230995 775112601 905219889 930071733 404882258 957788663 538547363 285933797 207198087 801354882 1067814833 825760720 826531536 518690194 257181298 890356054 1028473122 618676659 949188308 770896848 221565060 148389925 616754969 1018882182 424348047 439056221 376731221 889828407 850650100 395428226 178980082 142722964 144847606 510087408 572411180 973552581 899601899 568911032 309629846 419458787 348174528 712428830 529061779 76935293 519316594 483475482 480627677 921779732 271966101 157056471 902438657 411029406 349380305 56411447 14980065 456127494 1051641184 3840077 387476017 498105771 41579921 1052659938 905451259 380976861 1023078728 911443185 684346651 137483875 4672124 239614762 969299395 983354359 688415672 487255923 727070968 3046599 1001996443 795666274 961918483 2152438 166078039 400676548 575835202 166751002 527305781 96392218 952963844 815480508 935484432 612048151 1014407856 769786588 992248534 49294115 997379311 226986858 65753354 43620314 999843133 546249933 733752132 248795534 732813676 947882079 550472368 471834561 481155617 715233519 53595531 794654636 50582357 457101118 167696297 756031675 1070445781 283340419 816087793 815606030 840665794 262035688 740679647 730638841 271541778 1010809866 676578817 214391941 146511118 127470972 219395195 802749933 740797394 566253381 194806404 338527266 499866832 894063709 867688422 475406920 221192525 714104116 285123970 356687159 927969762 854303788 270497225 92794874 802868988 469352986 739749188 77152339 846223708 718803656 595174157 437232437 1004649112 1063772534 900118868 618901833 728964504 1066034516 672447963 179366762 739931930 174329354 327817851 787771176 633265711 865869872 962549148 843938633 914011324 110764503 549446336 968737859 869900282 298325758 1005077241 1038620867 874107126 970165789 359101807 575821354 527080721 350878878 89995227 346270986 154035841 234580831 784209678 870659502 288904398 268071729 76402539 1069700239 219045206 958073180 388201832 264761055 958929866 370449433 694623762 312897282 842037934 626982678 236281734 359504144 910306269 578004982 217661816 315764565 774598915 420494030 271713712 174646993 1051440161 7464617 426864776 535342009 565538829 513380869 1060723056 40613364 128706799 864638804 840862570 464285086 10794181 746967419 168359310 122199944 765989855 525645910 460303238 301957558 972036452 226446643 345912851 15894495 472425420 797874003 586298247 551880689 531539299 139489388 538560585 494644875 903003340 1138985 123068244 545178497 253107580 132337064 850967224 957824603 1013794875 81261051 543675416 185576150 410850215 54734504 1071222058 102161762 954074288 838575401 118992954 620394402 660240157 630858861 268157095 887930095 590157317 599287125 1030986596 616642261 709108823 909285175 683501433 472656277 176133459 107494495 380229248 453400737 988902670 7853705 886846760 545757988 1025286386 1048929128 520702901 445431927 104321084 1005824290 741838462 483509420 812280957 279565009 67116653 540431623 873380377 877681924 1003329923 167519360 686805194 160518716 1008515921 990253123 260826142 827938672 767348096 656020528 575855605 638945417 789473354 874418012 786840836 519546087 289637119 559798413 928670037 993102810 497210497 918692546 460619973 892799273 583074761 1008316841 166496644 503280015 164112479 944987686 967624856 541167417 867375845 952167123 722526811 196697673 512628109 542419066 824548088 677517654 314090655 1055189661 49049330 297440745 404940532 812141551 345373597 436400386 865050237 70828761 952514467 897387409 735318205 743507445 164854657 766367486 387397451 881803414 453335559 479981985 806436945 32610110 836061403 806228810 860708623 433749031 120527094 886098363 73919577 827085755 280084262 703497513 458250004 70052123 300674186 469169343 965174462 881013404 899643162 137933594 660586979 834201157 788533788 134726350 960357032 668556882 586438320 66575071 483963716 919686581 424909893 790561609 779720834 833668240 908566817 173408633 372981825 635995324 988545757 796300498 759808499 713860676 265258726 614302505 723783458 932285418 351351550 929690953 450638822 84846498 1000519097 540681072 408151920 847122194 665329409 762434000 360705154 905601049 410478738 917806350 665240053 327218501 444092030 405378758 480420658 473000538 4487082 901296646 404576441 898429138 602402383 105676750 953407645 683045975 807397498 655408023 97826566 968068939 832364685 917743561 599877294 111923009 809532860 950417987 302762340 791169409 274615440 5937367 809078924 55902088 1006421863 612722123 186740125 993891206 336801522 979098713 841716385 907201758 701182646 416726319 345178809 23456937 1069607308 602966768 648393366 677990963 323099170 535172786 251721985 187887485 764334967 209017982 467029845 1039764921 1025004898 136163283 2646527 811065809 918735115 996325411 420212997 478671073 1059342704 201866580 988217468 1051149496 465812450 408175680 112515344 334852187 744257670 978320182 121493632 571729026 739787477 319092343 375362079 105190425 987140636 499072186 172572500 212822208 778480124 189637544 716898331 261687115 734659307 625015904 776498050 514614339 141886129 959057909 1066790957 775170147 864912620 199158763 177833170 241067292 657109901 347406013 299739326 712579345 563556185 12813402 196883534 272008348 646809705 1042760355 128055670 1055542855 142411434 255530479 458077246 1053357908 969196125 635260296 403721024 2727990 636882072 112089131 135061548 46538005 320186307 877674635 863514692 83515982 182013980 581466575 769148128 989991153 199758899 840694799 726103019 238963521 52198767 852701403 497987683 611268919 214009992 804859829 437005021 788026623 1037430283 49957522 95306239 35608442 893958873 784591452 192267013 877329594 893171879 50805619 420870717 88414345 71607936 125151783 609358730 226032355 380027198 788836160 943934181 892544119 1067129877 321514615 177269975 870599466 713771272 924686586 414525184 391917204 475222386 320486891 222210195 319798400 1015086719 664552162 755700440 391284080 647197104 413256294 210450857 815628568 54299994 283860600 218248181 784933598 698428711 758836489 566541376 340835937 144092820 798266494 494526753 227654638 400869746 981418035 123340227 806034700 293910629 339940598 946877028 27185393 853750120 841657735 14234841 131094795 102608454 197240607 352555272 520338808 860063010 907476454 49332588 432099726 429347057 117062010 796084117 670189653 818686459 4090223 460295333 102865160 843624029 49770954 823955924 884814743 174348938 180070277 423882989 928220455 296235461 820231439 410987727 467061904 236009128 935984841 880562669 165265118 1011659681 503996297 557377231 433191890 553276272 969069850 910601358 878072414 569084330 466879674 738733916 962614572 660982585 992034715 552740601 797687576 89954010 667766627 650880831 995469233 750374301 108991148 401449111 509380540 613833576 329247109 880947330 1050873265 192753524 781742575 130466321 902578747 548242639 756388961 357203565 677182652 358021849 910549060 237800784 620505032 635108807 639219831 241247626 196335013 990707491 948129740 569208189 1026499793 326336073 1018623369 304556961 301692028 881189099 275395049 989316865 432531722 602774415 588690072 672765884 581255314 684173836 20285243 978945924 138966882 350312464 662973925 349635107 189054072 368695709 507539363 306361841 810759690 251868039 476712177 35562591 663492095 962753528 855915074 771752560 1001094772 237714156 5434493 651061562 156087864 929501877 723285370 436328041 1043541329 156211320 636022921 786758845 545018229 59798702 977469164 735372423 502051473 444998565 469128279 595647535 589985605 142773756 72455031 707311793 989536614 654733610 359004777 316696092 898212475 268802040 88399678 885770258 396410944 119923458 289569917 945941066 300796198 721363258 959778209 749437201 4167889 777762917 45464471 612645317 818474137 427203996 73292098 467163992 861603850 322837964 957050871 619067091 816621923 848426551 454695937 494888913 160747035 394476785 128760093 742778112 1045219159 211229027 702799615 99541155 498048629 805489867 774155723 981563666 1014679941 619547322 1029008029 177617208 881700811 212967829 1993731 77064468 740949566 136016661 707352189 704884281 624053259 10992839 224602371 480771151 342626067 969322637 893000063 333796751 12542057 706403610 165560655 435116875 712249557 481748602 998382021 285879907 980880724 442568328 899303591 13443025 966038421 449940854 438090927 727757086 264025725 1039284809 79763979 717219051 188756644 220070745 373520094 368533353 806523607 73610965 127821757 778426081 252224660 599923518 89185331 352048173 622509200 141318120 312167230 125649725 44124980 235187580 884977616 633197459 983056668 937590392 641946959 1055172807 433865623 575416237 304837653 648764164 644690217 1002186943 390077937 312199049 648803852 102669481 323779236 1062383913 815509675 537985591 912053348 499069131 19047974 371446922 503247965 140703211 457672401 1008169880 948129579 9361175 796099253 237034665 809271649 866726514 179449357 438645467 515808261 141073973 233878985 821860255 136364305 873851177 759063567 531714873 507088884 399207214 923595957 817777988 199549455 632694199 594459081 894522668 138303289 240464972 727289865 378223282 837005883 901319943 669328235 784152171 842433876 818221335 965378966 715825729 681094839 174943552 929368167 852099569 497919240 284740185 645006957 478370700 1050481634 725667277 953209709 594534390 542001236 904915483 352459487 714826602 179072351 683835221 623510127 96708084 199399546 63392676 776838782 177794037 329262607 77605827 798242462 704439970 374695419 599731072 159865369 289631365 947099666 430532158 760333418 326205947 28326040 741685109 335581634 444608948 406887625 63683376 1036272517 546846007 69099346 145202830 959255755 827747675 977444053 135675970 846143200 856140495 803864681 565551380 178212291 938264211 903061528 1018635358 921969835 393644668 461285727 85794959 671666813 260663732 443407794 821903275 957781591 767199544 157638389 230502344 658306057 9607256 397134852 357999507 280541334 281770298 273231148 194257609 1009602232 579844440 625488048 592587455 668787545 1052662269 49624901 734011099 552426010 69658828 723366038 94243096 581276112 13297721 408111041 545237637 1034909954 320702478 690413527 613319 123040365 323366376 325967968 154254739 281348480 73125303 528339413 394377525 642709217 229118529 728746532 441766155 379745510 1005016479 912075056 974569738 34890780 176613823 866329934 92729145 836288451 887533793 639608778 653634609 927457871 261654042 57866591 562447267 320510441 698381780 524238530 376298706 615320812 900974155 510215448 305277716 557543017 997937169 844570235 569208406 321225380 282011275 472944250 814302101 556594069 452792435 941704854 738379109 498365799 402772052 278164165 849968238 503397116 801946897 964171250 140287978 427506279 226536030 863876731 332473896 283885937 11608388 391568050 600450316 1035852309 648276130 150459741 1012859533 155123460 462445991 852976183 741930294 199073825 870358105 153948780 701617318 342652677 1030813713 355731744 951532047 928885629 147735548 141035497 382202042 638011399 981035932 399002448 829699714 232816217 606296901 521385812 587189333 1069661146 636500128 202200040 935253686 522685991 397798187 297376112 995593789 426694543 977007799 597593415 235159574 622252951 813439465 956608060 30318206 151055223 14867130 406204688 1070850377 732945051 512572152 700419322 897758814 713663267 982244034 330258468 165413433 957731428 488627983 483718187 447934568 138188132 117221927 402852514 32199695 898276706 445244456 391043472 582801509 40653900 220025731 659378157 1055883572 326197574 541164925 307722793 337640285 931822890 586335919 734510757 16301393 927700739 987655046 591030840 846854041 740935824 899967172 533531820 422827343 532454087 571882492 593536319 646548643 855448144 829957146 903356194 300957527 226933766 549431769 408329724 640527172 349606266 701823051 8559208 379300562 730615151 1020331348 465915507 476349827 950605918 21006895 445149728 465932393 919614708 526502888 58181604 290234028 193393807 291681248 247626026 119259653 645200837 1017559117 156779215 304405317 681727709 318837943 2912679 393050831 331079251 1006097020 863088375 424349977 21916505 100835661 299867385 212332336 571006033 533430191 1005470555 910006065 83716436 426587003 253217728 266001616 652101806 766939741 957877821 899438037 155263839 325556825 321842653 456366746 299751835 376560193 89818398 153376399 835491659 960014912 832512625 570566838 348797066 500315219 658478270 800347175 410222121 927354059 503564254 951304332 193368620 47094476 963784992 491473574 891706442 152539345 336989124 1020781767 605333105 662582566 314336643 587695958 100143424 559069804 1068661509 1025241422 110614667 957802520 772301929 388479167 924641242 297685749 617681345 558836556 1028767466 401532317 308352915 1024065195 182789675 859846916 126798681 308302120 480588608 1065139437 988884994 757922338 29629826 232796275 337916527 576498316 722821758 777513602 1057175030 1026514286 38582898 12841563 116191458 880023650 155409620 238413843 973150450 667909143 19993803 707902740 342024150 620012753 435299763 468532379 863354805 887839463 692354974 261153848 287348649 827069251 704988110 259329105 118200385 562184166 58169660 90628256 434208766 537555041 410931476 65218737 210577367 129155677 517888822 391831652 998137781 685548052 1048545974 527343729 1071946487 112909014 950741597 808670943 452160752 479328133 390881574 997085067 689788260 720991002 607151810 30837928 492428559 219724062 675678229 207056697 73466397 367818288 853572534 759934872 267220147 897562757 686851699 163653107 704258917 640835684 474836938 716726986 268900285 569729190 720193137 375527282 911450811 529157949 640316624 828591765 857921871 398935465 33498498 672199855 838361313 315789700 206141399 531837074 786041801 1030042871 738755669 801344484 965854679 101300034 681423154 590277532 15225037 39667001 957077211 26302600 636145888 474882498 456733808 544970698 388442426 123594328 858534982 1018139478 871245947 1037964170 843972708 459346550 932283700 104165756 111896327 863355462 749087338 1622117 305106718 516263480 675402777 970078480 703331534 324683921 222133166 226221404 491808239 615490283 393385100 105060539 91281037 217282225 788404360 228995255 474064232 1044733350 58614893 548799848 467384436 1006049886 793994361 223748607 632756570 1003311298 585044189 930782526 837835253 255659664 398932545 644532734 109267158 346956762 204514878 436123560 915436992 817548163 100957154 669090492 697828909 258909125 506200112 550565197 717117896 763852461 332702366 1037727619 556784 699716252 665639317 362762264 161281851 500789960 1059311348 429044955 688245745 4716474 262954124 456698672 812544652 218525646 301684901 426326158 434340159 923611062 1028010617 361489151 110474092 562428663 176545460 819724708 102022701 554433642 1068798970 296148270 630551756 82677436 51271520 277520486 120274250 678089966 911333618 767039655 17749212 200581846 436150316 238208606 81355881 913290653 949520513 17743249 247850253 510770239 434245079 213079637 485610649 461484046 1042508040 68726102 781990417 526056751 560168035 604697683 191330861 925334298 111939625 946115231 311753689 348534046 189488913 156702113 306945205 537297628 34501316 279048533 651326869 267055304 377868385 920064201 567406338 199653547 943977722 412956321 966141367 354355747 236757526 334081427 5021477 934077217 828865069 491145452 591678960 64600169 825978159 487372041 841901679 257994262 498300157 346757086 777913136 1051762708 455811566 199197043 571021681 371767972 1031927627 100314210 1065762216 324723420 727128020 1059032667 143636477 239791908 156123705 830683296 1031792843 581873594 759831970 581699721 345308450 556681007 431117863 951265281 959279943 144888552 11405656 394518022 319450930 123265949 258540214 102346541 361783056 72173021 21907512 465849884 386133951 812685960 994899656 895769615 801886549 535117652 789868228 850164052 565365657 725452617 106418301 996255183 119710343 415286085 369805499 211480950 174705360 228924024 430222647 234945749 620195416 123089641 912058655 789465483 647741623 481176048 107886997 206592715 80454585 121396409 743717424 480552413 836443102 880738503 772686202 645780123 1010996442 522783855 408685937 1025330164 903542294 811528025 704659462 98050156 589203245 687086339 117353377 89502362 845948016 313711421 870215579 885930409 994198370 965967534 417752258 525144535 92423997 755126093 224549337 116317433 414164331 152918761 719167509 304214773 321935886 133401506 677865377 15147590 160050297 449286253 1037003803 705839228 765969332 189633940 250114325 8817337 1041468156 619334964 516263573 545052213 1027302976 636897213 184470933 616304827 816756389 955948150 250287235 65016106 677261060 905208310 249947074 898971637 232650855 730887852 730489384 534437796 1000482447 812521815 485964158 205593937 474184817 1012945295 370000643 623595819 297369780 162179131 799966185 990742262 614588980 1044525080 469760470 296724104 997698690 487579192 564541284 896136269 433835106 1059893889 520802466 409428421 667870284 354693162 362256273 937700865 16019692 808789569 1022994599 158324266 198262178 328124456 509527888 808113658 420292866 227743251 934709864 973617217 179386708 420844940 653580482 621606753 57180438 110942704 491566500 747548114 499241845 765451503 443866440 511153823 728385752 633874191 803582301 948067815 1014272853 137545769 203027844 226181468 781460282 950837227 231529428 847315144 73210757 922089044 524116311 876912259 76027500 939549755 426474122 340389886 556644823 120523721 794398688 237239868 654908384 798564602 558713408 616183379 884504410 759513633 940224386 931555823 972697671 644751457 136023798 533831632 1055893600 750745652 1024081373 368718919 861725585 110516711 748823534 514738620 99023994 4375068 842143699 3082539 55863536 88506951 298519465 1066316451 1036979834 26671409 595462532 636681670 1008903892 181902201 111181800 231852620 821851247 295783438 487054929 942940287 975881967 448660662 239894956 703922624 669011884 6934154 319451356 285313280 200230450 999393911 136014134 832035656 286088385 890603966 165624580 461989939 437355725 520648309 393606662 662207087 691405694 367791109 1040311789 1008343103 257250866 167255978 199679710 460665851 590178038 810809590 202136053 941796494 10260753 1012431438 152658367 311205367 266696057 550639979 414764735 506495433 350887772 423569370 785863658 786276268 108066968 990833532 954391339 770952665 761269827 249759495 17543648 396755362 201434404 835695235 428082523 3780584 222371384 1050330062 264286049 558169506 1005267759 1056671513 666325678 787529821 32494316 618456937 522241904 892915382 799000072 194602775 951506888 1026040033 183403343 20932688 259443788 975126822 649153601 399394197 836618375 1057885279 31451539 1048099388 86833015 1001898620 785563563 585210605 816154638 32597759 42349352 442490406 281901490 316731776 198630744 322598072 849983677 876596778 314806464 233534024 386075390 228077116 531574167 509478351 1034177590 226994313 177981003 892387865 949549723 385690104 309269499 821278282 124752728 913880581 1009793787 929584724 980991755 525203262 977854292 381793155 503729734 820027334 465832257 786859249 766314000 65575382 59726259 581861394 260258913 1068369975 666439373 287539498 392217769 927733449 414439528 381748177 304098377 250583807 278068369 380988278 417220375 689374305 172641286 203365337 741903327 466853129 552756925 592568720 395296989 772250150 923029597 454011523 474380356 480836733 630936771 768577136 620780731 670875874 867482750 49882983 14929370 685596867 359649620 673593935 651807921 770974366 860730043 308424543 13350977 553630341 963803744 661346982 1055316481 873282209 786575523 250647684 853066331 381604781 348459288 198517295 856847660 864413047 228892424 493645359 101017159 887676770 212535791 683348193 359024115 314372326 216490492 700066040 694918504 661391886 277290131 747799543 739097430 221293561 672983246 249665209 877031519 56068442 31151096 150193641 424844184 461371129 14106129 1057554058 233834252 786017328 474553933 445849201 60789816 459821934 113907604 729164998 367212688 155249335 496295171 289956486 1031784952 935949345 533128810 747700996 196778828 318469721 765457613 403276899 765257945 278973724 264300259 702449693 925897954 362269119 107797913 1022206848 918631452 588096424 550088848 34011180 270461490 197441746 471773851 422255766 534255170 827235916 185910850 852415624 645975901 156270779 83313217 957847966 1005302027 717346004 485729802 18772939 175175621 589977571 559521343 69902802 304541049 333799495 584702265 553259469 875079178 392166898 63449988 620374441 97717197 777546478 257492064 495640488 738475021 891276243 417641025 826090206 1046229896 551108690 589592400 18191285 847071984 79250350 259190249 298421354 256574315 524705085 353221915 1023506829 674079507 798597356 5545258 714474116 541860214 312344504 973614096 299106824 902882327 676358197 378278392 45698726 354962156 16725771 757462466 926208832 876645598 311129972 926695810 745109386 902489164 900199359 932787968 65689742 343444360 723064273 698864697 754798888 373164376 687249310 951388125 366629514 126995830 803799988 1060156879 619383993 1051467025 678069681 233540521 973858574 650628938 134777543 995697973 935970999 325114296 1050784320 986677492 346370355 460631268 732335604 1002783899 877633753 1019535565 458928852 286478737 149770578 118698341 202479970 540387699 1012088346 258198291 997445174 411640464 558497027 725444399 1001976444 848161901 751494834 870856841 283872369 925131842 927043360 296626146 371795945 248494459 97291802 253485169 719374027 418800184 461084610 876588127 672276883 186572750 311452939 703177036 496089039 405951300 1035889729 619486408 390246563 532472278 292252031 425496794 710708038 623569269 351221559 902799485 178790274 252413253 466908846 647924766 666955320 777118237 118851709 555970079 307380697 227500811 241292561 922371927 693870318 138024398 291005739 826399632 258868370 703199066 818596449 869948935 669842674 362186839 805132187 681962992 474709460 886878626 501557655 852026095 693213453 792295627 107675494 703195552 878214408 692782229 732422893 493907984 680117574 202699129 120070501 533193282 472029913 339244580 321459163 429635243 1035117801 691754996 467351472 622545590 156911919 1019588479 413079322 825593664 101432444 836762892 222953889 752715037 181166899 204836120 862000291 977766801 200442314 659860690 727487441 707424984 812137806 904638111 904237487 1056799904 786885596 151830167 890791960 943391881 859551016 527009542 901906616 631281324 193331962 1016702188 10743184 40585745 494289324 139652221 867062134 412904758 596570286 900627874 591763602 741638799 845480706 845686902 58687714 779750657 98570176 505258442 426046134 959589478 376984210 160270242 875407669 300222988 913865785 1037678006 780577495 891163958 926733063 197454321 936219112 698879898 376775523 586463477 626173195 466807265 862060616 825283221 194461621 11399210 202789830 161617498 529468078 21710471 45531008 336852990 534774932 771732862 716819756 70464500 102947415 966870665 505966358 416306142 2068414 1019785366 450744477 589005590 823359456 17798280 667317940 367571750 988511660 340986293 35696739 485298255 260553826 603028070 314496836 1006650886 167405592 537546842 725737478 911905650 264668726 650146115 190823149 1037578224 975369721 930614088 773784656 708247439 121030900 773271937 521700633 945035156 324791178 105302142 397869897 292754167 442342773 649118400 611836529 443954916 12270147 876686654 304616506 186836795 618877396 761727969 590010590 224455440 947359965 223479304 212979629 611877164 562887016 926212870 1006720906 475415690 602401618 696506015 598785899 13033691 306248907 959749518 283723484 481892099 125936345 352348674 145026683 25104793 671525334 278962205 753997949 369887595 719125997 940761715 707557673 775272952 721699745 718532241 742872920 703735284 11452486 1059408243 470097148 479964103 578818694 759741453 607827861 1009609230 248429278 46276547 1057933501 411300889 1021408286 496597745 188327581 446649963 372399084 798289252 692497525 199322429 934144833 159411422 550689561 625737467 988856043 778490262 231491951 650462406 126595081 785887926 364143858 911514352 742407315 203625180 618463793 123969411 4341711 597384345 866925904 167580859 209189597 567553781 332966534 571348359 1018686764 1038416361 95049374 648452620 420281602 1017408227 356292471 691522594 116584440 1005463878 1069296771 81013717 311866235 98460391 547893068 896664549 1668429 739453073 655414250 925412934 617319426 720116353 316242318 762357921 141700996 349005035 972425979 308705489 243433871 89721972 363769607 772137319 660891189 481757878 400247070 359622183 162638939 47135423 136759743 841162888 863340090 848008594 692997885 289825848 862933471 219725476 643831040 987509654 978137516 891641952 134067842 286098486 871494869 841013412 832126290 929256288 682676195 461256002 649593556 34081425 646964533 200343680 405856383 755643384 847715706 481385880 963391581 463011579 29380663 682980665 497360271 524555440 987184199 402141700 489178311 121683044 1058623575 850840847 43263179 933482519 1002881894 1018079845 1761017 144933118 55672139 408946053 750634941 769321984 782028590 844000735 160581405 629407290 104823821 876385114 251595054 800860539 868225337 7463632 33390236 230910152 987303639 888566416 290925862 154801369 985030752 919846619 988434463 56920217 926262561 89601639 954517742 208147882 707184827 357504736 923262863 42682592 478899108 877304162 266752784 964132545 131537828 870149888 304364053 695748620 1060166745 484117824 230273876 649797166 548372404 714721949 690906650 546269134 245124730 238177028 1054724804 681954626 817103044 968801367 37024583 38919448 1029965439 865821421 754002856 969474191 185376748 833025551 879037060 56836123 692045345 1015073917 112384394 584669156 33579910 449566951 269417980 444963911 50617433 74249844 134228274 581381715 250898219 499713343 111139095 681312334 917058912 990500565 567814313 371567150 980413363 727247544 312930429 547884576 323283632 203586271 576304953 543706372 68773688 609572916 533885465 801934063 856544000 127997716 482547051 312443816 179737875 28904403 854684947 625798955 593105483 160503606 292746503 337655337 875496924 1017070326 301009363 445281926 211855818 572272195 367462678 173758426 361312109 910281279 736184836 453455857 444041204 1032644223 1019123170 14939979 451640543 536546702 15722637 208080284 597039235 206385514 1035469043 292277837 798744202 591767556 174834072 376239353 298964081 719910852 498196755 197579249 637590025 163378179 583199375 184110776 169988598 168405391 380210762 501596808 530651699 622435115 763609625 235902667 345822347 377114124 1069527522 1004321699 891551521 926426717 1063092256 1037266019 74996970 556045244 892393059 131941395 508472878 437358011 102647245 444965360 537639178 118743136 6092694 976870890 436740593 666978469 817114505 780750116 147690534 426926328 1069585029 157652599 374815299 578903484 388946686 912348911 592676534 92936647 251442553 301110860 409095231 481063650 582683411 145755011 1062545011 1019672140 785223674 1049833787 611299900 549248311 900277234 1043835472 1067980375 481417545 756253393 807040595 635821012 424456476 325469443 433780232 37951129 385232062 214708232 628768743 390847968 957862450 142726897 815547548 138187956 425619950 773163751 600163207 709296760 586613595 313072548 295571260 499891040 903106905 909076472 506372612 798939382 300349112 145505861 774013530 38142614 174238399 930516227 503871343 1060750834 16768424 41444157 26021286 270712720 691316002 426459410 717515545 538809159 326990030 18659381 962589714 620246213 9748163 11197549 838188947 812744716 1018800138 382141461 490560463 159162864 49077539 921983133 793731758 226250907 674232958 247936776 921132621 428266505 247946498 321282156 346226043 1000595084 561626762 361396853 977344573 739030345 382673507 557768675 836961355 242100409 1011978703 547340551 760002961 992337194 164538501 173806665 488851120 277013307 1016295727 380982949 271390074 201826403 984617450 1019059242 445972345 732399467 1043843274 932868218 86291049 386474223 142522451 331450189 76211385 281273313 492471297 71089389 949344782 799071750 107232449 1072064187 863451071 534555767 506830197 648737705 151169370 744834081 598415220 784981181 636343582 270109254 354660104 437511573 789487743 252493050 331261935 858467550 681526438 398535590 245301722 314936539 628830958 745389960 908674289 753486820 1046464872 339334193 927112781 640589028 288085847 343859206 1049906300 822210522 136376757 839478464 63495169 853414489 690100140 978771948 483111889 831725577 754263838 349639532 420180439 142754595 511779101 472628724 616077169 635225337 34553460 1063857037 872777200 266923628 76239900 726943253 912706332 842840179 851544008 1000730045 298991022 855723163 950195290 877076874 637528533 271668609 679435883 43284437 397069745 81370970 172628167 110814923 600761819 911804523 853129454 609901805 988416475 698401169 589626261 486877585 608016560 7528123 797194531 809416031 688616780 1050949483 787761716 89983701 131584789 391943993 844184601 480784068 799560293 39042640 60478806 144296144 54947082 420819439 758311459 790436852 612086471 1010654441 152797419 315674364 123033042 12255269 406570704 608404745 224397140 621769503 563696678 456705553 686662636 244102245 429801715 400734044 139472940 244861466 290851189 203957256 152773914 803795575 766362268 752932230 862293169 197567557 649338507 722877466 1023962717 659382116 249250076 893675359 349965187 413748552 573989977 10014401 905866230 878260598 498781444 439577089 51198595 40741387 511643407 6691252 694776166 1003143221 150839845 66379716 208950994 258197689 944850463 827680750 953305453 796955755 897005456 32464963 531291346 653881529 915321914 358392231 434423310 913930273 639192982 849946709 862689315 968667829 842667856 294837337 1047220360 349374110 603359176 734603796 781300646 693958807 1047941267 372107963 1011841373 332184686 641886456 571808984 269928829 816289158 277181555 109374664 899450958 700745559 978188085 292818235 387347208 193746412 667572898 554557368 8162395 574183012 730612177 619506966 717904105 521703283 902213136 660549124 255519687 97069534 730854238 514106242 42779391 561754370 102661359 103792485 406909969 36905805 973857196 1071881431 232335469 33804995 647153840 1029048533 1041885691 307565946 215031243 823089839 474562452 287262239 252089859 130555019 930060678 640521327 936641550 699270115 93818388 677160383 159186138 60668418 923657715 182158709 354831365 409400459 295663822 308995468 437762149 436985330 333306306 312291092 754587777 184569345 542790627 857236143 655963926 661246549 820655798 1020348693 497158035 375391966 300118709 793965457 551856797 590167650 626886094 502664322 59851404 1049492219 779401188 355039195 704354284 133052052 612607820 128598947 559517181 514784112 241739089 63596661 1057089332 996265123 633692849 816601601 128833976 285925015 37415966 327444362 515437541 912203656 212727486 484076646 1029722316 386338824 981761195 1036374146 839064753 752675708 283584883 87218395 660859275 19603614 805344921 85837829 870601608 904960505 641521683 1070911144 818574727 387798640 193583306 490327038 427634076 869388727 613943069 671014486 851882383 1067662551 236605790 317244309 974254941 1003914927 805597779 101616047 480990646 681849966 952929718 874057522 922988670 1047890458 548117686 931386300 468395340 791053068 886811252 937040000 601179117 793090673 718856326 385601733 68681442 122774475 1000432504 643392102 774500317 754742126 116817734 607467091 920972361 610932483 1050190819 15014158 96725439 695262728 428749237 739240752 203666066 551023182 257693207 703373794 75819588 295256186 457914326 814225252 969400846 639692933 128299956 218016649 376421724 898379325 16279784 280900664 1004725838 350994881 827348379 113819117 564646456 813758472 595542892 821042230 1017615907 754932570 777438190 219793975 779012938 281852886 669711653 578558759 1013531550 893454314 550684173 383826640 254185027 1072100574 660968211 199327251 966347793 599324490 318714521 69927778 139678739 711297947 389732726 280830787 415934475 93081235 523698036 103330004 949401836 671049157 819137488 969869889 212892511 654456861 401822142 119994704 11717694 596309590 431676642 485876694 1041999132 998306690 802164184 311708734 730472635 50220421 194741933 86909449 872435605 93283738 562554723 1023435337 371219540 259041485 1010850417 446203942 997163098 1054025856 401862977 202919257 395724857 488112870 93507761 175291059 261957691 1252235 370093459 514558103 691003612 860562377 228464940 790286204 31142731 691467092 519380408 346556524 240051693 880816304 780970724 940563847 563878106 155404726 501174867 924666497 1014360670 105757714 514380826 300911903 611478393 106933704 237534020 540566974 55043168 963302826 408767055 242853837 235923705 97694691 592115629 591960654 881212771 833428080 36977220 210511961 407374444 335709602 820045294 884760984 202695192 235685022 383309817 539282124 453841953 209056220 312849320 304250439 401920626 278739883 219475632 979573872 879830442 30604459 343125437 707300418 541700511 110601298 1070788843 293931981 816269785 635465576 440701004 77435060 257283603 810676362 371034216 149518509 838960829 830793899 137598649 712018436 427514237 692219790 723494443 420365336 418606505 214330446 712739746 229638109 624732366 268361175 908300916 932372568 739093293 919335786 494295274 831034150 859640888 775877916 848559299 1060430069 268057 769391703 899553201 306908681 104750892 551091288 133827546 399706809 531154048 391944879 663625817 224752623 186863706 1069701059 839019962 510419884 871272882 668239691 805313154 157585793 15614388 101882070 678815652 220087063 736573504 183185475 1003457805 502860969 549564523 973082186 121595417 589848964 616979707 191219954 267841051 1005646990 98585839 350311448 912887002 216590524 299704308 992664047 831468302 356077978 363596529 724362106 304039655 199066566 614378621 457298195 232054918 81933686 665334115 343417576 313185922 514223854 882788645 63967609 572562021 924437258 762800758 326858267 880174380 687867835 663578558 203228024 602813387 288253569 450581402 1040993804 537695142 466246902 423507290 848241833 685227801 428741955 230034817 622901493 303565297 486784680 61090376 78419943 244817392 533179897 906742812 1020293709 56821581 801754652 651270683 119256393 587764018 613048460 1040049819 72413903 282620477 475794904 821642147 497228329 203737343 27510308 835676015 771293299 595748992 404255143 644669681 858372383 805795001 302182700 669097034 121585266 411815704 763227794 161429333 565570054 485118719 431357260 683157021 549076294 691987014 606702305 52602722 443382261 824689077 770383724 385190169 908102311 319145354 685534749 162151656 228047685 54185465 485602743 391920814 373834126 1063981991 896692496 168312568 312087953 163431470 372758420 953039757 187177524 739929756 954969538 254722020 268211632 57360372 306963885 474878888 30865938 316477355 1063653245 707833147 593853883 522042412 987503084 486471216 847905761 295589717 438330057 440459215 161076493 600810232 314021752 941770645 144254875 308796763 125363568 883993522 109148221 412868024 499972795 891006857 175813240 862191806 451794554 217313331 220342565 750544142 153741663 225224956 29679345 786364350 622724656 479995877 664968926 529223897 318579275 347640352 590243007 54648797 466150940 727480471 524948928 679733308 848661929 549567590 915179740 454479324 30054663 923190108 612261733 524333464 6409442 829062270 1054322048 889806268 254018297 462271620 918942374 595296908 502254239 414497370 572875300 199475902 418568507 990139296 214367131 84905979 502155977 583270698 296481665 1049646947 963949143 631018369 1011411870 737639942 741079689 1037700960 834829200 941174123 940119573 27910712 573638984 5042189 899055688 576349868 31388043 396991960 825134463 865941782 176619633 306845873 272468911 986045440 77052393 411818219 1048785629 101297324 410055220 38488531 592405926 197142413 665073253 975828517 516243897 295894219 775226599 684295317 253362264 470545603 735696375 672040007 500410075 624534661 356152358 1046448471 353109805 478868052 221226201 568629586 1017974861 767650345 637968584 63465402 1068789453 272654896 717020290 594993798 426769751 508358474 809574631 702418592 180389155 877504905 783709101 212776037 391794306 403521719 581947356 966482985 184549719 670490832 913550930 160897712 113956248 307684995 859430464 1008348598 375493585 345826229 980102570 979069032 222291361 43709437 115663339 580218857 737343036 365125929 909312046 457492430 223929063 74192824 433546742 778546850 467827583 554462047 277000600 750701154 248697586 24980356 660142780 420193538 796827588 775587781 53467872 458455271 646802572 429966450 298763732 1008422251 288823413 523255567 53523007 665641820 512141245 180962003 180359704 961671549 882467897 670018860 681319214 244723971 501042639 420045368 986963873 579385881 1045682938 916197709 380188262 821669981 282036554 915589491 701494215 565919585 741719521 460840420 598602209 1004693290 280786423 733485715 647653668 553883829 1026344791 820267170 18880727 276374125 203534560 1055720170 792346513 849145014 424164102 56973943 597124033 738887269 782133326 482528010 416705574 954237253 968226261 966590357 717850712 268410516 150006729 1072490178 934603070 239750020 281312750 1011717997 160287125 702836155 955726874 423396645 121390703 762576852 836932282 509183151 769230770 996244955 296786763 933601410 301119637 420946388 966704353 79969612 683954215 37908533 54238372 809111148 427764167 68162663 900193870 246340214 377777581 544279881 47559855 103550899 1051216223 962079149 214647337 1029482654 108001341 66671834 853461300 315547752 693345270 67777288 653831387 472921972 587064592 251923943 181682493 764659676 814254948 392204568 356379661 682355178 432248480 1071437490 1062507794 336472224 40761027 917914558 969533095 980551217 58289317 418231484 706698812 300978309 206127724 495286812 803876052 725960121 200561688 146875589 840034181 688736412 578938872 661136018 873367547 1057514804 439047986 302131920 858471670 961996087 681379391 941226689
197429959 196916370 943009132 863691292 646593494 685757925 960688475 594780042 767271199 562439941 994593664 269815083 174891697 198866296 238600868 359767311 700555310 849797885 733672294 383559102 170991950 211360258 677767349 976060081 281335387 998298156 755188823 721120470 643229878 328115411 936359781 635526927 483662673 714518914 632867532 196868787 477870899 793645691 60684237 1021868044 421421047 143368497 663818366 1015566040 257850445 1015581389 303462472 465351368 166772343 539047082 392375399 753623044 786219213 236089561 278895725 1056520101 347802170 641368733 354800319 546286649 536239805 349991664 1002499350 727219778 671866857 567948540 602825983 390056120 617184614 133798563 119482459 364141955 596653422 337778936 301203936 887484929 76784976 211606723 92426646 185015174 1599984 542453505 546182492 697080791 867487812 504899937 282083680 409796014 932304345 869645000 741468330 425656633 1001027916 903805902 839857554 857626779 755718866 774263615 343290437 78034026 588426416 864184988 157704516 544677935 347272131 149549719 605136357 802074345 363698170 79017882 907803856 502364041 467125463 1071744576 953844867 190964087 207100402 223076314 1050039759 153567501 283650934 955383532 734538841 470402071 890393250 255208366 945577754 131313241 192073289 740024460 955263199 579954185 452506450 310918822 806600905 802213968 338013497 193090128 663306957 65240525 239799948 225683346 293857334 790210322 214905198 728215209 837390366 822737189 208152600 206303365 261265401 868790785 408862035 707728202 763921419 254741778 667796735 427994831 206010348 337117116 48381072 408580385 855408395 530499029 807058315 631968513 13051176 912408102 696792077 546053218 100327129 667031279 437060421 796358892 626672134 958515808 580866549 797400188 1029377645 421849888 662979828 733575073 426083870 452018378 630586799 472775712 722671104 963654762 259943076 761590129 191909450 579538181 855271397 260200768 70920971 175078415 639152027 227222509 555822243 113932786 1014700673 749171981 151437384 839709326 76787813 325007335 524187778 380158387 216467626 954139639 751703470 575864744 827128520 473190766 296640127 557915560 808230602 59604400 1040730232 23843424 130162127 58433493 863498356 500029042 458904203 238202152 239788830 295891189 546519491 180907435 381728121 329896947 345912020 879968401 441216346 425871594 964530220 30191811 215005673 38710603 457668559 336648540 837024803 187940606 492868563 777755181 235741019 156743900 264475365 887987257 537346484 767770419 205191362 879207993 570240168 276798533 463617727 822919450 315432325 64605386 589939778 1040362618 122084843 799038569 428937030 479241007 57420879 878875203 74210523 593489856 464614523 380923241 1029636515 767250666 507205643 845705569 1063328342 315665948 69338866 903201444 1006275647 619682811 716204019 622138147 948393405 952676575 346067240 624975550 863153859 883927380 862031999 263452619 293370200 668621979 944931895 223208341 318013975 698253606 772146023 967706330 285118640 12009759 427808376 242754124 47171686 310288097 594870183 378511120 183359631 439527805 160240516 693840707 208829720 674365751 396583285 771892848 138923774 692005895 688024627 649092635 40559829 901528088 833106507 64002617 791331653 686733900 260392607 1062369718 677879176 4095670 599439587 1071980270 718628333 41169183 870075937 71019572 456666713 788248450 321915189 373985358 329701568 891414671 334398289 109519606 952735664 861278252 8393850 791318875 387727047 1047184367 482495497 1064245918 137061176 819005349 792803628 248552533 534072394 31474127 310182754 944664332 562770904 621707296 237556482 1034359487 1032869586 825625600 946276789 849259361 372823482 265375499 521030391 808996184 220947753 876480403 954586266 268081663 413224520 452709658 518498115 791555106 547700567 283862233 226492139 975033478 609479721 42985020 768351071 1062479454 656178853 323956579 651942081 182539223 637491015 1018210722 921769989 160717453 349117853 899505666 348157812 876609555 594616523 564156863 414079788 49880688 186386440 136831687 773014942 676675740 597218078 331480129 209256463 346885895 8530670 425769732 953946904 22711315 377782762 664234523 250154790 66756757 681510040 500924232 306193658 699103319 1029888534 197353342 129207850 441233049 473052304 407466854 377963934 62999179 310522316 822643675 833622036 221055957 18418591 25040493 152523933 305563408 827365493 843653602 47531294 642159178 844307404 812364464 1014388432 533135749 1046341305 1015572356 339217088 727987000 670976099 35941823 977995343 659320013 257347203 921126388 168885171 107972386 525948394 31119467 727507572 1002531592 319515387 715774368 1001717744 762600903 46332461 283246277 1066450904 809475480 963170442 724664892 463133872 177983017 297298994 246118430 367941715 177437 461282521 1040315062 525976685 607209097 148501572 13268743 614193919 912556408 595232464 45924674 665282271 77470824 166001644 988895569 551550005 383779275 883715738 455374671 677052671 577674375 62365170 116570125 656442765 84931702 327216542 320545167 275442950 139172582 441562719 213940108 585426402 749561626 227010183 145022962 837595757 1023443655 248607357 980277088 919781707 697583256 560895292 333641130 706221550 729310891 661938388 741114456 615579937 801009426 654647016 790092071 155429249 180064339 395903278 340795015 895935486 860273640 926491122 514212891 988077151 100044992 666850451 592108860 553192891 275191740 337167877 420529015 764578561 611569715 495250765 799935242 915380081 863669358 282283016 788154219 990088993 832347692 598212324 506306497 74489721 16503583 968269349 858010472 269373366 620511597 839314978 161173106 186731 1032119345 1009868741 577924641 346607867 171771895 899735823 719951213 768351777 902825795 248675729 199651716 334120040 690607883 949243636 19648069 158563251 649651001 424131955 950196933 604543158 766294826 169807963 965983691 767477115 624430641 476040850 334133843 240814559 265320468 648081165 393454606 1016407058 107617678 436853080 320824287 928461082 1002346700 529970706 473844832 117220689 126367216 1028886382 499416668 110367970 969113489 60801459 797351250 891046992 904731449 40647612 897324024 248002799 373814757 108695418 117352630 775594345 387170440 513888877 503898663 902409787 165067913 688279087 242793371 12403253 278288449 677511401 88942999 479175421 555424638 557870555 266858068 170652044 271541250 1060978137 726384188 120582832 618623492 38252489 459158640 522954632 867779758 870373670 170301253 81901068 34457245 609924735 789507266 864297346 825150053 807078904 1042341668 402313994 833672971 215487944 525037914 35385875 1051313288 517671098 765232009 502402275 552773709 373187245 1049012105 888705299 979734969 338627348 823936358 928879632 421435044 405521270 89329632 222391196 314322904 893741038 994232555 804591179 664724883 257884076 979621424 188544007 774425607 543989107 13772170 646827660 100519898 95817753 445309322 374387180 323277478 353624842 548238835 891196684 31823737 976236229 12215359 621007397 281771862 466139485 198600728 415133508 622925234 149677818 235236320 620574411 630648056 775584342 762301738 430088174 496716550 321332544 295596350 587368246 681682350 523692316 314321305 857945858 626913078 658524001 819423339 855326721 822489816 44876313 320783639 1001726393 714309954 683060325 253972662 401425154 1040166167 363514615 941144725 217070220 931616621 942163093 907330738 738125653 518507597 643785373 625838147 730519860 446869302 458432891 1029540399 142018897 456783770 1008242997 8363922 794452650 242302303 622233056 852566589 767302288 445601119 1061525544 428963124 727079208 563920361 493974988 39934255 726970859 212032318 561283615 310677786 362081318 519013397 696272520 505468565 132553594 290479639 89404163 125607540 793544797 894765667 864267934 641871168 691660952 546349580 649295869 918322100 752084935 534184598 316233174 286812993 1010008027 847211132 41883510 681921163 497099163 228648365 872375610 320121321 484060447 659950090 1053253911 398065641 340474452 167478250 9738002 113909193 1045737851 795898519 314162632 412972031 243839914 609424590 123225832 351020723 317346633 860308802 782581684 34730559 489659542 405849882 606568836 474767286 872443426 997614190 603468355 351914330 204874065 893407438 671225072 433893156 169706206 414742972 222407197 609770304 179575637 122355501 17145972 280024719 887703447 199662092 909055277 1028566307 316580185 1044104886 577807513 838501062 858306470 771539327 59755163 253818740 302847832 371053355 748819241 84761564 180593571 404024694 458332879 321893859 280346251 1058674573 353951532 257561889 817873256 191441555 210001780 889141090 443467113 92102173 242355436 1014299942 826522638 424977590 928287601 976301601 636442541 967825499 812499441 101617083 395690990 189871872 890387184 713572242 1024273998 406662922 535385349 469466099 370974368 184187858 2835291 937890917 616505223 835719721 920903216 204261406 778024702 168385742 472826713 642771084 85700304 322062586 746276540 716525006 419671328 710517461 1036661460 870652728 291085539 760136190 1022286129 969397202 768665185 635766278 852292341 15285977 802125751 1026564853 295457112 297180220 195829080 918994372 170221093 935274784 569551495 872470754 688057403 150238301 10351071 1060671664 1004623886 887685888 744132043 520792068 1052801059 471024839 835385614 831906985 288382359 789174439 1052669756 263797725 865330328 365306185 58314047 945278674 207590634 518236553 468928980 60176174 895177315 920606966 17964555 505029515 283041136 660142165 32507338 206324728 655729550 508626462 85573707 899090038 188506065 1030511357 298604697 933634940 148966241 825138769 557268503 27851379 421895672 272599729 935111929 932101690 536649318 44663394 103900873 491385251 829063949 823587810 320420579 168768500 516317797 1007980129 737009401 596991336 200864633 995313219 509089681 559115180 213704296 81996191 963883138 398769762 165633253 1014465731 386876794 195371937 780053175 715577005 753556091 221459570 491505209 472323475 636863577 460259668 768213211 152191836 60186942 257625786 831381408 69423653 115450150 255566216 25021342 838326462 568319587 165075865 319984257 139368234 818513434 968173628 362297097 357190434 994840772 811694259 392827271 246207634 1036307119 698798259 859291748 689711642 981658746 651469542 88238233 928980367 319325084 301661548 681264696 295694456 692693726 690685525 1013484770 78166161 149689052 834357289 824252495 153588811 411556488 864046688 500001993 49000266 317044647 1007849962 491227057 136713958 138604370 705508777 863895545 816504491 663494262 4952818 984446632 757994713 262296149 19731984 413685593 646481636 680915203 298937024 1007741116 619861492 82538985 626718902 563883283 1061641062 181986885 808300567 558928566 306502986 629526952 590358012 63435920 1070174948 1045189239 789217526 527133344 907540779 1039637099 258487684 1035528825 1058174797 369506065 506696351 142555075 394154792 300362315 786210350 1058972856 239302098 809325261 831734162 868917927 732561426 68887712 512312860 281518708 547303141 508015010 691216786 632046869 1039044602 1048183300 998707886 1017240599 864585271 211565771 960368030 933411351 398335538 436871248 185759877 901534538 914502328 718392000 838809592 5025269 682287433 116576924 579046274 4530933 858705561 329133882 669006369 996699705 778517265 880374082 257330887 428543811 894429005 886623026 460039386 836008363 482756764 956590555 1059423412 536647068 852004227 930520289 558665764 562991189 96072249 974868287 665534187 992476329 865854764 663736257 172829503 632734591 22346619 342092168 784461388 62645331 971715962 475647114 190336174 512361907 365499186 61163023 308523768 730256834 704248030 539707701 628589104 426261177 527065966 180668269 279653456 628577121 841641224 410736891 232136903 953075610 950673794 466236794 265521398 228321496 855515882 769653846 364827828 475832992 572235262 1071369552 104240842 287488783 655953588 873410813 312193399 147874644 712037555 1061114184 575623918 375035953 188553176 299925995 100057555 268980861 377224370 156997882 850917825 615647141 105687302 692688728 91953095 956496423 154146893 481763648 237704935 213375509 290078769 1063372478 586374293 668906904 731874579 788077619 998413630 270121323 525893255 610214612 340385982 98189660 352095190 350683435 431640297 161888462 96024699 462916501 461941763 693390137 849014952 711466178 132881736 357360808 600835518 58900025 786107749 1036714554 803930840 981639377 223471868 941347491 186569025 1035363641 545991460 735913640 511749369 660419697 21379559 138457510 659056948 384346190 117641922 21535243 504235226 306021370 860145449 353032667 638488328 787561586 617498881 418180908 73816974 59461894 317097763 250109099 525633391 549843932 278288864 46627349 91966821 315359854 401031031 795317439 1025288794 712822279 489023648 737632271 459231728 245806154 706778373 557299200 596210425 357337003 23576516 112928674 776293376 618809332 160275439 673635735 417140670 495758018 6742283 846284951 1014962598 174355461 910747540 153297389 762999386 447913603 290198904 597146616 41952307 590599254 411835031 842769067 602136509 659896169 123993418 198020109 584773688 712473087 682784473 580819129 414941208 153798444 974626819 30532703 239119750 443874138 389442937 312141378 717549278 420097221 754089059 696361401 730154799 345179135 884059866 463382190 585190077 719971437 933075053 467427873 1067119490 156853449 434092701 540556965 471090601 903845790 769954144 251696354 361972753 544023503 261844897 873884690 729756881 1008938256 129149886 1043073669 648132014 546638954 920493065 67589661 140877990 856316092 152101704 297665745 35143785 397983541 818023734 1039801646 875123930 722152411 707427071 120932050 896133010 48054791 109256647 956099312 575500382 935109862 1061752100 422520015 875088316 908693498 293261215 490570314 544470370 399851415 551033656 661328977 503991 82061670 589580255 202100582 1046436184 489391334 325197307 516373538 282632596 695444454 756642534 131463086 905090288 347478796 798070127 557974602 1015999652 761215568 689244759 472476105 321893404 780916098 170957013 771368466 524008824 290184384 15836947 95776161 473556493 635553025 472508078 154024964 51555041 889274509 917098809 440972383 961678643 688899971 713520315 607932905 140920561 1063645266 207097900 819030124 484233023 25925695 779386876 94565577 229125879 109009893 741800589 157171058 727393572 1005379504 1027251379 822166253 392928134 930408546 278906427 891093080 594570001 266912655 809879138 253066207 946008173 1049362464 739170393 1046292296 98496631 139851475 220164040 364712040 962645183 791487161 287167815 277701035 1032325128 724289975 762450662 804795023 22452939 735933701 445034663 540715049 124786613 562018738 654885119 635725216 1029218340 239292703 321207641 320162989 448276654 529072511 869085843 79695393 144182682 254137950 502447486 669649503 279181157 211691799 432691042 115999198 342363966 778762587 504001144 514397608 211059594 724899249 321611374 1004607453 272292961 454661105 514206951 543140913 604872719 15014344 909733368 809711721 295880596 458782007 992042156 658318562 112263972 1046742291 492823425 365915403 1012059816 879554951 116760808 646938598 641881659 663270541 254325705 727969931 706521774 314503801 901666813 851801764 513951237 994648687 641684179 620674802 317972472 835946215 53817228 694979527 500470386 465368624 963464158 331261322 887770645 72545002 456438900 422910774 201039540 907613323 60641644 232968923 1009926103 469909467 28861144 703392284 861503803 716517239 198855998 382297775 723450704 298372178 987313688 75577056 676402105 889673263 223244373 116392462 35803600 766270505 852670678 990005549 828670751 329647404 524534513 871782210 667856871 248785017 637506802 815596010 792158109 810038821 489010325 412760531 282537320 327577498 148480909 27388737 76164261 130281493 243182592 1018867339 671980899 19432742 805043464 729663643 1044476135 302995252 251139892 492174194 912596521 742613494 941590789 884975265 996034133 708951291 912161650 344569809 183511371 544945187 773918308 353758013 352578079 915484707 10061115 26631218 585147290 144174853 922370887 491742614 108285111 273943717 901126223 819483230 294284583 377445174 935648526 526016022 353509838 738298811 299753393 63898973 677245251 725067406 1035706458 373630566 945844308 19911645 760962464 421130616 518960768 1055454248 641364236 238954863 33628795 848595140 614005662 880129081 988802733 148368475 112845382 211090265 95851955 906451817 2169452 650255464 942868188 661376192 349521512 934734223 23341742 1014897158 480125450 905787919 816527199 137033778 239550228 1060276921 84661596 437239826 316379579 88469110 74093510 263980744 552226090 62344896 449817839 770836040 532844542 1020918822 27532001 31839708 314073291 1058148044 787676120 175927968 207551125 840439529 212453059 697178118 701294936 741547336 936890311 488958036 366638721 260010952 133045436 12313889 341927283 791172572 503318958 377599963 360644611 1018026251 1006878045 412469828 282161916 1025486192 605023677 306818800 683178652 107064891 1067283575 23189960 362176277 73941551 248001382 1062414475 420462860 108661794 529352987 847690568 961230365 342911872 218895706 127212773 70301014 200625352 113610138 847985563 447402935 96881165 534667657 941994359 65392825 49388407 643428229 1058364634 143618756 572053440 39880996 691751162 370684855 481133751 494634926 887875168 703806820 204896192 299249822 640455528 81016337 931661394 561900068 938833092 636574968 671942263 899792805 359669241 239269575 117415760 634566202 456657376 197331489 44853647 121958701 547119910 212823068 1001512954 67970687 148577485 985963713 977379311 979559269 476535464 511964047 727611867 601825478 707013091 175053816 639390145 79538110 816286073 239821282 954388409 589022751 259670716 845041191 1051353198 104354539 5542353 984584982 1010664863 1035240154 409181745 843794672 91911839 819236058 293880617 1048345196 713953493 901586570 461842522 974192947 758814781 817209535 896346682 412791396 1041418213 996658175 246059665 296409873 28979825 337513736 811933949 336956609 506032791 352729418 783639407 20068844 266808228 862950249 568581804 806888066 122706421 118202300 665650892 954306660 231797631 422430929 746522558 132932585 858183751 1007342567 1018781123 957673563 44307178 704259441 502087150 989603959 7039255 750081434 807358122 977574640 783334416 211260604 386215988 349388525 452704557 132014055 726029597 353177734 862247513 300451168 868035274 890993995 601274003 444102944 649368051 707240126 995009133 485521745 858498855 933187796 421208209 932512468 303127366 175078007 572334647 181376446 528964614 474566151 1040684976 543705558 1008880751 517880788 480202975 449491736 908512607 790872230 49950138 742626869 986568199 277807670 549592781 373484817 260070507 811187122 762443191 815381316 320523750 817691196 227870124 951792282 120215459 1010116971 791537 687679379 556793638 549547977 323393635 399922659 601590465 857824084 579390960 522220787 5421599 974609918 455447324 190192734 1063964349 564632108 163912318 316012661 854287467 911802170 799009601 354307771 785226192 678639094 532689315 571495018 176064739 390159648 608427897 154126572 706416499 609129969 731454633 820117091 263481248 246046865 1036027822 900598306 881463391 371476638 965559832 293430065 709985786 646898092 434398473 182142157 74500750 184423360 50071994 741696229 155106955 688469972 396194292 52063903 725961016 67601495 375604375 662432465 176214316 139741609 1056616982 183324808 1033766102 512458403 1063412984 266568580 591327990 113909005 690635353 687249082 993194785 1005735462 783710823 2089169 129949249 518383392 679176422 637132965 920164114 700986785 574571948 151122375 325608103 725687363 811279654 886558971 1049006307 163053333 217762001 427618489 817952000 244744216 1029291969 445914541 55815692 965381058 1057445662 648213303 24067942 465679743 1025792674 374382571 24508742 992732203 228828445 329742866 104476978 1035718297 914981105 156296231 675498634 480626703 992893078 433783130 117935869 530570440 830027543 519453201 36886289 539147888 522557587 817008738 987693727 346554540 520129213 885245083 484098389 602744207 237509980 901728699 803613490 3144230 21897931 39553525 821176590 175129325 32817274 347339572 862170383 1034991703 330387308 25232273 172964661 573952843 23694519 794963423 968737231 147188129 848763399 370519584 803783171 233347753 142954012 96318989 108742730 623446948 59757895 907843986 198456561 743666761 811966961 500712272 339956890 112556866 491269395 297302297 323569849 6283948 390727359 736456823 1020968983 962921627 797980310 992654117 782106451 421076883 143748176 976638869 556382556 156431120 727023671 248967528 558413816 967420927 616088492 289246713 288773184 716742979 715563425 457093331 836747041 22831153 157224733 529456182 874912220 569477395 414370747 151376278 303718023 328924073 960754219 568043036 809539723 729306020 432494767 49096483 114191652 1072674089 71614879 183963323 317453284 602335572 861133798 500729898 267575088 705055410 794825603 735249510 950990017 804749766 870724105 13262493 278779428 833098117 481611552 461557933 892279098 612742106 455938306 216250284 923119801 448792099 864107774 523741281 993273002 780830130 32937976 90788809 612440809 895048781 136582886 306527124 77868967 992115886 36855637 935048869 361143787 94211843 68917218 236832149 981809165 528854383 518883522 593377072 162345018 735539335 235310138 307436790 486453491 17845206 743952168 569610140 732611982 208747098 832790904 748209033 727061171 1027390213 935204527 255716697 961961696 938876221 131085924 549484125 200469222 296000860 798031042 824148249 732240490 319836465 512486152 280837573 878341221 67298429 190670857 530288332 514802596 1049208182 552906924 614563152 288653128 171073863 869406829 752123300 967467846 1062015119 1061755354 849249233 776360169 841831390 717109014 218884114 384651084 644202555 384281178 654875480 511140832 168721312 856680047 1051012038 737000172 956148092 441444149 743545142 600645639 135210800 953471520 841120178 826492576 408885395 958326453 319581692 393208439 847987822 960282385 841377286 178491426 703906048 135487587 971650427 295964041 134049915 714447725 192116788 786842218 1061768582 688667910 901662404 298948821 654215097 609095323 887831277 268477873 1040609316 856139434 964412456 645833013 910865864 116689221 932334625 50966384 133689884 438605973 1043606328 357660866 213616010 607638869 378105090 674730593 587678703 396455763 723150021 51394261 424440094 652584434 923996672 316755579 557780318 299661482 1031886049 463620102 186020328 988620678 143880909 830292217 147471722 72582053 819620571 973995567 961876102 895258555 747280985 899789907 1005787731 665251981 649670982 276373608 191067355 1013099896 513636054 1006989379 556061083 429113578 248503793 271252236 549090823 793639143 478996917 880724416 182978563 83404677 250667503 294219698 955591275 244065137 238802854 168047365 535390604 164894824 722401680 1008403763 466548649 598517695 766294170 179063690 49428855 625301724 758889573 780629930 18948769 694016442 788670404 263024648 988635717 428445545 229256511 647186542 954687348 862877323 679441299 626936440 451184054 369152984 447597103 690376217 322658692 382448795 981806520 859136532 704875724 522764083 548904070 709280899 139979633 293950355 932690725 600353620 194262984 916454338 307972309 890985670 546791196 852044891 207152139 214931441 654356011 52745486 810163949 334089531 477351335 48644382 663413722 387950308 265555638 949340130 827828704 941187451 478709618 726322500 571504964 649098342 767098730 1072763460 712392701 573573726 160410655 512087413 652998201 43469297 611925383 525747071 918000343 164982270 1013168781 4503452 457199595 1024175676 1006611855 570641436 525287229 97449908 637477087 223787745 105885386 459535682 139914051 5639650 59694402 872605720 930925686 61480876 964460168 1041616955 296311204 130968541 15274038 561538308 169261553 172863400 944340502 146300321 1010905843 50944596 452007594 844466577 120030515 426790332 542691236 167917867 814323888 566619856 593058414 165770776 271186268 576652818 292358308 600378324 51159966 551776283 569573525 847405105 649601230 931765780 359252422 855972820 477426620 845080125 1018296687 96346806 344773929 880714857 139437820 936074404 562872396 626502271 531107982 339496384 327339854 636190971 4360055 1028849406 457107407 235730796 621313217 230831783 898873183 832537843 897869223 32571609 513114117 769390794 1025798170 691505157 215659708 1049230011 712476478 522108272 884729329 457431972 376416234 211964339 328367622 481768954 329188652 829455675 50023890 702733890 92044483 891853001 336914719 760718234 1067277219 10290675 851399466 309846062 754741876 521234337 282917671 179886532 1060436499 662416017 428968122 450982449 633554960 767778260 746879103 810100705 222778158 1006787407 555550851 1042081362 650250215 331628603 298251465 580396697 920120549 927413669 791446470 340418525 755832713 985336046 461234917 391333847 50950248 495031372 229266179 984048472 601212873 728692551 1017423092 491382467 454933033 638033725 312509949 999450255 208594103 902078431 676666455 74012614 846719448 592436145 138048435 915038344 642401700 415562894 969554352 96565385 781840999 720419874 348211815 137189774 385572129 714374254 475925728 729759732 254159367 1033941064 580951961 842693418 305416447 8000472 864802054 955436594 367024680 792081692 140673036 59711524 29844048 383568997 49090693 311000234 782847867 245884119 817004479 2843781 765939043 960713965 373067005 634547719 394586610 235669235 39406069 153925015 602311114 710087050 693499728 293314096 143961278 714711079 138555693 80863714 548897367 198421396 271707038 223605328 471584336 346456686 427310889 108570928 913120537 111845798 518784328 306825422 914114648 397008128 19219690 916507785 897174371 853530519 297725680 40569173 775481287 37342294 647260848 988290615 342825412 1066935936 889483893 283620556 871619791 235727402 892289022 504172994 402702351 454782140 221710587 705525085 980437729 133782899 75549587 938363892 989868372 449748450 1056074464 457846385 512776365 938895980 3382129 361411285 375434212 591024844 921673671 992775345 257277989 152633997 269636825 553647534 154454352 268654994 302616208 291771911 904158841 832165007 476235 160220425 548277865 468764046 87788893 1052686746 494814235 449731692 672951690 730862255 2128704 149520217 94335373 623534036 461718716 153908060 343743381 948466088 150805287 133354700 812621764 263617118 930875212 72048599 762540207 521403965 47649965 557091071 856071136 445682721 319165949 1054959000 527038039 854652408 56703396 469034060 853481732 453534021 300215871 1053087128 48966990 352176033 376280862 647611468 898861456 126570293 33231044 82615822 77700503 456794946 636388714 1051306967 148811558 531076249 55284092 896490101 223864434 952306211 569849883 416043784 714779301 336413018 804824986 1065542533 704138847 634969805 683265537 147240757 818023472 780783264 71613836 92135223 864899872 131593482 780689708 696265466 829383464 973844182 110264581 81219780 927021494 423633379 634754799 83813934 719146541 715251108 795112182 1042622630 509550178 296700832 657731546 1013552619 728075040 91910130 291305359 488526996 374408357 233109962 425105342 805760138 964921122 149136363 20833858 546885513 950167359 935191851 420476332 658289059 1003646613 340586742 1038784960 42709437 855394354 775555019 558971893 949113360 554351897 272865213 409337849 537739433 791265472 762817780 858667051 833449962 134761872 376910378 466725407 559152903 991269224 917799214 1037640477 1062531721 667216409 431309668 896556194 565591247 818557419 944775747 111423709 359601800 928766999 233654229 480517940 397059898 510812492 902311739 285352125 386104766 369589291 271402279 988859589 1019730113 777467338 800839776 109432140 1043808068 857817653 245652033 334996359 902031645 249900264 199814970 518044765 72447860 908416342 815779661 763090155 980811080 447036261 1026455186 132525824 163076071 648846319 1049535924 928978337 1037260665 4414787 730509938 227029382 1039316854 343067554 167749663 866430363 368338731 713565634 471611426 31042432 128393785 1062336847 362904183 510560265 604887318 677367653 421625388 621637566 748415371 1061431575 1027713509 369115997 1014441780 349424619 435743832 225758292 968307714 744808028 500153554 45793607 245803196 1057969239 723610544 260250256 721423738 116239294 1029292775 1059174073 221422121 308050152 372831868 634081028 329086730 523846430 856581388 1071070180 366073139 1042624800 167618630 419334529 97810188 1036158366 255587692 1000201272 425365715 502623167 38751702 670082328 990652697 186880926 55672687 324511335 63160642 561389256 808187190 798214171 1003212297 941087935 165435326 973585505 606306298 879974266 565280174 318370841 129588214 628633571 244034625 483451736 347087795 651577944 706652103 592811493 1033571897 205540138 372118563 183767996 583028838 346710817 164767051 133830031 56096106 629828597 649240523 500533568 919242572 236508375 373958978 643393127 771065699 311484134 791079140 553079506 1013331678 1064118714 572946422 168138496 698068797 78483421 800662101 972776101 172509910 420631373 623081199 212984106 563076433 626825723 565749832 279191082 172506155 932297295 606125303 1043347958 674830135 1043847074 529797159 919957010 559685912 194399938 421339670 208921013 522029001 553185906 215562393 277859917 396016917 32151527 456576918 730756088 518262559 259715916 1043782024 1006067212 3838172 729367615 111955967 1035138960 525521556 599315026 561746973 961376193 563243620 625785227 618372891 993259151 525388991 936117988 630555330 318052637 488109288 9381067 340015602 444819012 216259962 233838499 580110622 91308816 392317152 713755202 813936333 942933825 758307293 947858033 27567131 660847052 539458565 346805615 978922806 1056515416 75766850 32707694 622229986 294599873 440283473 477817108 1067619829 262426521 1044255810 350743035 274196956 114724513 597502203 866299698 56560404 690511956 350738102 605425338 267836594 473662813 1029394558 133081353 632094683 278334748 975646134 307905931 564302924 551655973 867062418 726204188 197806292 958691009 1052977308 447561871 472464341 101382507 99395376 1002148138 135670727 740407636 983673857 942289191 393869237 119083743 244130706 191989301 34533310 822246438 885653949 235689973 346158485 294627699 723946031 146136190 508718337 894927304 190998762 262968538 634453085 756081496 611228354 636582278 647994649 886355979 464561633 679900917 374635576 593451518 373072451 28326413 836053712 558680064 706449978 607407273 312188557 677161494 394726123 245072406 200376879 179381752 170568911 376484758 271898119 34374547 576973876 998198496 504619134 118792581 109259193 51783838 902753933 814823843 1007262421 457522413 377054278 447411574 149684817 102668257 53976394 372036282 483342537 217525246 276864337 532994014 38503727 1000697024 962433189 524392583 405488968 599866132 1017715879 785713676 313091629 669295068 38797385 710060027 78851275 250372719 143721618 107964563 824856164 523686167 423410973 805437768 606001420 31687058 116824218 860191555 336981036 773211025 846381387 722671583 189022467 473034556 397954440 942245165 416416544 18710956 593510460 6808176 169441512 293669231 265607526 906925218 736492566 218587912 177452698 654437101 330646070 295454060 560644989 335975219 821523754 917380742 935033420 268754567 642653094 812498868 62420053 658855345 718098867 990698056 329665148 246586798 859492655 234867719 454837687 454798381 592333387 389856173 138600339 7261203 116493324 1048348008 554996397 419262968 327220427 813299545 681507642 884629672 822665909 841997846 205539199 813407651 193657931 1008558378 417986650 356038046 741828835 495103891 945713591 1061835008 447963429 664960067 913431323 229349477 106151823 553667232 239849501 423291166 929093874 10685188 1067802856 871815599 139699442 827524925 738747067 809537104 655963786 484089614 1007849577 807132525 508462214 1061541037 213023449 1013826598 646185479 35858755 610847111 607988431 1064994563 532859247 814205697 603224432 291965122 242649539 175461738 345898054 372154978 869544774 82310907 589764673 178875732 535863280 19396221 262164356 669002204 279226161 206578640 880350697 609236885 1019927146 76445800 365327738 1025957355 662638961 106956746 947651321 126084255 996165394 567754771 28516953 163118150 768460169 399899250 501422914 478770891 707437321 525425577 807992721 342609896 85659192 848266383 159438293 851936689 935684785 610964113 671756755 523714825 588365185 1032646701 1044870403 684052011 451570090 565343606 39451921 254895395 964410531 1021991059 88643165 338248274 980699861 953577023 305807484 344985325 507780128 971520586 364364469 700029310 358459476 614813718 216862852 313187938 863314873 719586075 1021804058 626843721 717298567 554559332 836093147 133681338 255451758 459055632 105502687 840468620 567856400 320735699 846628977 906842222 601603714 334534514 594672275 303397216 838829262 822421066 443705720 161629495 667256180 39716041 336673801 110599965 179288549 705778931 931850593 42738703 1031994374 562314463 234564944 940014429 998515379 246474551 27430108 465764141 465366585 560026555 622963387 501888249 473351387 947025855 45935579 861640204 893271886 252915369 865627098 652683273 883033405 839154292 1056653710 848192869 552761797 1020826672 26186622 549746151 616642554 523586687 480345191 900708143 31645537 705739801 761020344 543692076 212742260 619955273 202395158 876065444 792394017 725213038 326048217 702144945 883118411 290341243 801880973 683437118 474228551 301058167 911992434 406793358 888904800 57916669 74820861 955545013 6959444 351756989 651400533 98487325 506577621 330422522 147914198 498429442 1060525577 942230283 732582289 874490870 551499018 997683418 633277642 183931231 273963878 881221479 701567352 864541940 901722784 1028827462 373541833 399460675 663559854 539774748 207365788 196945198 95181433 217219110 260132869 645151849 483173472 374975155 746376653 596086781 295778997 925260965 683237871 205348553 337455166 527332339 965033755 684523004 448258229 165322538 55512375 966787484 631811401 417770984 552123865 949171458 170551579 1008677216 851783886 573825883 96046530 493022425 909748375 117567529 424939463 371332654 616402663 615432128 750422825 748742223 455772454 123629513 967819226 422771134 150691056 854024131 1060560448 327057684 663594135 336595325 1020699574 666780026 962614173 970172829 903366409 335275312 290786107 379402268 1015330043 760454153 569360093 160084167 90741955 221613036 345286819 799812543 43207818 111284565 684396001 1027819002 114548208 594268115 461231008 520313281 821899909 695669383 372663067 592643888 522436688 670825643 644013635 730434745 702361164 214010377 1016243260 623996832 662880486 23388031 867640798 189101184 929928832 277932930 543361588 796125125 356201457 323278487 671916800 190625329 873029891 638698460 541733173 433182040 565728499 643490173 907409788 941030435 841626357 932464960 487205040 253832016 847500973 277131514 111478881 81331696 611020983 277211927 562430805 895023592 21525280 482457366 548272642 875247728 92687851 91611658 180348693 361725591 64027533 858765082 289526767 1068707262 5692784 470925313 802823458 66728984 336062580 17683855 328402680 3654961 399909226 858292263 169320941 133259876 402057623 549070912 955612976 362754914 253729591 715757284 484095270 65711794 701068792 28493363 282702823 250581548 292412282 195166689 497412543 494676861 1070193621 278353843 282310574 307261606 437948947 809621510 471545321 626878588 341987506 522528329 1016449111 84370218 480321060 735467902 704512788 1063486122 236781903 205204669 233955057 863671120 748396045 852361137 53493234 176567360 665133484 735586072 484097998 959598578 633667439 45583687 901047923 148628661 398818572 790274724 123931263 684924201 334892844 172072491 162373577 127547588 963085806 205557225 431835606 874824782 455838052 289093508 694009956 119022180 865527316 648595633 909870050 336389113 528394616 546461628 153575926 583823569 561811070 919712772 1028737526 814907396 757742089 710182525 260895087 961372289 979650415 844775980 898615458 148640136 545826041 833774766 1026604801 340863790 968376422 872416945 866801591 456136413 236225384 855129209 349572637 279877586 117645350 597837405 41060933 217392029 711503288 194384199 56567155 106728101 502174894 507447096 182206111 313618593 843008905 572141506 130932469 812684576 910582591 502636683 1006186069 403401730 309519292 238206417 457521108 354551292 737441884 570673888 855375416 667535640 268266610 11389598 419946624 768080178 654505925 382185472 590794330 332599421 804936461 729472658 645418154 248965116 60574842 1036090099 1042074122 489566217 530789421 698846038 454574916 266778834 973846717 361588738 457160666 469797591 475208628 660831187 680226431 867028845 112944655 32199863 542280091 663849278 461726914 167445553 43183051 268573894 305493297 867815386 690515039 1044883672 852664760 400503259 118643674 903556887 421826084 284600693 800217206 766020733 1073132599 547183481 638317213 424591831 341045288 482411216 872653168 979110983 281763105 618901748 161580868 965955009 548209088 525819508 609125920 136824207 189516950 1048660852 1041671232 150935757 658202795 236433451 82231446 32647917 361902584 140787044 432904004 352962101 86569451 864087294 406623778 29496380 1037618151 110797420 625475902 776529520 868184513 389094197 115664727 951963283 578484292 240398196 53077602 275941177 812286893 635920985 126894085 388738123 435274800 769573543 406044191 173982600 615793266 427924276 118646590 879924479 450427917 346616684 860455718 637686678 239554575 553574350 274526033 924390790 602553211 994091630 896385897 276077788 653125062 142416753 880985552 1019572218 604044635 190122388 969060377 32293396 210953240 557554341 850838412 37628851 571911119 129289224 1032465830 633320245 692085446 697801524 541768855 191472971 625389623 877495859 136799170 40189306 455164113 890330150 280072256 189669019 483033909 1043258815 320654685 561191771 478131321 340110789 1031649562 202591932 134102184 595988883 839698601 933233810 734419776 1022591385 778198260 385774086 509256627 463636953 985245463 214122006 864012776 838498923 556817633 477518355 930823863 1056106490 755383639 600975906 844504175 727186501 836494641 469892540 857400148 788829855 452260699 585357358 588514841 1042922607 41319797 205981977 554878571 1049057713 279434323 992875763 614785382 78664051 590518398 51178884 694029341 424238681 1013063345 285801066 571621398 105431833 979575901 490303894 873945036 741886720 377869349 602505165 981891884 527538795 746232419 651378983 293166104 224612175 160811425 912656787 692863719 701133233 67866401 50429266 568224482 603501614 439629654 909539703 768519880 605062261 432554600 336153710 1035994444 273116104 254003380 607141489 865586578 438517631 1015230282 592636436 498789302 331161989 424062061 1011508411 978433349 218157273 422517782 157497118 42413505 954845710 1000318065 496674252 1036489505 449263563 584985183 367085989 486586959 997864267 860984818 844691551 501463976 649417950 985884404 932478210 908193664 809342055 530454881 400138348 112212635 19528156 405854696 610369998 386181813 757243337 703105646 110444332 408445691 262371789 815306379 22080993 820271248 825723164 766711818 975299353 254140169 884979963 529419117 176671829 85624049 212576583 547378280 422877162 730021958 943602926 247681633 994913666 220359417 147618420 980567286 497415834 435916658 788315248 504021111 906442498 580257034 268972557 487322216 1013626209 456776847 586821513 190281216 742175662 657464516 367972025 1013971117 228243384 738676446 995417987 448441997 110371743 751557384 1059924066 113219318 879435352 760132832 608925414 1047007472 215206957 492984312 160596017 205471669 120837947 203068502 926650748 1051868984 232966130 588163828 873336976 659564699 929705369 697711168 581258317 571139767 130455239 269220509 648879398 611670680 967170539 51071712 304469410 352636927 262581701 112430293 446628573 709935582 765170154 434426296 377257221 307424991 969475908 562124476 36816862 564477406 102996111 464310663 226935614 180810346 26489566 453905587 819178386 492155208 825511444 168711246 172255831 223597808 831448427 907424347 51656354 40079885 1071824881 584285008 1020429720 789310465 190777605 628271766 111201014 804452704 241613023 132517644 443615627 857864304 801918213 874465157 575189945 658813871 739659991 659656517 92134392 854079053 112997892 758471303 1039775059 867979438 57146642 591479546 897016809 97643753 657796570 66044991 717430125 316388171 32645130 972933229 519838118 695238357 1063130018 1000932493 181588719 474325434 7018871 770876703 466261688 695630306 1014877106 266095251 964158980 700274026 715839058 766137808 314648041 129443617 855232422 472057009 857710612 1059293965 665182420 1003445891 534696770 606378724 106544725 70807688 1029313479 847024787 24375414 388749943 1010924555 617694394 289631193 469150458 248851720 334126894 222984690 581569582 640147149 502300534 226324875 257441830 928956670 363763534 327237440 223735145 149990226 970105127 1005436419 175651696 132521491 875340965 932044697 978861865 622465698 552373024 211559707 563099510 981015537 501662755 537356150 687610286 943904519 567261680 112095212 956001819 440871807 461313531 514056336 481098875 623467529 422499690 812313806 758368383 731801319 934882715 406446561 83123791 464270961 433832094 926449499 987000580 334242194 662086071 750755745 628899116 13220937 348793309 396144748 647453002 29423658 834247741 525138761 1041280595 379622618 17504952 88030745 626482738 348774550 396749409 1041666962 849014341 611272876 64129024 317074365 68043741 97892864 1014795410 175395958 858124482 513003912 410149318 444092911 265801645 248700113 228705921 551290668 601616588 244132472 945562459 620490376 1038964290 315632306 714485537 551871023 84377765 989487044 52716369 311866530 329894782 100408972 217923744 356784439 454269388 261660406 645653367 43015319 243782273 363158663 815392882 466709821 378187011 88590038 104145120 995013629 203541932 272220686 994940741 226671739 1008087626 168130414 608461787 307801520 842165920 222819785 622579981 644747881 209860836 686825990 146395131 341078471 378783295 360642465 539376889 768325568 750253904 843487528 701101071 755527068 658560169 179089598 11515259 502284921 230841168 593993884 331733546 257647559 307435840 264242059 622516291 206775757 348920293 248610155 287348636 492043299 772186787 818404272 501880387 294306357 52412240 69338591 309124342 269996998 548708022 183614997 364921771 827159915 505888530 941142401 375162377 535694604 148433559 881645797 962504685 40970855 393020395 747874584 298002918 742252428 621552297 621220743 531172793 384690530 882704350 412178096 395455198 596420641 1007301260 485465766 832688897 601417685 931150890 271611280 14468739 729905377 78472481 234095657 309033206 694720634 100755793 749642305 349513124 149072168 233829514 48510778 122106888 452246344 304869139 879487628 818801747 127329677 652974631 128820290 530119657 116551034 36240499 48618876 809060834 581156842 115121818 291455211 484613002 1056487816 407082929 817535831 346687712 741424983 891054530 640130076 449265947 1069459244 451325517 1000957352 768778016 897904687 824545986 89452031 923307533 421120861 1016898825 781201208 25542066 923104265 445837307 257239037 965322514 369186902 68151270 158182414 867524839 943264190 421406476 767001791 1011663899 613100943 873134629 694215030 779411535 935806313 77774041 992647214 326385752 1039067073 863471174 816297463 167083709 326455393 219850112 729603955 893594171 243364069 895577612 782270810 881523265 808077632 580965476 865882359 572216181 498733109 552753782 130686121 447126573 569158622 493833253 832040035 209707254 909113897 963955654 499348012 249284880 333670741 635448996 345885343 18012911 228122746 106113405 927599981 836571324 810809342 477056259 83668438 244759762 751501857 991482460 675097396 444382786 145089394 28686242 203657584 770573648 398310231 527379555 966445450 1034741748 1029627017 510610978 1017133590 706463321 898012566 924955861 293746617 377552737 639977821 729108325 438388144 138556703 945608597 706351153 456173130 237625692 968938823 969075083 24460137 799226387 93754703 744692281 788903685 603710965 907444447 443697653 277552040 295829733 497729532 640153070 981437683 359166076 137245184 113126725 242282520 297863303 70202902 464625040 675077214 100827012 875414464 134311771 324328352 765637417 668685140 359428770 133954254 662420701 1029412475 531962712 814066282 621368893 176455857 132206051 916123405 564661656 236855240 796261278 410182112 567757427 690111589 1002114901 102269219 980984326 536640129 553396685 111759529 537918397 600461801 902114873 630442585 1040254392 597456575 237215430 668475055 366246220 632527351 518605072 155862330 645083007 683977178 686244523 30334235 459802000 221567622 741455259 312204684 69276013 106692204 593525980 460985943 321758778 331591377 113873114 939851866 629057745 40387662 399098874 619306506 296170557 905387856 872140560 757509101 1058868797 974176408 813575654 525099294 91712455 461779388 1026640828 180223948 330237315 161201573 267911106 82802108 526416972 1061615887 401988000 917032131 470257075 879696651 953269743 826420045 977606779 388965760 234083005 199664857 790196509 219307430 902183948 148036218 52921925 1012307082 620046419 43379543 704009556 489373581 28257532 558904619 556478173 317907173 115667685 401925319 399559464 226541594 797422303 696800907 496086705 844821130 701301298 912377585 435936938 234435558 308997911 292180738 196994421 218435251 936963388 492554462 266938155 1033557193 630297156 839108665 825329176 411559895 928096836 159429336 1059870524 311185885 878177351 897871128 764421835 899263921 849573579 479194728 997674158 34889595 37190722 1060708810 580669696 403774777 542586770 90642006 245112978 681101116 852099221 328368055 473370984 786763944 186169497 671418027 546191161 832665592 835454689 1894791 946112499 204148600 967959842 92826801 526372917 1070798281 454523911 59251493 256309203 219864672 386715566 607082224 658675285 351635975 581254185 899856824 455071608 34180955 439665150 928564530 713699244 971936589 1016144552 794452906 542269588 376377761 777243923 126007423 430460297 650499442 85334563 851329189 358653976 954253739 448059694 441172769 187710591 715155855 680373373 318509456 183338548 51771699 717338063 443717792 601060446 331705855 192058070 476299413 331118169 568598320 369437112 1070996934 1046816823 396039769 845137296 1013117213 749590330 1027815389 673841898 930379931 332912219 984103799 705629259 696750034 616932038 541652146 687515302 191570024 591255643 949185393 794496488 192995995 86406702 556483688 73474413 184217015 432632584 740489633 390029448 589109410 957456868 155280121 845723392 847227473 986539635 926748320 919902605 843799120 904608153 1023502749 524022367 326738238 129793517 719927367 190274967 605608270 590619709 604135116 321107404 1015492295 673718279 793573806 572551304 884301957 42970113 284837441 445401800 560353398 298081939 732879663 11191680 426697757 398495320 700461301 771748372 49657107 811763360 779483747 210833120 682856833 279514097 256494879 438858673 389270696 234205313 354949666 864964169 34791257 759953597 95319610 667954911 826235005 982536133 879506055 326919325 909778318 667601902 472106238 65153569 693533467 878986047 557288 576037372 788006216 476622837 352395108 661234486 81250380 264594687 853809121 372561352 389826802 831001218 230443173 1066376992 507630873 522459734 923103049 223665824 51651636 1068250247 653029691 362805792 221464522 454386645 227669050 906967655 397339638 964082228 742868701 923006902 241854440 172617037 919640333 920589886 861544035 329890555 1017382022 491180709 734375485 697605583 438887770 375348869 361067234 757649804 838369902 370298092 608425169 333981612 773850619 592039645 113142302 922069978 157042191 724713421 335767278 710350965 542989577 477692455 11787774 473111315 184881696 177220553 474108188 1007970556 1034359261 417858181 372511148 707011498 843675292 775342241 190837029 779160912 434348303 800151895 456016273 942280016 362799291 72357205 81372689 618726595 941223033 537829182 212874071 264827638 245279478 388491304 693067818 687237607 846154547 962235420 954779109 346149580 570207494 891813529 1048490232 308511372 573249943 51382033 656802149 746036803 663800805 416910698 390486852 788189122 129288510 617231999 1071064896 657279501 844138954 283725980 1000629016 716119516 848359681 239210501 881476127 650436123 944969264 673225584 280468924 932353130 694639865 525559942 669890027 123766173 986635727 225077351 12534202 903366205 301833854 267879459 365973453 121904901 773462689 1003514177 588838618 466731366 423337001 407512635 991974958 785435652 564913117 578656000 608364070 502406966 455483861 411378034 1038882999 948535690 672775678 213696997 769411558 382473278 182808729 16967590 358809680 957421512 1058712252 167223665 245628324 789676112 448712399 977148410 835886884 120183344 931510544 364504165 578227752 93716091 605591568 215029966 615104667 599103347 491820339 1068286146 978667900 390788369 259673396 158766019 142014814 565686658 529668255 328958920 73191144 658679204 1015653461 822712763 686307157 240299405 948001292 24158713 869015285 649116931 705501388 478390486 718098859 415777797 359906675 87443222 687975277 484893505 502004529 620740213 873666759 981201052 1054868493 253191712 427583320 257444782 220954974 196601658 331966036 518980163 6118483 727566680 937023232 697713883 66311788 570904325 706587961 197471018 279048703 712286782 467181549 626313369 227158708 828920055 274696608 146804931 964918792 149297557 710449385 845483001 475349966 594839410 16568563 130210750 1073305257 391962460 1029102076 515542860 836471956 703093782 1065591257 214943757 203063131 581122773 200461424 1046949411 113517855 647763908