7500 300000000
612345485 421257057 917328165 217640346 502865834 87605469 859305371 753232784 152918431 802262715 501451559 246580942 873470445 963478091 476647904 197797712 656636988 329963701 651170193 826166975 277886639 715012077 699657645 183000024 413149453 815687604 857157632 117538674 310687010 41902114 238628514 42543012 594470466 149211145 329814070 271996822 448799478 679616314 984915249 766679923 227693496 858128363 879567770 40990316 54831363 312314408 957771725 586017073 279751818 256268413 789042438 84483152 269999780 184740545 418080761 955441785 864023911 260281815 78734745 378688718 459492535 932020196 658901159 470808007 406505953 812706913 330332740 825789147 301916067 897375580 105230719 736245748 224402651 760944812 924591709 690367406 64081555 304820523 157040624 75218450 536651991 972567914 510504471 627016110 861842817 485290034 956273729 822258119 175658421 52876945 878364911 171696470 68269974 79687439 208312861 70042130 786140162 604575878 920435021 525267337 379716440 71462302 793881947 199889325 220987541 225825657 605613887 821576454 152467827 758991897 59433047 877903775 706327050 919183950 192717277 725669521 378887827 581381466 330675576 265265705 861673799 11584035 546965230 819153080 819424358 322035219 740425462 209312760 34607699 546337579 6170902 108345820 571353619 166586141 95197025 132704408 757240295 893260930 990109581 568494441 766871936 100106378 900993443 66753313 905057398 212785232 887185801 916439361 352651292 76190828 994492457 559879389 56911297 815245221 270103361 387202459 395622019 189052100 182944711 178768090 114140362 585038212 618880247 279190255 77685096 876642469 325126282 135335499 23433503 670917172 15322679 78896861 53491828 590943275 645119489 603313657 345888286 130729231 790736689 927040552 508302058 814484532 722880 547755225 524334949 346184858 651120625 171670922 114972980 796838203 229384970 815939225 174811679 865621620 81209265 853473398 469555630 546046095 905497594 649761243 604013681 281047616 254347458 824333080 140936681 420969804 825360555 127013516 702448406 999785797 571137716 567037488 609603486 187377264 834199155 345945165 294879127 676998343 625307634 850160974 872116505 397328676 543443120 806018947 121479759 261723413 484308171 713632327 791292792 106378678 202580932 478918523 740748691 871292839 17353312 693434077 716984212 362761825 854847664 910896135 450773371 754814645 530397231 568128965 625377356 170386309 629594138 176941586 44911540 799157274 612334059 696656907 939250789 233809775 202870022 114202420 142573190 37692604 361484663 122508694 751566455 944109217 339912668 122519991 137521390 908896341 644764795 902280554 524034195 360564530 388072884 664561190 551651655 660996358 604013047 944236600 428488701 756900400 687447009 735737907 836432113 976813774 639965338 597427468 679613645 792187247 340274282 899810090 318201769 958322031 582875534 895281016 116766238 527449126 374464568 37495743 490228035 196091759 893591349 957603197 418156009 628335120 678603218 870070541 542929989 851538223 131447980 365388569 773743122 623763665 258580387 416919197 185845969 816331245 11886317 981887891 402395185 436316716 872677703 441236033 842027145 37183808 439561029 259434267 391218561 343829982 777444811 72809301 125857489 953071705 75211668 244352010 772181281 620139228 228007407 922092034 905266500 558463115 164300369 975098520 446875751 984942711 87256303 253858342 73188331 85282774 366026929 659984955 952219157 633460784 661164696 62362238 624236748 880836985 19250309 164043753 94580817 632076081 624927991 474154597 49951699 290066063 857437427 303420930 12448545 366145353 395433980 998459856 582376195 358406722 529426013 327265152 56684370 110079191 446783434 683576395 823573099 203349020 74289548 883401626 677461612 255945149 71815461 997358407 164683212 709756444 493067534 613757594 243230375 226755957 714345536 96988801 471265236 128526122 408140632 450162798 77515879 446036862 765472619 428074226 429414706 594684014 126300399 855365265 132859782 491682966 11559795 124679834 618778217 143320532 82573200 325158229 207840764 711957578 396728714 757844531 583895039 374564434 227017968 254580902 486085072 696323232 278732745 990237340 765007002 577170705 463886794 188201262 881849794 875529685 132872087 482273703 458062657 865713499 487557699 854899013 967320023 493457819 353200586 339627661 808039007 42070527 484749239 958791240 701065790 994748661 271398392 494230372 493330636 604419799 702782872 851813234 382009349 276383444 229321128 129646249 871481827 282045299 979855718 266476599 186952200 588533982 865157662 610009927 496326229 505128983 582272885 496541510 712036169 538544722 335548323 567537129 214944569 900024937 771054423 791335289 18341989 546002177 706474139 56349185 307655346 575665869 788036148 53553710 968810212 440597450 538978277 285011593 684267975 428842545 661952548 655367661 697060868 858531270 45599736 328532509 667084140 756831319 439688272 930831125 453474532 618565730 914221825 189679483 367209198 755796436 949365083 756019253 326637264 234496747 324300390 26028308 217307746 507572028 257961150 291385005 493768313 208000721 80381960 641122284 629868560 168470258 524746047 600882561 739719342 510574324 29505976 613877824 198368456 943666842 754994533 222239305 268736879 790543937 609021142 841937002 671073350 44636290 809598419 142765342 480933926 471513911 423428636 782246754 329439009 754825717 445541576 595589574 794052064 980280433 282270725 813774790 827638852 807232652 576067331 159364520 537004902 253500822 223784685 710165736 864873190 21646307 791037315 935190272 219821395 766183016 162278967 8993602 102220802 107089240 15980269 534023988 760888106 977290017 636459012 660914899 422262095 63938343 982888872 872474349 317276809 250392462 74208662 38783613 115070597 730804382 560560413 499454450 954561822 420561409 4781407 694868118 430472252 555496574 982210283 226386208 831219199 576001504 724912379 145236326 512995716 877563637 115478087 997968687 647964248 529197443 78528039 745094775 679979892 62507900 396479212 273612129 590580938 238806853 354725238 531811565 175162675 425754994 680838068 133333625 64638109 672058526 76215407 816812565 477529713 582783073 31657062 923340800 184872386 339426328 976111523 679509508 809533530 594448569 208500853 389929523 354867506 932226703 83789168 27092720 714205083 108841316 776622901 426688934 603222472 532493395 685051518 936482024 382229241 843670134 875771456 630598255 346041645 402689112 609254601 638552260 398218478 424793253 950876038 95538267 940832769 718672605 773255481 33660379 279809451 305599805 684819061 626207324 902837655 390041469 784937618 941847993 303311402 455127791 681933621 132635025 113631065 655183071 561960996 269359295 349654722 334774321 752938665 896939521 326625709 929216603 443630746 415381311 552662642 888188482 194506880 117643217 838694028 41303226 319422459 75723656 234800947 756302529 855886855 277481753 144897558 879235205 443289854 201209416 806879327 790321655 58833666 873598171 114895008 451902283 63358824 338552745 780244334 455673788 911957153 651023450 54649487 141688353 945506383 714520950 264978184 430265213 568974942 708325115 529137209 92821337 755120225 965755807 824955602 442472006 200211037 23431661 767205124 777213968 227469707 473308923 353996603 554685200 979015150 277069172 711298251 410109024 483880605 394136361 845484530 130615200 231745076 580430200 871431842 255559481 708399538 109310476 592141891 553003831 959264498 945625820 328871306 963029914 113619987 639304592 552089731 681422504 513816906 230272692 37833509 881829912 679528061 432957484 248575370 349172834 729632696 549983433 480446049 99448293 7938575 859379685 893905624 691194216 136564730 448412464 605499752 590546484 317682636 208516761 654221788 454298716 215309261 105373030 412872705 953828125 143584247 667492964 19978473 298343264 385972042 930776888 509083867 824630876 389904588 301999827 425304538 145912920 737269968 694356930 615869223 512261976 439102251 871298269 284537851 306760741 509753545 703513746 96073218 439153700 994702945 212436934 596942220 799192183 812876803 176757639 511584246 274411979 227958924 734656128 272263854 837583022 259760561 308967207 968012523 29415775 400298104 676152335 167863566 821721021 776397674 498306896 97052535 814047767 837554679 447517349 781660932 213931295 54404742 720305587 233435943 842181374 247246109 895456361 197916067 913570689 665078442 63204738 874693603 251659632 996665068 717670695 282810871 514673919 176599297 877856178 823299884 90827102 599911052 260641934 373410886 803242859 821723010 674199354 41010055 559561874 542299244 414741329 670593158 758990383 317045586 251496170 306802624 667251771 996578547 917131153 937318469 579117137 730300853 959573413 310613805 585288367 746424055 519122556 998097164 403046846 142164702 642737142 707512453 467015744 596643374 224065471 552773622 354323477 4305440 657934929 397373354 275659630 365592194 41217802 674921983 385748676 540357505 996711212 342204754 688285937 644251527 118045805 818090115 913101264 953003012 966286473 681552531 537972752 706441241 856894942 108089231 604767327 795758167 742047432 514796050 454486988 847944992 883426711 199772143 39903063 962026615 579320051 468052301 967334254 588337392 63060972 604237568 194809798 229046936 164572806 955280960 833000459 445841010 30256208 859096824 418975994 346283311 601691295 699496583 967654760 337462611 965961384 884708217 90161753 473124697 956979040 483185345 198683311 796823676 95562114 310343317 544552957 104599586 24921007 191006842 237077990 51033263 678944123 593534994 272533461 142591913 344146582 219329409 862877617 681876242 9315776 219312054 102656575 157653262 842823257 318030351 877099301 177227067 799748851 318013542 745109815 81559658 786788206 711976681 10442474 884153398 727803840 458750446 427974117 829571312 913216774 112542867 40715390 482981124 711595577 368227306 769152517 614499962 637716111 204427090 480818091 198309016 509562736 805668833 760922638 182377380 98660371 961174269 142275426 962742470 623432373 830668810 689868300 958677878 320466237 775641342 187295368 325779664 499233168 610885083 964282516 613469108 937817038 389738887 418033718 435107139 413319886 962253436 560746910 574161957 184774844 275729642 677127628 932950410 157596562 871580476 969982798 58178491 186059431 16343875 966686503 915567454 658601473 961184204 816525888 784619263 376635924 370587720 220673257 593267618 789406398 320878975 722829723 758784583 252320653 207219087 143159323 448396291 901081771 695540562 281069321 711426133 604734404 878074327 378581143 685248399 992645874 442240101 566181884 356033921 719114811 923513894 603155705 431778573 998388578 384467505 69895648 742344985 673718495 703414890 728786816 752656788 36230861 489436290 663128883 949187606 706256463 631673351 564587469 785723169 369656557 13957592 805309483 66116659 35102461 123926385 480146213 837498429 722867905 908895398 781283366 295146902 316150067 501103214 679374356 537705633 510164359 299986475 249991957 957113527 514807554 618785124 138108229 275475591 219781749 223480836 554735096 181438215 23016996 954430234 203329528 434921898 953091960 941250994 629700879 507516210 473398470 609529520 244492786 75963171 587461199 779219875 167811685 5673396 578189097 36252274 17896653 95947621 536561741 549048221 380363243 276765890 460217657 175562773 409030578 210025801 25331965 760639237 472918587 222244417 672253684 5958294 372383542 952718144 974058957 948932210 368128736 382503830 666778561 571806360 183830163 8073864 72018531 934835770 435121577 205706379 525955514 76050675 238901477 486965668 481169736 735778332 561293152 423823279 883442060 48349992 954302685 668123468 49931681 346342301 299952955 111861607 651542276 747305648 542875907 887484257 952378226 499403899 152890657 95279344 174006493 14844336 985824816 325012452 643285998 280365550 468736865 515539485 701066063 615647661 231565184 684246505 202918317 972717126 870636009 160490652 903461050 928384625 166642263 214643676 494644418 749457374 453053071 563158248 87628383 380896453 181873760 672096683 961622432 172530324 116830045 129496658 359785745 318865580 494189987 721526332 290799808 763355046 479162103 187705870 762051053 602527415 200894332 965620452 455358285 513561390 93468173 692855970 129149947 558664730 849973309 24469352 741805820 623383560 310632936 33536548 322038125 965355241 359505014 194535489 202821451 840314899 701761452 662917245 43259615 757547614 863498286 820785880 812788420 115354735 246781333 980810152 51729046 307283729 639963689 312173001 138224697 85429182 199066683 62419442 940665283 521522494 332778786 506433316 179981831 890725991 146822608 216648251 472231871 860598018 118567184 147295399 949999957 60165838 853176158 365177908 995760462 401951390 214602338 931438596 226481053 263736331 884479135 378444766 256910514 741714756 72348449 886652030 422363646 194805334 598321042 288583366 403021954 372061402 185569875 551164376 858753881 393505971 955055753 238049844 218090626 42477729 370185266 941198379 210967047 175953276 45973011 49109780 368020999 503779683 475525910 71892076 181314936 647292408 918194110 468444706 407380399 247570831 14852690 347159794 410598532 751697849 906127674 356909625 809398371 414396242 373735832 554478350 160791808 587296676 269524769 42810356 209520725 883744142 492972346 498558041 514751712 732270936 609669911 721195298 539622 358247102 409140407 44936984 754864663 802713143 377934561 94320925 417937570 769082317 865517051 671867925 486880282 893092251 802896295 200378273 972633298 570353750 300342388 957560128 944936035 503099442 319749722 758495885 329814735 121966443 25183514 343820095 499004827 814813648 580232824 626896707 884304095 756008818 214191222 15296894 532841960 936050883 907377264 93693499 604504440 742248256 575106875 874036597 303321536 579986568 650472833 855508417 137448905 606052147 506633650 888585279 499177874 154068705 840871271 348872698 677431393 740236212 255125527 171420713 466240481 45313142 821714746 101829324 934072391 514448407 157226921 664024466 178189683 956758323 312664996 287952525 223000287 377003492 87899777 376740705 533932191 838054004 238235847 634165157 942657262 105525696 220892639 250582677 888836232 991626064 839055284 958594997 224441018 361891493 789765357 959619010 592811862 533087971 83843635 640186362 993479640 342125802 387890469 111752659 367777866 933603037 100175567 158080319 157319602 579507619 489199762 33083879 143751681 531306676 315233568 115578630 290242029 75667586 501525412 24392417 687044060 201252742 501989118 312512483 496625148 759406565 79375148 772382552 13436783 61569983 555187908 2183622 903703716 363526677 764382878 554512612 690886849 459236948 142511502 423939384 645454908 109140046 637675344 447946377 740506628 615675771 519062684 705378030 763127561 92823990 360573414 976184434 801618583 979801067 508444528 722480371 502968624 80400302 172646569 234077527 659235360 354734529 501279115 494268635 733831526 59972786 173920660 19212679 254243901 678569377 436252254 114363330 951471686 591004448 661471709 783750914 525766995 901267509 21548955 707206098 475288438 346552630 754471865 119140308 61977694 558753653 607493993 697318073 388759 650442504 628002257 756801914 668550029 538736093 305977216 258026387 705294343 679757239 400690144 980658315 489284077 819629511 756520904 660476449 188994090 141701603 974447381 641472684 52478821 519988218 249010320 355895715 27377653 728608304 206748219 55689734 692754912 821761716 44501004 245860297 946895265 180773185 432691853 655397784 179291471 801206080 429636386 255411985 846006613 434952325 292269522 669787977 434735249 174692789 637810899 991988157 273851467 96963008 746912269 240922358 689371281 774656513 54392171 401746080 653168861 566153045 258933807 876873281 327651724 458767080 708115748 790937208 659095080 354768205 465290496 541021097 708362332 93649448 734950590 171620269 548234595 264711920 346194298 976723879 253688244 10964928 386812020 850128090 206011865 321374906 947587891 927573284 774129246 732330520 696617926 694151451 383386852 62700241 78794533 212812227 138619989 306858980 271931319 582546409 715333681 906749507 201566701 678810398 965262087 565915487 73644299 340070483 976019532 403077639 764814350 467404694 713995666 474880138 265616967 45286754 924895119 300478483 133994977 136766226 642505612 303056699 668072904 227605338 294429459 904648611 411680448 455393704 761329321 629963830 369512122 998525669 399543466 426814808 985137238 200805068 421137185 328244619 399833745 772523869 236227389 42053030 963362202 894678187 198315306 584489685 852181260 270077899 23900655 510969770 735876944 690834463 509947931 623508790 81386385 886373471 719782086 610816997 331321819 399574568 228384651 403674722 467957219 365549161 5558382 950213873 711346337 277976457 372582761 691465841 847573097 435463098 422055741 510881656 635518670 670007349 467038457 937617865 255609435 440756328 52586083 930833871 957425037 686651227 670300476 613288888 386267480 507633145 775794710 822011958 108312577 346157383 373540513 693404405 390142789 408732388 274005606 746359365 658200646 447798929 387901310 181046416 461673977 640218718 605943124 269928201 221573445 45951409 522914132 701619213 629417667 356657015 332248113 168749989 486852629 315435893 432915411 104029224 257537212 82329564 951920382 896653115 458180822 386172287 371582149 2029678 408113147 119032313 22400199 787840821 494104992 388283601 881163619 741858878 869825472 434404313 269418661 775408670 508375359 798606693 353377811 978993569 184117246 558959518 673233441 234023977 668869261 922508399 30451008 573772062 75157423 350039503 499920225 872947149 948046754 384096399 176890238 612813225 796985174 92126083 351491211 352215094 186314728 883501826 522197401 615666715 637731082 804255781 774224156 196253866 751520488 490659423 216008110 126081014 200649189 762786490 956652909 195317114 937587692 757393543 520543132 76027841 586038371 594959044 341981135 888365930 632759808 452496983 121573963 718053957 981738246 63169349 905868978 670840985 700497270 914807325 463289543 813828357 844008562 341836825 25709581 66811527 218235189 127754006 649653511 885118230 54997104 93673759 693518071 192847156 161694439 362513045 500426178 942313769 228240152 487766263 571013103 446400993 649932309 146682964 371977422 445666148 761999731 366117194 852159157 919865581 288447067 907743673 697974630 912565418 893174205 678918154 975903884 764669199 590461861 870863460 132767191 262618022 714564276 459597945 87359641 105034354 186272482 661204615 838269699 822461067 853985153 235079349 847576596 473646850 467277998 136835260 61688769 906673899 501629166 125681833 763121390 688420686 841653451 685809764 970420363 903907604 21492404 985879648 476822705 377423868 887912350 561395230 134999267 379005232 493028013 778871223 978830134 690111045 959578339 884545925 881341968 528540660 597373974 88461201 368608034 627162395 104275266 725637089 966002098 94382385 923469580 418064452 891830366 288253594 939034733 616665898 835956069 899494826 576707416 521851294 478134609 979610393 710293788 122965577 285564146 452102980 313204708 288015064 710905694 834579846 603279800 418623810 484413210 871401321 745477394 647408847 966567080 397462317 137163124 603232860 315581152 840045884 576545430 599493605 473448126 500319403 747764671 902948073 1140803 733746177 382247492 978035523 246747594 462393566 354754643 510555984 71340659 662491761 166198954 218017126 763087420 764087020 731435621 391844508 741210363 222965706 934166292 819277281 156287746 640589870 83275383 460100648 249779821 779817433 118106561 100768522 427152288 505931014 641523907 293978342 767101564 739167977 257663142 564121968 187741216 725522887 158461677 649633612 105758242 714723602 147000576 632166071 666039981 50251499 94108952 219159698 158486469 341820727 875273811 344176653 182989992 786901597 504979943 353453297 452744528 314243993 121984883 122427529 712319510 597345024 93213297 385199918 541590384 966293776 954063048 419134062 706272219 260745203 614403198 48166361 16894033 957877899 737596519 584117247 397632462 864365768 831176329 472373099 260755206 950194379 805141997 866477540 598353212 898325282 383315625 909727675 952486616 715634351 718032182 160516369 213673409 793309645 574972718 530711032 854929195 378703499 749303531 656049146 286513163 426050305 5735560 951806947 9965043 517845460 912947359 324217078 205032064 115071342 814008353 208939618 219132139 330186356 799741400 656443601 681544436 165930153 537858576 441201750 952900225 287989842 598564916 369874268 116490563 740091212 226565572 751799949 482226649 88935116 594314146 445128759 648763883 356510426 559143270 835661126 724818105 175375683 478833196 913931051 870770616 337103450 556234052 561205616 161305802 229665501 471594346 564306198 592109938 378092552 136357721 924992214 294237001 18585105 659379859 328400091 281811677 368578296 656881087 338357196 460905923 784224820 477585732 981552772 516397524 866175800 672531942 384013714 278852200 198836809 161541966 477491244 21569375 74939813 162329019 466281594 613435065 84533209 345839558 528166991 820522783 722327528 336292944 547855463 670724510 628939387 454710592 967046766 740201804 255034319 657593233 132833008 261310769 967559292 910040171 278465719 252569798 825196991 435365611 575608766 908206005 178462617 616309687 146413112 421625676 538902369 885143171 572581802 515503729 296606764 456222141 199239083 774067076 407001881 562595696 102834153 839744784 645527133 891263465 135718546 217676183 601484468 388726952 81022291 685341395 246671490 981547632 807810827 49366294 848000139 778408465 745908947 204274251 691815638 290070814 248364597 961780664 629438169 414022381 433132034 349291570 457806857 927522428 88741417 479420361 409174893 979559237 337768138 506977067 976765228 767298444 421196844 181686493 158024066 713077305 872375313 936470981 632195948 789901522 694808852 769664214 104054207 495472395 912195867 416105478 629673373 880932381 918532326 863203331 408702997 355756803 462841571 903709310 595889992 723066028 617968919 984642329 445980939 495260109 891904194 749376208 229781100 504228752 535962227 300074118 200201428 592484334 620379981 308138859 986740101 99634040 13979316 42112160 987046251 29255029 1153311 409477861 982209516 703790771 798531364 767753622 90207394 317833025 257067450 962994299 488942045 218356894 458330050 562642942 312893291 641797037 198771220 706774902 875572398 853876677 193880101 123629441 873160281 940031716 393386834 221234825 233450951 252052227 269015755 12548970 834138104 594821674 404177960 583697352 769945183 927626470 722461710 898796509 493647346 383704270 990904750 457257044 267604725 172936519 639391451 60309041 517255756 254787887 944523853 168465404 405452861 356168794 23210229 186427897 200866437 25290581 403991908 628403206 311341595 183200128 330116110 546856012 928527568 260881582 359122628 78587643 560922136 933621114 102181909 747469412 635652364 361497117 420854307 251018378 40731888 692044947 715000940 149691258 738478719 531252126 7703081 662835014 44560453 886343892 797573597 254715659 739739553 324765464 815797081 784616280 333681563 110211514 176729678 866978106 728779693 251735942 790351552 380963343 715703749 941380459 936728342 177134439 71055932 929039194 568269101 723598070 746842738 830831728 575396759 99153752 224172276 228762494 61463741 680458421 377975750 321831634 339473829 306190335 212685772 291798248 700237443 108411682 527084717 774300579 53018218 889502666 892650195 720847657 111056411 579418828 989134734 923952219 699822078 352847922 285536088 898450160 281162542 70691814 536088627 854841133 220982009 112150575 704866115 702835643 595668369 941127749 866803769 60037485 857050091 508669636 715349583 458768662 325636697 310198536 475195406 968865701 361991461 749021422 751404108 694359851 975022231 69420889 277837200 261972659 488756773 187488043 946015379 994091216 114195281 864728875 289618929 241874156 909092768 373420640 982458561 642091609 749416409 978693883 502148921 118840338 95006011 18797686 15138238 853966943 823161226 710457072 128599457 447334054 226073239 741796906 340351052 159948302 25933574 676860464 76997280 162688150 178601723 582484919 625541293 120845122 616238433 480641182 316376846 379607919 922854870 108956311 753689056 686484296 840446775 193180127 630438749 613329745 993944259 963637801 618394648 330251041 519857049 103383767 506996525 2330821 592948203 972293640 31911870 917448952 293986228 916947682 173301509 146996105 509827521 863942169 403117637 603772176 737106588 950742077 79090734 889345192 537510445 865172912 143222346 872561530 310589308 612806722 122005392 146796259 317396587 716291606 487122245 620429955 922182628 571360103 420216703 372685154 203513060 644495651 370554928 44714485 409792777 829148886 169996392 989637406 774660523 644499020 451760909 851556063 843190310 838389064 697183908 7294133 957611773 278276691 264931536 709784796 614428426 491236100 645560322 381181203 998584016 502564915 13513864 743298349 731093442 138680416 963471006 87758827 823912879 790189339 167844076 496884370 100357799 522788885 725769234 597892231 691008813 918754600 699938939 714344065 826063471 179441827 502824221 394924477 829847590 309593673 246773678 874268661 971092700 479504043 463713854 143476382 207970396 158063439 311893355 212578736 50084530 713230587 211486051 143380856 286124120 114445280 320967210 209557576 317832150 187683102 917577836 937410349 543975283 728882910 117836180 281331325 296837081 693277057 675514036 213076572 622434647 552506646 810205068 79358312 452907963 694302165 359846185 901646654 170710976 876032489 233182808 340396434 855192956 69665034 784661708 180853134 202279635 989557508 886939748 409968271 84723444 112956667 785343705 651413351 404026443 160612345 323043626 259444876 127150029 799929082 628657301 265283792 704624478 278285852 525939158 927605528 586996367 935580266 500818185 687436850 384610408 80902115 381419046 957727600 649716147 427850437 640019970 221921986 450814106 949288327 905155030 952024787 212062860 855491440 940172562 310388671 917598730 982626203 70896440 971273486 84239385 516257112 23690185 683179032 859258165 821508685 85187282 796864943 966328759 766756719 515694065 654852551 629122332 519119212 266425935 788130283 150509260 191855427 270642731 736792043 353858277 604201346 624909339 977265922 164793493 136359234 443875379 676377873 936752691 274863372 998544326 610527042 198239083 589700055 162878045 328761628 655961927 756808990 211243312 218966954 235519002 548696075 487850624 513201362 973908331 266557973 205973139 167355333 855883390 41527236 62854733 822213778 594543995 798176144 227380072 267348694 21681982 718218471 536313936 930174862 428605370 584103758 647083934 906361869 989892874 764802463 667507720 553829654 983018864 773808863 837799119 481322974 683475604 897746662 411288470 61565542 308122811 380969423 456645874 222213182 494495541 86136850 971589471 549048749 844223699 99431758 580813946 404988910 856224549 904496220 28647766 840173185 604224435 477169260 805682665 667699313 564477867 594892183 510716791 74521070 725261328 341920234 937372207 737176561 596059533 240783982 978590992 942769893 226210163 473171349 551745144 651958114 836454989 146872139 198866976 84807486 623027388 393920442 431356996 551934846 338299579 624544843 25033433 35146405 953463547 512209459 826765288 807659595 890147999 536536762 912078360 141184448 721342080 329745542 595487324 661409821 928482103 227195217 557541108 814992160 951334505 510830985 637508470 69920819 105118042 962868346 660877744 864759106 263330041 456244637 462676046 102988261 768618235 120438069 528288966 985641977 236821161 265791168 67320826 727098442 959895316 284251718 589506230 731006566 672833090 197414485 476398399 626894931 706880553 190718851 679972467 25922459 271374108 528578010 448124965 529258291 365171635 205791953 288516529 312234032 13141930 924572595 483449739 299334161 658997746 982780725 735785488 7518161 259429371 551365290 558889189 651071185 933898637 213174321 17844451 669400849 867370228 342197129 91230526 951623816 895371297 901702838 317940524 766733673 336473656 194439732 328453032 973482795 106491146 962561705 159984019 155917565 732011279 216662768 817201142 747522023 734465139 134232162 137489534 104439111 863352321 553928056 622253635 168412888 164338336 441916805 988850842 617164829 360129841 490817861 419409250 65389898 242855436 865417417 538874165 822440065 474035993 837911667 26598717 915693480 41342011 96048669 465861809 282963797 322886233 231527001 156266214 628527370 643350995 138923816 530821038 152756445 633976531 251502811 844383562 357565663 97475502 168642833 529585431 7263357 895899158 677267113 863617235 271330582 832372625 839522633 83332342 144726399 915560110 938571290 432058736 578575770 9768122 989414687 264540692 513524509 591684167 788619596 882476797 25191769 674990380 977823718 934855115 153584021 493755425 876134164 911084335 316669386 504752568 185756613 495296574 917086009 133563804 901813048 213423256 718654340 233356321 741867514 624027954 947506829 195183533 62280966 406837803 860226164 709711742 206970157 674840546 871081022 632548075 514525143 244173167 153845193 620151729 881087983 546419275 321945545 707940715 846785389 917117967 778466140 518107168 705264001 655277141 83434315 786805239 605704025 286337723 445609183 717712901 859359119 944151814 49114206 389006919 644979250 777892706 678366497 50416299 202334919 488452435 141132104 746656477 585432952 852596552 565021103 472588130 840247206 462046327 201192793 147349444 114532401 913943574 591807295 93936080 23477134 533543760 896586889 76856353 136681155 167299366 186910814 959108749 809846927 45117407 104833754 690482994 768286888 141594157 668184350 218275352 671017756 475351006 12496000 273414531 456505817 161708091 291397347 823608392 779153921 648657442 171703849 682162451 61816569 189528742 318330463 445741576 843880216 754180611 332060693 281698283 892734767 372252841 304165235 615831014 423322538 346674656 553922989 641778522 678678875 388249860 916897588 701927255 696806207 519341301 573173047 479205459 653735686 656872150 915342394 245946123 661194896 152336794 216037147 117527001 278515811 430792422 654767440 423936359 126010228 292919317 719596227 503833726 1213334 468546901 250582343 775774972 829905020 557778158 172451253 117069796 95179628 578302115 318524072 331391119 807830403 646949681 952716497 908708097 230654111 806328308 420794103 682928983 844321004 109191849 989737870 721240668 540698382 937781582 773900787 229105978 194130664 419200038 822244674 42068557 511756039 819333593 184051925 439081235 2059439 275806647 292138073 739314815 321429902 165119427 571232496 784970738 448643158 1492039 805142027 630777418 950559538 638831397 843879784 389380530 218170774 181186659 516756850 375592021 509210322 905458093 193834748 895915681 30121138 604234915 757311332 905615411 656100485 242112031 533470706 332457673 738986390 889945915 783365431 634369396 641033879 968434218 888508458 573368545 354134641 845347658 705598760 77486934 780462578 349651899 972766560 941413678 423417161 961163810 385295485 857770509 459505021 462424406 982332873 381692065 967921907 345724425 932080581 19371133 794987132 83828018 330975279 487464970 944023690 34161426 561085100 787147508 795494679 338954377 622666550 909443403 199733746 51142045 224040170 696125194 386422052 620794454 789273973 435354587 573930154 741365361 355935975 418128260 234654104 121131223 308456608 616793324 893156698 356989621 801959270 400255950 4141333 671152695 513972889 904844025 866154284 578576614 812661373 588283713 822698718 408843676 352406455 379425542 503310348 919308320 414706131 520206942 323654936 669109858 918678786 854432226 618215146 202821972 516423905 284963346 439580428 648246114 716369524 300958197 605065872 331610929 997033714 597463907 670961465 742589364 277530849 857436732 821044386 190988925 563362408 990785109 941814255 150137978 660554530 996156505 120533409 446357599 890909769 65953947 122337510 635175983 829246510 328015809 548757360 526223786 932494166 868118591 44575329 277713235 40119231 824109420 62168162 784231964 88424000 247409726 837658323 997727664 155855374 749708711 142620700 197443933 854433883 987587211 747694882 923174813 213926424 597832540 479252950 156139583 235063260 905181012 171815143 56136503 974937565 679627598 878873240 276996606 82778138 653226562 451624871 3224731 852985179 331245949 6620544 551409616 603114423 231061035 833222753 426218775 169256378 758241778 639217497 482817173 977425504 449005523 477724733 584228855 207006004 29171443 485064929 388088008 703371629 750596952 522182542 411938908 839428292 838801660 557818199 681933938 388219653 87727954 51691575 841022958 171966470 826339642 943499359 398297867 207872806 116058120 378922379 567996090 943168311 631193615 267713928 85898865 135538355 632126871 311376198 719090694 851454145 459026336 609583367 260293481 861017431 121390363 861185734 873831295 61412807 868677018 254112312 699453735 546506672 806207562 301277228 35230398 615271178 698017878 752582984 932034717 156598567 92697064 250274828 130774826 657589824 42712009 681483068 92700982 446674249 492440181 652958156 671388787 659987825 934881891 206420635 125931655 677672815 875035163 54168552 181269075 766613814 287773501 460506546 583765436 521163083 47864069 761426113 803013393 39974398 522026715 836251283 209653950 698115532 181955926 500460464 875850885 610475077 520658302 317969093 663919294 294251601 464217803 624531478 63337622 555574640 984706393 956796774 292920799 682247762 468691021 561358146 656829852 634673201 397602084 502435047 32176284 496994763 402665513 838581968 45521403 281327104 617114592 543161170 536672864 529856809 598932767 279440152 128598494 402752129 415088250 533894884 964668093 395214634 36471791 404694464 740001017 721168138 770913483 342264793 39025477 730035658 286601277 268789244 85088882 671561 709710804 174653193 736793387 623810142 259666552 660981318 833201950 598682771 222767135 402265621 25010926 751618271 324707989 799349441 235186418 73341827 34637354 204208122 585634089 38809086 97131457 979476134 912082363 903830060 4606278 59488355 786119981 237756686 298470743 275285146 937113878 7180276 91337976 468987719 75772415 231476822 198403303 164038139 325291024 62300831 357620217 225812282 411378525 348691320 656976292 320166424 289234470 531335992 898866359 152552711 656145189 637003596 873566727 839728044 364436206 291602932 433958266 296574016 681978680 269389303 809668393 209702130 897316553 251736084 87108870 819261291 329699122 194947486 557529667 154835191 249463295 805844287 749189880 735620867 168376081 996518703 804197332 574632338 210008493 347179802 778246007 444123459 212306668 713049054 937141950 272817393 990613915 560354863 648149464 953786375 468090383 991739201 218665788 990867710 971504658 465794877 931300134 3075726 152595845 50779164 779882127 930106410 541180056 207546818 443906190 64837070 321573135 475443227 80066670 35342719 576908286 474665175 684349725 83479633 370057970 997944039 649326090 115976614 890883806 396299097 912718421 743515508 539288910 430892871 596540832 570456680 815957153 396737258 995257234 702434832 380153577 119188001 529255212 595073840 306377880 224359035 375685107 570341318 8084358 563194871 662189371 796979746 216988112 888336252 531466521 561843570 413465931 791609058 409144408 178436191 601617979 356696884 787600963 859283783 446961576 410904360 44563327 682255156 21062872 459795941 642149018 784457105 587496479 324885342 335628260 791417186 917871918 73518336 964344517 658379125 241059328 609793919 366410395 971751954 682536652 216028944 734335040 595827572 973431715 509676802 603948405 535708305 927235648 494572899 958500959 843737536 639352497 281362313 940968873 403636531 43050823 165792291 924401860 397466901 993049510 278215130 79023694 834849084 21086972 458134179 127958160 16328331 789128527 42564516 107875874 166873063 70358510 475381696 933909673 784910036 378577161 540961985 437653441 571760043 414737501 680803617 203261429 1970042 978350855 176246389 695026667 601234808 299427962 951234167 992923549 869557283 84243596 997511342 202533314 733650424 143583402 226514108 455128395 57766350 294014508 584019780 659546377 684636880 668922308 570941813 217703787 860365845 448917519 704513336 2088037 809412574 720801102 697033202 544362349 257735275 422548014 340235766 36088223 62023802 277521859 667479690 396014593 302212445 744026772 425844372 170780128 231889591 681928674 556787545 398138835 995336605 678333203 386337780 198668448 302368144 711580196 726767978 376195149 666813497 20594586 182561415 789951869 819592919 381694537 485985322 564729895 962591786 471404480 975821418 323704077 844556133 563697490 160315347 879307991 825552961 600244673 789680846 543545036 296252462 13279624 456258846 566167340 623539364 690593221 12981127 481680172 971086488 621817793 144890249 886811790 933274379 216053022 797599050 376513757 223384252 190961308 644667281 39492674 902278398 617169287 757577710 759058438 662404004 303078849 844550904 190091800 849381479 486736046 204171147 436284299 850450211 710749951 103055886 892682342 454861383 368414240 603836479 887737004 527623150 317072392 507336949 76545617 554268421 186493008 907463343 204232448 202987985 188647993 660879044 152726731 587720531 652948187 58073757 40002748 471272870 678468522 888790567 938034528 355339821 270644615 458373282 667704117 411090885 989021034 754972563 605879224 39426943 308539574 145313364 260702530 455758893 60723372 874834176 625253867 876828133 763319105 122174941 724769717 581881976 902168842 391061862 727519945 263981965 696655955 944432601 165890649 412703056 843101191 296900260 481562475 8441398 755350168 946106747 722858428 644630961 384856977 983013974 766887063 951520960 994340038 208066042 677325223 334140053 600772791 984768980 342069056 2915737 615186105 785712445 767300814 190197696 78548800 170063211 164477199 143229760 624987192 962719536 659931382 552674685 488453427 293695293 441649292 28932890 365202311 372206895 853737595 172629358 624586863 884292925 985073343 331398556 841755636 831290647 707522712 541883413 529824368 210997269 117296921 908634772 694740326 8802264 660127871 94274496 966557246 964808750 639499111 484389919 941973803 64612651 933782954 286124765 518356613 828435481 272080184 372364838 508414468 170526123 686138482 973385085 414063555 827448622 162079125 76005987 362461 290502615 8539088 955911195 117102770 746707793 70364106 41149243 499113408 372638478 814551388 984339885 927040409 659922081 538729009 983477637 185686092 105045198 765971608 137551667 335324399 581077571 554828431 821707641 669313986 4560654 752866976 618998103 301095980 895157389 468993253 891222652 979066234 544801467 112647536 754254005 887686082 478809185 594037 227678007 330957416 127852661 229389734 437420172 35581628 702186765 527581340 268910872 587193537 443171838 23033969 182877255 411758089 972657429 18509930 777526870 202590395 878564337 413487569 204073146 861383351 80499580 511323362 425334064 829081808 449247492 162003675 458973026 269231160 856236794 685304630 724933427 620579833 186864965 389188083 519027623 772351647 643983684 583122190 482890866 69398004 764941663 201573916 797890787 747624130 190776013 807230334 437263316 802789372 763899835 97321243 98006384 587915675 238893357 115567769 411268161 344504465 547675434 479989980 901000214 842163395 189455559 638019743 957104892 842626554 670535407 896782368 320589902 196677452 501269629 810365948 55993507 416025136 255423322 208924499 170714479 796368969 520863011 744978956 944356606 871431997 71578454 462915940 137306758 600647444 704163392 550225792 146431325 790685655 311569756 321287476 790644675 116643918 347922708 651903253 137417887 142008236 18744430 611820728 169895637 29970540 222625055 914832374 613797468 945733105 16534245 785300299 746104675 342440963 435812792 773519446 527862476 212889363 755675881 589681368 70467227 657326032 424980082 426080676 529265485 431929109 14168929 495523413 846283569 384914778 504788473 273443908 659194055 619011106 918690658 485214059 396087899 609249372 571151977 477878588 155484280 377803123 383252430 903264180 729160415 156491863 659241867 347605624 557710483 570820903 519816757 349383050 112682769 178037112 214112892 453029288 981075614 416271685 728598221 646020673 606962104 852433523 882925846 530609941 572742574 575883518 779479721 773560168 253981126 919939130 353415906 882513582 60323312 173956099 107085830 817545525 344035066 668160519 50901069 872532632 810867551 612154482 54347230 886061586 6468067 233736735 257065197 672035513 68369788 530480436 235857069 792752623 990563805 782225384 454398451 192676593 71278240 618229093 539579753 222819724 990922510 142761672 154473323 409412750 390590534 228113281 550667165 39693225 549479016 888027514 551211898 470978998 13842806 383515169 207657220 630626599 256820978 594578847 516308643 374593646 20346683 915201933 526753619 724158963 791990291 504151097 467214522 19599330 379307178 158674297 964947563 72041027 233292546 285410874 66992378 843869274 290293079 849627796 544484882 224188862 274805343 211926373 351142 621613741 869794487 322990937 403638865 584346464 548681424 51681671 409936979 975956090 230779766 64051770 905691177 360494234 926419198 491981772 72750280 528673551 398149388 636445102 240330101 389069739 739737342 36118340 956168112 905397497 154408559 76353067 703431144 920358798 865557092 807461313 539448273 302174216 189056951 235721113 139606004 520813908 193300666 773598517 620893014 124074381 33907073 554063785 605785096 744237604 675877311 984044238 167280857 330093225 687693855 786522668 321969208 556269514 264166884 732056962 987165148 543252439 48462971 527972727 322262165 121668039 140136242 484575885 289758320 567121929 509988528 427194234 900819943 359803634 64922054 321907725 128959367 25417698 877138142 206292920 911172648 954081780 727114298 645677563 238737865 292074595 804606637 357692828 40950760 138674368 663348523 272853501 115379278 649822749 615958795 856033174 985409468 431048169 474592823 442753200 375754647 238295145 250861628 135224977 284734997 466490562 173967063 958596012 268903007 765908185 443470635 539799378 760849762 346220377 808013471 930158728 160849715 513631186 564049746 302838259 79718172 416659004 502323952 518941768 653126432 364633314 108309440 419822342 77406342 486356661 61415136 939713069 362448392 185361271 534569581 813354115 981048492 561582825 593718749 493261383 949530155 403060105 297366887 52465037 954274717 67411051 160136284 40066345 175622743 442712085 453658747 850274076 133051865 899554711 849081282 572612767 185770613 888076770 551562410 469992472 833822455 343854368 437682921 768480963 523364405 551336988 461548684 438252838 449601402 565530988 713973878 611817530 811911306 54432631 786422163 932109302 436480679 50393541 200156955 241944544 261724987 163921959 520674423 941236162 123214010 847250425 543823511 27944640 283199831 240604714 696363786 622793403 41110074 924865488 671302046 734838975 408083716 936104645 482077103 522161290 366570294 113213581 395500841 240116001 832751809 580681372 525857692 791926537 966257268 669465884 402900620 129960475 830286105 9421546 334322866 905296088 767799938 787242807 317115641 61644313 110705224 423935944 721632859 415082823 902961029 336870033 146598017 168293111 887984587 802608577 435004449 729132316 692877649 585592164 543209854 745435027 444829899 90239109 796150136 670544992 631636523 783284584 231730381 308666333 103765076 701405300 339690794 354304318 527006677 874308814 882447541 556486079 156364242 781336724 528099436 320197891 907528371 937968055 976801421 955235942 586231249 983958699 970975408 41729099 24050022 469653571 584599377 943569699 887464445 776780807 472171606 356450854 553748135 318529227 804660183 262880001 241402736 320573715 655514160 471926637 476133874 973776694 825603549 429044845 574205187 154807854 388366719 781502244 157881230 444799743 499172859 214477648 22332031 461961410 155579586 936755559 777488344 713336654 635020843 169697868 148839649 141444225 57087996 718282926 135265148 395534384 431412743 457738750 929034390 361301161 872398065 292793099 746868154 10796513 818006798 872668219 94951359 503198527 857303912 486656674 563361796 289581396 491082350 996718677 946510698 472173259 505751895 165152998 586712443 715328852 821026117 980975489 573789587 484580432 733499072 248903559 336284990 142456800 169444340 334676218 313739962 5548434 287721204 290903687 174775377 101058240 766965778 353517603 306153746 842976589 571816228 946623302 253837283 580768855 526045836 87622794 967366249 300396865 25220455 746162574 905772755 385188293 155980618 406845478 460839163 426928278 672707216 540310250 956724527 545660303 236880637 405995427 431081732 917461449 72148252 359214867 591620536 830827664 171428495 900153455 604037112 521756448 29552060 736645646 442457273 43377552 993173009 68748878 310582122 879525238 299863994 885643459 336138755 559063090 288984839 98684377 104457597 789229685 498013853 964086051 755123429 925331623 10284191 581034705 699478940 302355692 378796914 987909503 490238053 693237355 927639930 26724817 967938413 950292749 902178719 130377449 214035823 675373003 428151094 89035318 502692587 528707708 813028942 138854619 247354679 390147503 833538298 727696544 523875494 386158610 399085966 836494596 545151396 372600099 840137284 588566945 897432528 612107432 779240178 646168072 833838723 293993144 93136102 75434035 868554930 436147110 111209505 810742871 368752610 211693761 267140470 964920689 904389558 403450700 279350210 56712121 168713695 173430114 655925783 330288142 456532158 855909386 469949196 483424082 584774432 633862454 856138974 931407073 421322809 653482444 370886064 214207151 908587184 431248977 340075507 760836861 169674452 367137844 357739744 979424696 489524204 688476085 212256034 641553262 296303787 288122770 949972461 153198786 777826954 945830426 31768186 882990992 871686263 996553914 816113067 94521845 46949545 401542882 518125892 564566600 411305875 230411622 193344342 883906435 37986049 871730463 576071612 50167088 50937815 984761582 872947724 403996172 312543734 826803367 150377820 810870018 647053826 273880748 796193997 909068114 159793981 316074279 307370303 825280350 223668626 582552803 162471441 413440942 372247496 729042284 521137388 768228681 930474225 775903406 446084483 920083051 303597858 535820960 780875113 881183885 649462599 411144826 135080086 48571119 150738189 154746613 673808374 312199944 919862148 823791854 572069030 127726184 472947085 982635828 794563319 549776526 643001582 23962002 645134439 291369206 605488812 35203765 93166948 320091940 688753672 25134492 818377782 623650250 873060344 344648186 513369385 125502113 393586100 963769254 680060954 167695616 264213054 429491283 468664854 870686314 202783891 777863032 184246929 695519808 939489388 509789774 565794880 373326487 682580401 804969464 799176083 462556196 72713339 762327996 921205459 892210004 758043588 635585903 757678547 341772409 479837870 642745840 964606294 409558814 66847852 668860874 623194109 415096955 953757393 892179965 413696747 882708228 265638259 967996118 732100087 523052316 79353211 128248571 117886349 294427367 302012941 529838211 216197154 528024380 456315214 37405250 821496145 542403513 587838998 434451746 354416791 916819954 515145780 980604332 94627777 775590 165844075 609432769 517079713 656596951 347582105 355514582 762316484 486236646 984052461 255443427 349288661 175086177 4234760 215242399 159726005 391170265 194741989 85030530 6438937 15018538 493423860 130090201 316279602 771603160 80245717 912351481 439027092 725475216 198437163 939529183 351926038 983407011 971082438 43791925 595549539 192372665 563187147 146278856 17147118 438040036 834074564 681594975 838220444 161286322 86383160 779094991 172289368 711830990 892302134 560808269 882198196 163801825 656176210 663107970 124629004 732350349 951379097 878529815 271419450 217409215 496905163 775543213 451216083 997338673 965847942 858011561 831924955 864419399 926470713 913064681 393096924 246654554 670467954 739626588 537883300 532837221 365066161 795717109 91064148 252006041 136077532 743148304 527094466 224239154 456759671 859541826 822169789 743829078 338810355 570752323 803600639 777831692 634250609 371505542 393071810 252223327 504065700 737059450 873987435 258023723 470791379 22941789 65788807 461075710 885228216 693035529 211666383 643185432 393950075 628583865 347062092 859860236 188349314 924385850 758418415 310981667 695831831 632731927 355480102 454783770 559301979 374647541 695329636 349319323 720714872 62822650 100355468 116336695 202465031 270307164 616582120 971656556 761659108 172718745 196450987 562738176 538809202 809214069 229158631 579333017 905628317 924338213 214754804 602570984 289518264 94773670 618934981 90188686 25736999 870875322 240853077 843214508 621004574 123806592 829918015 526176262 378979456 180430290 666583785 255177070 740319977 128957219 341975239 443307219 577037007 897846509 408802467 459099895 612700596 329435774 601662899 307691478 850532182 821626789 845923953 207312072 70064848 643148275 99404018 181568719 186267373 395925044 121572667 570340778 65918955 204088274 737100912 77597660 756826664 425735775 275692621 720446523 99944120 989711241 135088782 761289137 149306321 459151162 442295219 133789872 758697920 299516023 360178813 691307464 402403443 490196124 234628671 168302392 168855586 625528557 300741825 541545212 692401793 675836164 445956480 515804293 870146373 308204316 513838447 197928660 996310297 517807525 705717930 259524810 551693080 330019555 600340565 294600741 482190069 638350202 325865995 953594908 164677248 556978886 57045553 940363336 613765960 111329128 405113903 271021147 207387932 55496047 980159017 214713422 168488250 611133572 633856991 693742846 189662774 199157455 678077923 865757418 656852386 557115428 217890933 824642514 810998498 517254611 574458132 659334748 59030997 502335080 359783398 571140260 423150961 394207688 454982415 657922558 132468201 199501336 102780117 401167814 408255004 717596868 616960738 348951303 472755204 698377241 461077561 778313491 194007499 82527163 863176453 773522839 552738270 779267246 693619262 262172587 840317584 566151156 985420279 968803305 977909819 594975673 283965149 553706907 784639668 284196538 692773734 376336051 1796732 69468130 880558098 668023336 924530465 718933190 695091857 397353865 822859825 518330721 712958440 776173908 219845428 88217963 634634348 818567560 634301117 350303554 328940121 181219824 740933638 988051775 762544578 796380870 957300209 509739557 384575858 740991155 724999535 757503125 617399385 230964873 758245198 410808521 426043143 41628403 832434645 568012264 118213951 279726911 592858250 947340429 334862752 968035495 247035621 979495167 107178795 233939692 981898732 5770554 356608896 935935006 152670986 861795223 400867162 26013352 35928515 671402472 933862380 269784763 581866975 44856975 205775584 393168658 539137435 364027844 67135549 210605054 337231678 836467866 883842062 448015737 989489016 21478233 340887898 97867754 532170745 850484212 324941164 626575803 49588575 495057007 540179404 825542247 249051761 218025709 559323431 198934685 133032207 23982687 841261339 758049597 206263305 389973591 280477858 549202047 333908122 237364730 807176984 348521267 53610372 231762964 397214186 269103138 191946185 296719430 697604829 487013268 443964163 538377562 691569912 403006187 596113761 496680631 410559504 654150253 941062462 589538032 692682478 214925599 830085727 144177526 474849822 629832396 49090761 637391214 821980503 148568613 134719805 851728798 125997442 491352834 963301202 622195072 607487849 881838278 635508525 359968633 877894909 963944161 853912286 536495651 232405827 13719920 303831898 452189894 126906077 178720767 339029777 985631974 87696689 967659118 843978796 669759222 219321400 494385137 542417509 899107882 703371493 32791089 727918722 54375274 994333840 135813487 461443426 237279421 240187786 411325687 488199606 149422382 62218294 766598175 954751827 495300354 57416172 207909151 641969121 505085953 435637845 563316004 440460206 864428232 232729762 647174620 955188239 264484463 272158863 63394048 571113031 58178364 13611940 735822868 390146496 118229488 751288382 800767004 94638736 95280251 909241794 444417763 804061687 290311000 711906798 360175335 831444229 676020867 104988491 545861092 475874649 513685528 34809535 953762299 911677443 486550665 645959231 577932159 437497483 499030140 700025505 557336925 630627339 336784959 583647887 112498213 315590263 602319081 297846935 302720953 113812477 394579726 489418336 38395793 905161351 701678366 972207352 458256808 649818462 532459354 820542536 705059846 842679016 793028843 893209746 106674115 360137103 266711957 530769608 315430432 413857891 99032865 675988064 799928431 268392278 586889881 785553518 365747656 268078070 45030403 260631636 590757035 638257227 948261893 744530292 854477303 101733786 249937273 48198685 658664066 890619284 954401319 401965718 14790951 605321853 343120585 2074712 311683729 936823339 245992687 810491866 114184105 294827821 410630258 691871113 843094170 821821449 754163346 262455252 582462589 336652445 360087727 648383587 228891046 871725990 810341537 832871527 181886602 881872479 660508340 324207116 684175691 948786753 173819715 698198284 36436962 111817449 23315951 35715165 141897960 802510360 126923901 481263882 266929921 158812628 540536138 76679200 796685542 256949611 205787071 493687309 234249239 325555813 391759696 109261302 112258301 981725909 481681940 348956752 964379870 173669723 517085271 173215699 384120797 870581389 858510418 926729979 728256394 177141603 371483918 395539954 209100381 562522103 428163946 512898744 712696763 818039928 432247085 265256548 206171916 88843063 608697993 461161593 901766111 316958991 49880755 121185607 487910338 642730314 983445521 765064651 299301198 285884823 248119084 724488969 331189406 548272554 313756629 165883885 964678444 169929765 57066149 739413657 362808702 849376921 738547413 373300324 76262168 864157064 118062274 256867466 963144725 817712704 426728660 94754916 402038573 226940538 7277617 514324702 458378821 370039119 550720295 769718579 372412379 979551427 771061535 352177309 226270869 489207551 952563559 362184983 713210432 152984011 938337977 619330428 717410175 894188714 644010722 823459808 196706529 151195406 98495732 295522153 785186511 430258609 270324519 535719813 544595346 232838975 158078508 207703690 105887434 497849191 38965887 83451875 105582197 690991197 104859677 573707999 825309433 801169337 473656146 864477205 770416961 731565294 705921200 439690097 628681982 453761893 242625052 112158479 933186818 541836692 507760636 554559361 845206952 269097972 251417755 135497583 516022688 116810788 150642389 850050753 420912471 159112492 240592657 166822091 414060658 566004397 953892186 289439178 320821125 901078541 121459893 824984367 653277178 123303661 239104243 511740862 604656325 610849547 975326658 788818007 653240088 612755071 662165688 211776516 332552626 937027784 533041603 457291833 755816188 759571664 776464941 877536745 827316190 735136590 301001922 533836491 24679896 50884915 495995669 571013180 808279273 818525648 592403885 841688447 316138913 208583661 181579950 407426085 9744100 576394233 446663975 937106056 290391899 919131895 7834225 320297436 185259750 998584668 192854830 384506988 591556633 96999373 723596567 895548265 441126212 999523178 210644687 811493088 214000553 983764232 877865046 995852356 16153566 215687540 408824213 477006220 821845989 223522133 226822761 906425719 996746832 156172436 232214259 330983046 125149634 929481536 215739107 531427994 422063721 470676911 587543889 731971345 175827681 203415232 488555955 52826916 640495207 751971131 713829775 585280809 643605589 28944605 893743189 552133013 562035831 545553644 79963608 183025852 777992690 787002956 186122088 990629766 787375335 364748087 616750874 203345483 913992544 399945667 881969183 801824667 12027935 7209849 134095787 357594378 137593452 328822218 858869117 48965491 606285877 521158727 69590828 552102968 797126029 46863052 172426740 960372657 878931396 176984842 551451242 994843829 453653957 834146523 227793253 832794680 90748943 855095734 18764681 407032590 749942350 666901310 599033713 787105230 768645269 898475253 820025464 253773009 109219899 347686157 344564773 812121690 720841776 680559824 17350072 897633653 392570165 26077990 556651246 248635585 857738228 603130203 341503311 680975857 216505155 615641885 879186463 954399834 593983121 485142665 661391647 575196305 796207383 760173768 774094617 919049117 479171183 570358308 874470454 730536677 356107238 671178314 344229600 316133560 299188070 87868627 646396812 76986105 617854398 333043139 380681423 789815369 730619262 859879853 221776851 686679610 670147386 238847561 925011286 695034036 642367306 161753500 376465324 552811787 762433961 605302667 772178246 800884669 854319943 69320051 109366717 14727418 844309006 156707256 27313119 61210324 173729131 204535085 388663120 658377097 970375891 285622383 468995554 576543461 727600917 844177355 174441011 265075509 107513543 407794125 698360947 315240931 58978274 153391428 825116595 180408938 931212985 514725050 534293145 466139717 858961794 239390594 870557492 810344494 390198819 402341918 150515691 762566081 904265805 482624078 42303907 950957238 564190791 948263051 287368218 688821547 110155742 269847980 933128163 391675161 988170412 245995518 901277929 386940024 429356163 303613715 198395679 687157657 356410928 847437387 509195572 752140504 628289995 861073794 364591854 614452232 749169870 166152281 883083550 54229527 871424862 607859759 856064431 970882291 678048449 176493386 725489944 820008066 873679264 90135616 931359407 615727155 146050326 402242911 928409983 996558221 980010144 444366092 517884009 456705048 396037364 594009445 528481684 355475537 633167629 442805633 806829458 251922359 781827542 351421647 951763473 990303234 409172082 242249883 144776250 519648627 643578662 42780079 668542121 715733574 200583396 617282070 524724490 577154373 847715660 392057409 185107633 84547717 577513717 31464382 125025996 932556642 984476892 734521203 107287660 796992073 925700702 951516328 603205273 370524941 664245491 491779500 931858122 114301005 320464813 756007874 571978624 517505642 981518250 743891882 72079119 47237666 391979426 203047111 850793085 297075918 440625312 448737522 22196355 375938612 167213006 364397233 82206730 910258537 181123861 174288045 257682184 992306387 277235656 193935771 217598888 163580871 635735791 437531545 942954109 397805735 676230474 93972525 21358065 402730469 207056914 452774669 514086608 149286466 905760520 717576791 962445519 519266084 368207335 709305610 552375976 364975610 164844727 324845663 361473595 517918951 493106217 575406563 615260570 448181098 67220984 917482294 216015169 479086511 337421675 288429918 207630179 908102257 331394504 212796511 279944586 460141569 178087133 406736465 674286360 450046400 693989437 883941829 878598990 77664833 622163099 751565524 421860996 763760437 513482134 884431324 218782404 643670254 449338166 517401027 695760852 263305993 112326181 189580639 876612773 273622404 183268581 656613867 788519396 167041807 790963768 428267660 326195648 251864743 914192810 985934975 721523145 524012756 503872840 664225524 914975355 740573294 547180828 801693627 439087457 939597758 56975593 718070369 912245821 109640237 87563525 395899219 93666935 947457335 392564 894311338 960736131 936593971 326912620 758825933 616755669 808113345 300550368 835662388 773872512 64290399 453668779 179648071 323726619 57223509 796244325 701060670 986736483 612575364 799217152 786002358 494833400 971901157 195904995 281125121 933907302 420368025 786662100 41125599 549357039 22792783 540103849 748408919 516301806 832332605 290701434 969415232 658035834 80717812 447088590 710087774 718144866 316611330 353987098 471817463 767653240 385245288 599006401 314532599 853930760 583273754 598406707 989001718 312143927 73347353 363358154 101760883 804733175 63351452 65209512 275068252 277706302 63270436 593001263 246914288 503852878 295809225 8182442 383790060 305084957 678540082 671735810 277497026 266374310 831946511 206766524 54462850 397218184 232101956 277809196 309612463 318422566 782499888 654615688 38369363 598117458 458880778 313715624 610455340 593772695 798562152 524803677 654000900 353471267 916608474 793896811 763738398 534524239 871290547 790117668 358485452 163920333 447102951 300285602 853713950 407494509 325826832 799665312 587992245 755174028 288414091 452817910 146279349 520898841 973498047 774252975 943245273 628214597 518808190 924506824 809133728 586997959 949609859 980099464 219843493 40945865 368565275 649229430 652413196 294142066 888371425 585808664 473369616 592357282 822729110 919383770 149241570 514256991 376171959 931130372 958409600 909800048 691360056 500252636 931753925 253862220 60765734 321754184 142162983 552535062 768521887 448460126 534632303 246340388 591244538 7548453 141525674 914516023 637778246 956516180 781882908 258643845 655629619 957460155 79690106 370032276 652759925 191296151 58349256 763075688 653773447 100879141 436414471 78386481 585680170 346666637 905229591 932371538 757142932 450954589 682106535 604964998 316630122 686403794 575935564 639572789 915244525 140973467 163784981 953200643 537159460 15243445 76254669 753316739 179377065 644082892 441781002 233250830 615460260 188743546 457293214 534860522 181491396 363816972 875904131 104743281 969080046 133410328 745244441 88493509 778912463 296425933 290890384 357025982 458677241 121458220 222521838 3731839 270841949 194045526 631848374 948460792 315374050 479665156 229177032 970233614 815079227 456034849 816841152 502509828 325521541 555939232 452844641 403699303 980326656 98677805 738770083 865544533 77070683 511795971 567245162 186110799 142407052 908530014 569610262 601632150 786378446 946105593 910989196 926391108 380630750 306761370 841074289 357569437 304424114 779461839 730535168 597821329 602125076 487391178 532044365 690998486 18588851 661719817 318106271 485533012 211352086 592780286 217753638 940660541 949664259 902454739 459704693 641477367 417631217 394400301 715476348 711104715 514215671 602860101 295001888 990455134 730181838 499215110 659949727 273855966 975551535 958636544 464325911 335854471 10113181 942031680 628498722 313705041 367754646 270901899 604551234 30364850 622505217 735793183 483187248 877592678 134118772 42943895 799989550 186138952 352445086 689444105 352996694 490464628 289768138 488745758 373848934 153771429 282642462 516672608 209617192 401872769 672616569 635298657 403256151 300182024 978336218 461748713 756744379 999791943 873661674 176578311 408026568 76653092 316714610 506611896 490044742 388740399 334447637 603840273 19443928 416378434 970350801 943872373 664199591 744489379 715260131 563972320 967251369 235095311 204183749 710129004 491501604 734531101 821903883 893454879 868626428 877545113 731101880 61358941 683551552 462450340 672971476 227899471 809157760 459677540 184870664 607432313 401038886 173566845 410647708 100620531 291557997 32545137 789456561 730597825 20011937 598485157 49091966 594131180 192359991 176906510 56302006 472859967 389636599 905549318 798065307 546452052 277121651 364867258 71264248 337396700 439040474 985891711 331702008 949351626 915755777 932677955 494531881 468383417 425545594 949211705 48746200 863929203 514288260 731389944 925668072 230238481 636457411 391506982 395030586 252991091 945566948 317298835 624452597 796482978 775574315 668454748 622929196 897969584 368782761 754936542 883000250 874940759 571388871 399978298 688360940 511043958 332981332 94386350 87888139 219384503 211700927 978186897 982602054 86510873 404180215 967132641 382387558 35713875 84426190 740107728 161331053 690072990 719107069 482698755 775224895 231418731 392911737 328042558 827514438 508702604 855651383 481674558 334186448 767311909 414253491 888862907 716541837 748945014 5972518 892262483 403502922 313606205 436925755 762807829 556706380 971277565 824326 108170067 721652895 57224482 260849589 519692513 503391853 544855941 829313800 559768995 230912297 134443845 197699611 422694951 398952751 599371857 335922964 16902196 32704138 904856544 674081975 804266548 733896293 638481026 76115655 142084739 353852540 456284760 396965570 157163223 313749814 330006390 782248709 262862078 956099861 177161263 161785415 147852974 255767451 258680498 782720762 14919898 508707536 690287584 386956000 18638231 570558939 412690766 220859646 517773850 330014890 909762559 459910757 197457813 135753146 825416336 620987526 865588275 300897353 163324843 587238008 803057770 125935165 58525881 628830288 385864802 59404778 522316505 454801888 537204714 88904769 162033384 765744193 571748366 750939445 466609225 435531680 316686676 162165859 564943537 253144635 605301138 629242604 164199566 731553159 908856682 459635811 662895637 208321396 742746468 41963746 326614247 382778824 891849382 884074039 193347679 584547752 810054994 117511740 585164922 776174716 89400388 501853540 220036947 795145159 571661233 749100443 186203013 479346083 361841652 988524292 495000523 844941060 36728207 282787370 618037341 323737379 581255756 105028713 877511460 221717276 693163404 288173325 672896431 171597689 69600924 955828651 890847401 624427827 249206616 310065438 503756359 277722177 805187306 399006749 748101082 451666625 426318000 596230006 653669508 973864130 35167548 21902313 179478279 347783852 941195124 275108771 297266873 457242188 880575450 676717398 348253076 515193318 960384873 776769404 199155088 894074881 974156853 180857066 89430948 449859468 704344436 362790889 783251493 614112562 805918448 332917828 119821369 11556553 189966116 665786740 407778261 634441892 788236600 842119388 280487082 346624441 889091718 483053571 272346174 826304181 773915974 618649340 890961320 879668266 302881755 579106023 640398568 313682617 713240720 815060961 990673753 172971828 770452723 603636058 615352164 216060982 242659934 407969795 692157534 349465450 175235090 70907299 288244419 978063530 31105335 90965261 133608354 127523057 843223686 705189045 20946955 734440709 357092084 908998329 698306287 580216558 562283433 535251697 518933163 780860849 290790300 714874242 167650101 362294473 586092176 963120353 777331472 452347345 215307457 820566704 83530427 731969527 53652916 419680340 241024286 979018184 363248105 687448798 430899662 122420096 311495247 845586616 589527481 194036491 179007656 210381009 347628440 260197527 717922369 962240818 194871681 402905012 451298013 380383550 202021273 470830372 768934832 814958986 910100967 437697861 445544071 548097878 707244355 742009112 616526597 994552744 542485357 723486701 368967175 701164548 966681146 706150317 832884521 518223050 270296040 614257092 733320290 621321004 877602451 773312681 339356106 344781001 851213505 871904267 792246653 295619307 281478424 112836505 727561111 698221402 650062639 501285486 635373662 586237659 650897793 570642712 795171456 702538056 805062723 138249585 842981197 519503547 94830087 406198262 20240828 692435530 358150091 364577984 66050190 609464613 587859156 186986359 141677252 540272494 892487225 890272805 899082958 352085685 522746900 921286380 730955008 339689964 616309264 183470520 957880043 702053897 908400457 900371156 904457984 934910026 61296652 477710360 669782530 280336155 151217188 424995811 148306901 472365159 137521356 649901202 300801293 501027158 314257487 242716431 841666833 108373047 332586814 91462785 563487467 369437306 170888481 221168304 994590932 6979531 371896364 253654407 143730053 813220797 158510324 378960983 918454678 265443089 618191099 404338836 601818038 146606231 990600185 173866425 64041503 74316103 733532961 624539749 396700966 232935977 606831770 808249997 518461428 106410673 458543165 827958938 48454099 465023280 809036986 441000160 373705506 601078750 762675928 337259705 704200547 986051196 958600409 801908542 757603950 819597481 527036923 869895073 304720072 701969603 510467099 168301354 688097551 404202872 176978293 463088844 943709324 690948584 919968902 833296483 739830507 747356280 465395730 371992973 56388358 325086774 240008001 630322722 300678877 632186084 716964837 803639377 638927010 758200739 679118551 860903000 908672241 75068031 846605341 328899855 638815089 779112178 542664870 790164370 299555636 694664346 309424838 372316548 118672671 124362006 458175274 736744631 153285469 156558779 259381950 836652405 898361957 72550817 487314318 201730192 86520473 577035064 937180161 177119956 857514553 845828958 503919427 680741609 428137442 226047673 465380910 716094624 88954598 446472585 671800133 530100056 362271280 678962057 477718266 327058550 268264416 762183041 407256319 672524961 339649735 965730942 231877328 540861118 592483237 350852520 764584392 86762740 973406260 355804282 415807277 13435296 769969726 104119712 346462420 906685657 509971162 61989714 271218314 604003510 996207046 766304032 377401576 583343714 775684754 739819624 35322339 86143000 789570508 440229743 391566605 603124544 472802646 301813150 793130579 641632648 446960942 896804187 268359070 720008456 598602607 216580358 179065223 215279061 887401910 366824213 260959903 243894271 830769889 165573095 989699373 765541268 268639112 174226528 880158114 841193283 579966438 864753006 535993130 263068561 260424837 487674752 756483819 813458226 304227928 673799716 567092838 329139757 979419594 321992140 258257279 577339263 653693521 973145181 714877318 97482659 814037517 870551771 121950762 839983962 947527749 65856669 125534997 198809871 787335755 731549539 589268719 827357776 795919645 866247869 516388880 705199199 297670572 123573056 374454311 52829497 522400164 495534478 996987916 950992591 371275120 891221295 312523324 92658938 382417561 532127990 185325746 484996896 880225404 997509201 414832017 430673963 298143484 550893424 959860415 45800545 685021777 478952873 651886245 450518939 585641415 129460814 538471636 57941600 850046219 743585335 294398236 661648290 771456441 531569415 649648851 628401981 514064502 930580677 321236636 985095369 344560056 828244859 496557350 794425955 523439002 656175814 41736125 942092917 789159241 127088388 22112466 16512255 523065473 532781431 94908125 603997815 351242006 275001763 622954242 904351885 429174308 218860805 245660416 41841481 954139515 707623438 15323547 62384207 715052643 505527781 506283757 949926616 792988139 915019787 615597991 590049567 886038902 716481554 718723071 897776795 542343550 6142249 313597428 282376787 706351660 517638505 455655517 105227266 396502411 696642722 692845643 20790474 650376696 343521809 948187145 914433072 901296725 474430174 960819396 937623453 841845434 726905409 403428792 697280284 828392718 609823537 740250042 618798361 888388820 378550025 218801622 962130743 572093970 217466609 255713348 838053144 350159092 667947478 741039993 34035846 408160666 522105765 106063280 710719243 675534187 889894200 97833300 36543996 762450737 157939921 580724219 99215776 157084705 545253429 361132830 272952388 161987183 828303497 295821337 143766808 370214432 717676988 407533647 298642086 709301501 414048403 382851947 610938096 50196387 625958738 936690980 795170744 291612932 158188754 560832766 156529976 896788462 303444410 36321517 990181240 141475060 127688885 301727741 814296726 390345013 45149088 733805213 693768790 979218039 820060255 206640612 435948258 738776597 797728900 344108730 512274958 120687714 522881007 795129593 160447856 348767697 516863336 114232924 689903556 621438078 491021939 278848882 677745353 317429228 261350204 267132292 578375462 881429771 735242073 580589584 49543302 586642803 165442432 262650773 773694359 844488765 365299288 707349758 874548270 974277246 934492584 849532807 458153788 735834130 14680032 500419438 857855264 266167530 144633887 715468834 444061708 750462088 253317221 240720227 602276212 524494776 635206102 805964851 347567635 135202523 697782460 142026460 540387910 554796417 486625731 87766588 519499115 866414680 693747287 453676313 359780864 984400399 710367441 209298324 385148582 292039310 389279429 343115381 374586857 132114894 666239737 897742500 878942403 873611726 795522720 106132763 1501537 47930835 209925234 571008573 922086314 755395427 497500389 733952484 415319068 877582529 520280844 534953694 357021267 60460780 272090987 668004432 543738230 218830221 229719743 318312800 51956244 879326439 84339645 232656193 37324157 819862597 296300434 676249078 224316002 731183507 537032469 169015560 196705420 949602662 627814185 484079106 738236440 162007754 190847847 815379947 125940926 295343801 339983469 255080022 217684498 865350916 457819556 284014382 876131970 408651641 114350479 566695941 543274044 554414980 198233028 131776394 327894205 627451378 827411592 958390806 447325905 306078213 430535013 840640542 507882868 930285866 422664034 418523920 881138835 87360544 121173018 865977439 757606542 739192420 93076179 755356412 582913490 217630341 574231606 387266945 792850260 25448316 279700391 474493466 4844859 463660451 411657653 833639697 831754650 126467924 6551981 425156086 731667803 340984095 910299495 88302903 60999079 565421958 253957506 877799137 212322707 429516004 453348930 779457098 106737893 897983580 484662637 432547687 962898737 434109272 792929901 501643471 373173772 872880365 51592204 472604804 808377299 135265754 335459291 940335428 536654325 213555881 937839835 715176468 971946546 287302771 634295072 41293657 165490473 787506329 484966720 321585593 43873553 547045990 338215342 258655623 492812549 596174311 415411448 571727490 871367365 194892180 498990454 135960530 694458631 903011713 266523949 434383398 534223383 889678277 480474871 217159405 959072110 900784225 259017261 1821088 624304032 98071841 809178480 239011944 628953814 748704731 96458062 180677703 36305054 803999858 987654575 778735556 177135864 267498367 129789715 436674124 736129169 137712519 572057699 900685840 733050349 325411422 114817487 528559122 136829609 408835526 250335928 398458549 189755736 652465111 213111120
