10000 2 9 628145517 376140463 883515281 186969586 762888636 326402540 98152103 158176573 61402893 127860890 9580639 570870045 646139320 178509023 484027667 61263305 841082556 558212775 940563716 26389630 579113529 496148000 925801173 837151741 70301174 656585276 285845006 902071051 403573724 727123763 9467291 296231663 631265401 899374334 520690250 798571511 491747710 799313373 643215696 789204467 614608449 162733265 456517317 555253432 806956092 181457955 528156707 751354014 158398860 152040411 743974603 458000643 37883251 164556874 882264705 205461190 877444310 167035009 785986539 300206285 732553408 775142615 132099861 896205951 555144413 457641319 19344368 590064714 506507264 909420688 489726670 55434271 793692317 210461043 901329639 537850353 29523792 614794872 570497240 905203770 706091348 904237002 118054687 337246325 307178253 150625750 896162464 644505509 271356543 1738704 865692963 226102989 593986004 122173998 807688148 583502198 468916698 747545899 468884929 620479532 675026050 541326149 747075168 203959041 191528802 491192255 104714246 101365768 179252 960570656 244081265 440998363 674385237 484916146 641913151 917826070 670850119 607465477 197877364 596079578 260773936 649320809 627715320 530909771 795364952 666130551 863834903 618524434 978767535 781321609 717028607 338249948 328373828 116584253 913989446 166308313 85199311 688253174 585283937 439133758 499892264 163916122 792406062 887651011 937745614 322205909 136611947 842842918 654604898 77623317 702064956 112541862 243836201 987809421 711659178 528855176 533456269 546812146 738903070 650982038 6347420 108056513 926891754 802439067 408151175 593571254 26183360 189607912 141352740 21890134 29895225 60051922 141356141 928042087 774860111 15765553 760106751 233605234 181391331 366127331 394679452 861562696 565366329 857043783 155504810 432087162 146632055 71055043 615622322 588455136 334302762 867602751 305226977 961242387 798641856 387771815 245362314 246358002 582417935 57772653 563361442 101654817 957259212 157356036 311362 50562949 361231637 427997030 15933737 573631434 744665832 278265999 564361783 428089053 628727977 734460159 467628531 7731314 645915809 619188796 238727431 4601215 88331385 918128718 870864063 742483647 569235395 153311298 781575053 33386289 692050545 91768488 17776007 295244438 54166876 313816596 394647783 234755062 258294463 968789408 969193611 86041628 184483001 833089385 226179699 4055061 122467278 334102286 41427013 203235253 164843367 950663220 210101196 693163025 976173645 989222148 161894772 611530246 12548914 621233323 274117328 376079537 853874984 75477465 634292501 212243445 691845672 648862019 473847709 425782009 635869581 19473953 420609637 198996647 616806550 673602225 53290126 279393326 961338088 782168754 422589151 970499969 416729353 379641322 800316994 793940438 214934245 730625184 394969667 117470247 218055245 703117346 738331540 85428660 29863284 329898305 153203339 72865407 778377584 745197264 703186338 105563599 53312703 498269224 781534199 730060974 399552959 53667751 182061002 333472874 228141365 520388909 472301826 650633496 430648519 904788126 669286311 57427980 927216002 329000034 28692073 420020835 33339989 921204712 431545624 656697209 939969171 638880286 851655466 634178419 611182709 722349051 10986040 366747062 827862934 933990134 779079809 959846254 575075189 837614476 211940198 856226313 911405559 675059646 662413804 269147577 846206434 766524816 87516989 918392821 330156387 507863435 206036264 68368376 695392392 186976572 295261852 900777793 398615495 249680306 248748593 42621457 24601206 163022340 9940127 691350512 445134161 97371593 750824260 706015273 574966007 57981855 279164578 926989897 93898861 761717669 927952095 314633892 692477849 889741824 936211524 979813072 472616392 380135770 459249086 939048 830572585 96448862 734324576 165450314 52046927 19955005 695371487 981553561 463536819 260485676 702243861 24537532 148656432 591003107 497589119 322888734 367803781 652840224 57022143 162019948 764116951 832688674 667023642 738895129 608970028 588667695 264619514 528972253 719217137 669333775 857661294 61820978 675902581 634910094 542817957 482898390 9719147 270539261 784365687 671155532 688620652 597378482 479234012 69453403 645203571 185554051 356952178 701772941 459021407 728536399 534233339 861910961 4860789 403607670 888331741 956846681 698565083 788094556 27652513 390041181 971368734 488312298 933552501 42022230 5127853 177019660 125553578 127094564 622876764 785511732 719103542 868495465 71047394 219485654 416880435 623810827 30920283 409872106 129735006 49668790 817164486 1915245 457827993 495370072 804626056 600640480 990016105 920192931 527093991 802316487 274625656 850368910 593594000 560686379 756056853 785696469 981626898 855680793 424066479 56480628 942689 811932705 166168414 720045104 371382612 856995800 54101850 317078798 938805799 108434006 153580929 331493338 873825785 874225337 964075734 289217185 246312015 939356576 907070973 43914807 197307791 482383793 960417728 586642610 561143174 73019923 931392396 157495277 305337827 45552884 769426421 692611079 790194362 133848069 402740014 982938081 34562818 481951993 245478801 168162723 538681111 810120201 229213213 828022072 597649208 914827891 578682611 933450445 244541450 398405367 37570521 427200342 348910355 216365144 134311095 959854857 238506304 601378785 454885917 927830496 287122784 731924446 29524922 846345756 878730919 145801758 21561574 803482301 968637228 824510072 677479193 732757003 537352811 285567299 694307954 283077648 494002116 377520604 511692849 433664283 29664505 640872739 464058173 411223102 10845364 928987134 751217311 646758353 600868095 406101461 6464517 35193838 627018186 437036821 535333440 939271923 839153513 631806894 299911110 938876931 323640595 930487701 204781873 955992452 30932836 63622978 275879358 124689826 531397339 52922930 362554319 553565899 442693213 645375334 510833514 21462065 896492976 860769251 934226103 8411212 12882433 137061168 507745925 28640597 488336992 146145755 228485318 855991244 707044926 839054836 904208143 535528179 81298421 382491536 440014617 319887184 799805760 62538568 385345347 170554159 141525951 194832567 267602189 372491549 713944949 1289983 112956318 599123567 961120585 936634693 416925247 721500601 302152072 54563633 638657246 141695319 644791906 381525359 513726605 18058216 55006312 551427632 964247040 350536909 612870932 373822890 311565330 990863022 866505538 737321619 823396416 774991350 366740911 519996074 899993388 580439378 610624385 687233327 815984411 169653814 844432063 470680934 543629944 73310040 54458068 660900120 394623567 923478835 259728656 54755089 185174227 236365445 844878631 89858467 146545625 604051154 678890928 487186722 358418266 303356127 937642151 932514406 854065141 681824055 638634988 208600396 248579435 256680105 436823489 292582197 407428385 221710024 649145680 387896709 47993505 961817706 23825187 216540197 381666329 312450089 106958250 761654274 721414362 6209253 649230265 312069516 801992666 979495489 650585863 842044216 582637619 423755553 109458608 29480958 277976483 245504050 925786548 51133915 60324618 91277410 33521526 943436881 432878830 707094884 14867006 2412258 53105658 453081645 648485303 444935064 669083514 5213562 423502705 340158849 916432865 212256840 503676768 465186603 449655108 623243354 362295899 21165868 449465821 834013878 162339486 93792413 506613896 357304872 659821129 301427097 471465801 237243838 557261279 7915971 827362756 40658250 970638024 239085245 513746883 444981731 903655887 459005106 789089204 87777381 909431204 386153678 101365033 202255340 980720987 333190080 366712662 292362845 185182955 70271039 34741654 479392989 192495024 506911105 266958822 297903704 883091690 676357573 7741800 310901243 922829372 759668939 988954338 100460986 82355246 412176983 553072445 151125196 80117931 982234290 811014150 109229610 727925635 884992809 291520496 934613779 42367722 236947596 219715920 207133067 27329016 793257391 729965728 989263575 906567975 113215469 970396413 958574082 27223768 355915680 952971432 465229403 286801358 566781610 852680584 522578421 600253360 372770543 978444711 395650086 226830732 53866713 267170737 155578377 652960847 211368402 817936248 683403004 187312462 34214094 212135539 50814754 38703296 88458943 610911290 235014626 327059521 441585950 270264587 546284134 60795729 130720873 759086152 316484638 563832787 555354271 890357495 111296826 16487055 508869061 986629697 392229171 708349872 544804453 300434931 849620802 921395015 498052618 474696448 406999271 598719942 898340806 10423805 43621476 274838661 759773356 142886308 919955264 234387008 336466518 651592018 26016453 415400343 254570847 636130185 17777794 984306573 241021930 37012078 429048009 360032778 671522842 311346251 964934962 352376409 494291608 443217422 129914134 159653803 119803152 740354505 526924309 701609362 687082676 891825968 942686865 33220742 779210936 401729566 915408944 798404195 252995796 841491217 604739166 133423337 444310469 183584169 259041481 241685563 749917643 690751277 353827299 344336225 174993197 296844038 253632867 670916806 625779377 764652353 766771908 752210107 135715877 408994577 927845317 531661810 721307353 375376203 820609767 706051 803218465 852585193 777168371 578368491 109294040 103863688 173791345 720232072 953737432 611492330 119677490 787545374 523869059 860278388 374226375 72115669 17879614 676743601 156301063 491704888 52253680 797117645 698718605 251649463 67868295 959170074 957542199 661380134 784962419 811963279 434589352 769649213 951355433 423873860 524073415 817973782 360499874 386916344 87460927 70564786 425922010 445560715 289618429 241574260 689074769 943765892 442047925 35525796 366926989 647876492 960157532 253005294 570874774 609812976 548584111 42444768 754163576 111190563 500682155 52703599 125272004 794461499 4740883 26939507 806228496 728288879 711884014 76379174 924831859 954550687 163443462 616210857 188436490 895833548 921942378 55446143 761005941 876142491 45981933 337284880 220669274 17670615 268180388 930035496 220919521 808858092 402376556 677247093 790552119 417384045 52495970 351844108 673601804 526275982 288132457 69997029 487429908 694185387 285730983 670987610 109813898 533813695 756026888 399424940 31867560 488016878 559131066 848816510 792217648 55547900 63925423 690871384 967175142 982826451 515202335 813576486 799515411 389645312 882893059 466721974 88547844 671834678 350199963 520740926 603368585 747666379 431301352 954420179 651340919 860514870 875083315 87281907 54988327 536090519 609099396 925541628 62529268 432187695 428069932 999519154 298181056 564492772 984633916 51454397 309945712 277095614 377877771 878812968 345906540 32036205 2432692 111036900 244133920 205546688 962832278 58187843 772327293 588328751 117475538 830112638 343746424 155665234 351362768 642632239 994137226 762137192 77079995 15721175 70975535 327761105 144916992 201049689 405061991 727276692 759844563 132479614 784500536 244760538 143555754 490366063 657384234 657779569 310083520 920857406 168889802 33928011 627478163 73542237 427603751 788588284 640708710 605254692 221093208 192329791 344005568 896296016 919253748 475887985 51242219 322781823 237262232 311039508 936524918 904950965 628429925 478926669 878149044 36632538 94471807 619408999 636374331 623322170 846770575 946605902 39304549 448867332 384991298 340433685 839499474 65663435 426920136 478075505 610487013 650909960 402907989 972605499 871982658 18159765 211669156 551840754 885972310 741560115 425783407 55245366 271666383 730976774 20774392 291324238 217608224 182391572 775346308 597872547 69940734 642302409 563906010 894038595 591732966 5764982 877759688 140504416 409756052 70068685 17369502 397082830 247089549 801484135 471797425 887960200 343472023 641189950 937052890 253831467 251351099 703747124 816496628 549197433 450837578 56960906 23791970 99430872 340588373 893700457 530625158 987546320 120942132 448749661 69129035 32422801 127118720 365361364 21952668 838820714 833511448 659391908 56739563 749113683 307551648 354430082 547386539 14298213 924829949 9014924 329285334 456489052 649281243 177855680 52570472 539827228 16585767 576366211 911263202 375095337 125117589 589004827 822118856 985229101 224145691 480928564 938538275 578409078 268291700 690936671 24018687 155823222 921723807 795539599 865865198 126878529 12054109 217797018 212281988 816763666 24332726 680859326 454003161 423616710 823618164 743027737 535253514 89695327 195763623 667026480 51208376 53344643 59820319 444764777 427201415 324574203 56271349 640282000 358697632 990633524 27518211 682527318 111231792 643741633 22140263 50949070 81275879 881364439 970214148 762746862 659752314 297486287 660918529 900417044 692668706 29777832 54973512 220358014 907681562 945766019 604529160 22437329 496018724 458543909 96499252 26909587 807519493 349864056 978377218 291365553 53189380 264521226 27562604 577220857 490138736 22951053 166911666 387625121 171290135 531638357 402212566 749910719 398793423 69192157 390248991 226879950 963402225 465099330 308428182 188988464 349877721 23083463 322251404 20367014 908812903 673138255 723746067 511899353 740479873 794784742 593375872 409396693 208610191 79900985 354531311 75053705 535398909 845681177 703817919 451779656 919953853 354781691 65150226 550450507 622673858 986461819 231229518 977585453 647534982 677853653 864593823 617431917 726203269 142321003 38895730 428052976 194465728 21525570 819621628 391888764 614020155 856036740 262390961 358865470 474800511 505972479 557512397 486789701 232431897 832405413 443784398 205351940 500552729 17443338 179240696 72480980 913967508 588312297 739587280 638081904 737092898 931942304 467358626 937412215 142873952 366071983 981314811 475910894 16030319 586150973 872684847 843436219 279256180 267404434 809560532 41280299 38324246 1404574 722382917 438723437 103380739 387771505 882107424 220812052 844649067 796737473 427744712 539680409 318590339 950516840 860518628 451997655 613341700 28154083 544817886 43733133 464382121 293751507 618215782 4821728 425996213 691412352 834803948 358598102 124158314 373071953 374684457 968680412 475280019 782782293 398362007 167876929 133501179 453412798 829646836 533873848 125594100 211731040 30941379 933839834 566599889 464641590 75943371 52266402 194532716 230324958 914536086 589212912 870619809 61727512 176484083 171393798 939834576 272303947 120828788 113965582 73616991 906725376 855740913 894959506 46039094 234999909 745166851 448126721 845100098 360399051 707924362 643298353 274884595 613378344 598316840 478735832 703846589 206459797 552250563 682582034 9480858 486760145 857223175 395011806 4788358 343124157 346019554 964090017 536293122 874416351 830012934 749078689 294344339 65163487 392529770 258447755 474150976 574773516 238110922 442687470 75949591 50330840 401672738 584701118 539580840 594422615 423924791 82319314 312969864 714922949 697716494 902103654 828921039 61328381 190378099 40206233 268136346 200567554 206191219 465776880 878424971 285260154 229755362 219335889 858648900 582039598 882996438 34362633 872437744 260640908 36944170 925370183 495709114 780437797 332348157 930617759 703728723 358334511 191091504 115916040 587271024 918484484 531213803 880816094 107926346 681109409 342227225 345890912 303766813 307214632 446964455 591142707 944846761 50458718 419309641 237986269 7017396 801668910 466908021 660936011 890707078 435609124 764562021 59422284 15958123 492386035 384650586 643020308 14454069 645373679 119899476 413800634 35680439 282255764 608469659 251653050 912166219 757455613 56462137 964982388 365477453 799400558 147741053 570537642 251193502 104940747 813591161 907846406 590598434 383897374 42209925 965967250 715653954 631957781 359423419 545044030 11421546 590888833 980101753 294346078 403253644 585268952 967547874 273393193 925142940 955882932 948389468 258210107 475553810 17381202 761341971 718477075 170113132 202798612 72162677 171199126 997307305 920587775 290562484 721070987 71071438 673072958 748767560 313880861 70762340 918886557 518100074 692835420 688678904 943870479 929594266 994017979 43445914 918279977 806701082 602808468 690978143 257124772 32925808 533486496 863725792 946013151 126914792 111840639 45180601 801194842 152081935 770895414 551306762 284943164 412688186 854185644 152068600 329041614 410718973 753668908 68952621 828806142 252891060 129222118 348647764 882302429 654649853 93411693 866527647 774102818 394427196 699466555 526290753 335496356 881016854 173659689 384304372 122914788 655083255 187360503 560106612 46586241 225046156 63154890 39357697 817306561 57963593 872988585 369043937 696151311 315413220 576210687 359934172 430883447 186626264 164902428 50391231 274043436 39968483 849269940 45915609 892997123 24648841 397707614 13916801 656272885 48357007 959179798 29282702 33245857 15862656 376694972 42397917 222758855 370260523 278327699 50771407 305221326 788722211 880329154 499338696 434248000 213279294 756559830 204209329 331172680 405281046 499978302 316117879 597646907 580748171 612968398 365590154 404724492 233274175 68726333 347059295 147809494 480109849 912416936 253668334 477696854 711253955 648324108 282608437 929193326 204046892 331036623 637939123 294245284 409250311 442071096 930956013 887679649 391600713 659370226 251421933 598906290 457976239 297729933 57407166 647229770 14270774 493897213 220095217 49544574 387934881 620604697 34615835 422799495 805711606 740112157 975745365 720234820 411206913 434037289 460794043 154642870 953257936 451730112 242688493 719405442 482012469 734707274 441237137 716324978 600806471 186051986 688299727 766396660 430687202 331968328 870176723 827505305 909443362 64592000 393509455 30829720 98215404 277020977 269920502 409598025 970391397 612184760 503037698 561550250 543980665 776056402 293865135 719879133 86568021 407547301 64959934 978775976 958680301 250359608 491927027 190724596 54503800 848611574 90908567 902876238 946276591 839649967 592296950 6397801 3515025 213151895 132893154 15163290 658136673 19831750 635612719 647189338 456036263 161601206 901313077 339384776 927008619 32297928 35521105 613589797 978313469 502612927 472806500 7383894 180427376 165586498 934075987 118273637 650605338 401073759 793296005 540657408 17010710 447200515 819652712 514878713 717941954 659628931 296034028 205983172 677184833 72715286 177477382 63895804 355358970 631957081 478095406 928170719 841099031 318823881 476479714 509095629 23492359 504131660 666135841 203303373 246540029 46251689 8203505 769512711 528910959 355379467 297818841 822714443 191944855 465285507 463856232 294614153 11165941 292220547 129992364 269839959 375606219 269978979 625735867 272443503 150279328 582509791 225443374 518133293 103685310 67259799 796665761 542699029 596408244 716195470 86742836 649077835 571868116 68848044 786683661 804386074 513657014 613069884 938557396 207650670 704570803 594072431 47083318 750317401 157225067 757105879 492588642 410138770 510501696 56592108 26074767 201220337 933510104 183145866 598331764 57479412 143026591 98700401 713022414 313749566 165801027 906009028 934633438 669006866 34472502 651788427 436163048 493336028 892094255 538700594 217868469 912083881 30267561 70484999 628364306 676105386 188270179 16322495 630850383 293495733 228277470 266894833 961231809 389177796 39487459 140639130 441237312 736335988 776621818 66062232 479216297 32356998 32265203 303955247 577795166 198117474 196719457 45340295 955306689 643888783 340975387 33616171 469766844 320908348 181301433 520883339 582489661 476789691 452048413 568533116 328889010 123217665 286034407 198274483 550700945 838347303 708375039 624777805 209331410 429299179 211373583 937858122 885997939 150518320 664540679 824689677 142393844 782033017 10346135 741625566 584568536 452777586 221292984 609921385 270416682 650807400 927953188 256031292 968456949 20229068 833259737 523193420 981150155 639728052 903986074 758845809 450961727 14069594 274609006 194852069 894476139 473979547 412362783 72037321 39550315 25728633 289447356 624787872 217773536 208231321 816558872 917137106 248806254 727364806 283508808 21575467 880123710 360417132 135005481 49772633 160958332 784911390 679651288 379031665 224294362 972591888 691684152 172352619 781508108 918376093 904643951 94523041 804326474 671133123 660266601 437079892 877976529 36210338 596950612 545294632 856358242 22270209 640803874 64029603 335957441 664514761 814971915 854359473 874953784 592646280 572804616 991580195 292897042 491211759 949664856 171794475 526607392 788458068 943116799 420520417 51237687 16476465 6690627 30466242 930810031 284628643 772583981 612226092 433848806 539524076 666419470 890269155 499877307 159209457 971771127 432570511 697203475 71589821 492303935 862199867 441569112 879839996 179842305 855297752 812608757 617618049 991080348 473919160 598295004 290698945 267802929 800900372 527193600 457984085 599588904 25084550 655290843 189062268 30057644 492181391 571561192 61343126 114044714 353141523 274660394 17123242 687455958 514914520 646707364 71646945 676595750 483394058 303453663 217456137 652723029 877947322 631705703 32087315 688499425 247312218 760290382 219639701 33472525 73959747 718306215 634366793 239164256 785151791 969663756 721979020 397702948 582476991 471104025 664293600 166679016 311811063 769887727 604780395 276482815 413747133 35584946 619597685 44567295 693192285 647236875 285290734 3713090 759532552 272429223 65525478 463509352 64542032 796541110 778652690 776000979 758507950 744102253 547721550 17998378 480488956 181583748 610524181 82389719 851592955 923031224 21466891 440545929 533416911 964274250 246546036 764396210 768772222 325548415 838466234 30985738 856117364 49017374 78867179 781835018 737173762 793744117 585889592 200744562 34998746 27980373 560579448 789310916 541303189 187286673 737032610 270592967 817869870 356720258 192210007 49198852 731154820 33689606 343038294 14948940 248341979 373422204 24799749 492336944 608999003 293971786 461873135 165087368 873546640 842875480 204206912 73162477 510874601 570440850 71601995 321726782 509926969 164781161 842566917 756695839 867281977 241128019 130655111 163304309 893406467 876437319 341632656 431356652 189806488 741182273 154615553 653660785 297532764 123431876 190328671 485816760 574033045 328858195 834166356 955413943 110101232 531135223 730542382 574234409 317657083 661582525 243136094 711155981 672524204 675327540 217489403 898369316 497075416 488232947 341282365 178150518 340097981 585178897 322660866 193845709 806624377 78081451 666275660 362308665 985081233 803614562 899221441 159652746 766658155 281225179 615224617 4845273 614707668 374135101 116476916 223640832 931332218 515570358 652656050 716746525 21551475 196148982 36202905 897690387 875587252 48193714 297302274 334004233 401539995 11759906 9792492 691085033 402703206 982359172 403790199 904468706 4483002 318976151 402199659 539487719 752770845 539141408 75621295 600763182 678146940 21682793 578661074 717855153 441471142 117725629 20602501 223198384 518882510 121789421 817774367 974839853 763383053 429940687 537600792 112916335 710797277 689849 593252750 666930047 557217696 486685962 577105091 285899182 659797271 332471457 781708445 40105998 635089388 953624420 22685989 567305716 201894696 734182331 575730952 69176444 695626685 64031507 899172377 725775109 810860286 236261979 839416269 813143985 531723041 900451466 64373182 607402982 363916228 7041815 21215785 475734224 164906085 455357567 785733743 270176220 791970537 896622786 362080151 539601215 53284886 838968295 726992075 118080109 697990169 13892212 176820695 826758306 856980737 118551030 8806317 35402076 859325761 860499839 767613668 632816351 14816306 968689187 269087284 225773232 67637903 948968826 483906811 8836634 804975863 68429858 92269500 10476205 631418479 453192250 152050842 600306874 36333789 46256103 848483809 77257176 994068878 194991058 61857406 76510562 625700785 24685480 754250370 499826422 163105497 704675994 805804451 117183223 657730431 754213339 301258170 60707084 65656190 207900452 929499974 473139871 298423445 116489523 243545576 49248096 19022057 128345671 623567589 100251071 150198144 37200038 657669032 732120437 454751943 927188247 78749757 515070460 238743309 546530665 3330518 77489938 905265926 89690858 620571978 560232762 147256393 913372400 626193809 667866170 843421137 849473364 548253258 833692063 224489088 853301490 302220853 539602740 111422359 511394347 637784505 601832847 645047104 662883171 961942879 759422597 55158533 249662339 54810196 80929712 469952086 280004215 234567403 189881584 437182726 947008433 415354137 571418343 2072526 491951269 172151032 992381307 644561097 107535179 214598981 297461336 551652854 922001568 941485026 171505516 897082298 581020453 666583124 983047529 13068123 163824990 958136902 446414406 233684358 33479252 838045700 470660030 482541770 210525716 242143488 721701328 941922331 376303662 930377809 371084606 909002576 146429495 551921455 516303374 102042533 47788103 266213241 829397516 711638585 576420220 150091311 98001733 458770065 926535285 644957688 658843277 283270419 538592215 379871645 617299450 891706764 244010188 34477708 696527719 50454443 860172671 430739286 20663539 844569476 308975009 221630001 716266879 239241230 70042856 693860215 332246835 459559333 51628938 503852069 636501497 672959112 607045830 748811357 9089537 711272284 526621019 44789732 654699068 169034152 27704335 571429541 485652193 320039511 752255530 860855084 307686378 263097401 66815480 668279083 971533719 180805249 65955659 103177721 753338603 974645064 698012662 63144206 995938858 276270601 37210707 191449737 610014050 941014564 193999806 726365610 910363359 884939100 44330776 727298904 385464756 773077592 629728069 192722076 875610681 567609125 597361070 702039332 463787656 41830834 500179136 285767105 995768062 596808787 283709547 778360554 165757120 265117759 223607460 809419574 378735668 795837458 459606499 203471333 30645124 410641483 127868837 756009304 491821343 746942415 384572139 164333973 876684855 587653733 585084601 588031684 814916 999003960 502909081 700906421 713952383 402418520 71744790 224803928 978001000 54552121 430653505 840052802 247379521 92515890 303142959 250346799 110171792 577517311 163358584 877560186 863442849 660949055 662450618 974077607 980283393 601374199 210430996 364663770 469532932 789124366 818762668 417302621 611661121 441892303 655463466 389834270 70479633 192446058 156335674 890168366 266077971 52796275 216960525 491659587 681564843 828034145 56276952 535572023 209152638 864938512 677183572 940796039 241567992 586773823 440815421 979952853 918198470 215471891 574265812 726395239 189520732 943517075 644859741 24817317 69207408 408313386 704897441 911764383 229908349 648869928 960400236 2202757 892117057 627189569 37272848 473473324 614752063 158496268 991907040 56530320 157598014 217292933 845656502 730789452 130068681 693515916 790502767 909970212 458677421 967036516 991744361 110748028 525207166 79710004 988299020 70421726 50173713 799677321 837742142 725267320 204537603 398050259 784954349 113202331 56414513 350234851 528119945 988964670 804042046 602580596 229527174 962867833 48155153 951983519 50075871 48263690 883363924 949720932 354648462 363610323 291685622 475821864 441450517 63312730 354685866 984923442 89534457 824689223 841810789 980637997 703838017 973317354 617131748 750718121 689028347 17284019 864863012 257678746 84078520 630844087 395873767 920885463 499325963 572277810 215358518 554525853 356111117 304702208 171534554 787079945 460792028 550884642 570333922 119661729 586502936 519116351 166614048 540682956 20907364 21305889 194613163 852539989 489847275 114550580 479989854 333299180 121088984 119193866 517758808 921925797 562870749 676389593 147348091 410830968 847088301 34340859 899338989 268515519 71384450 227020910 496417690 174073018 825745560 71273810 910813103 739502606 405551024 876298605 986437920 460303170 949129870 4521386 469606179 853713473 919221115 365584790 416007347 456426204 140199364 286790626 47219983 231173445 137913401 792053476 278645816 54306452 855486382 740524821 434565494 800693573 187856253 152928660 601868756 689907640 629564931 987272866 392492191 491920048 487906079 69788196 81589227 846600661 799125174 508021796 343477006 885634098 31203633 185023312 511094051 820266679 194826237 924853114 727317384 905473720 740637706 107564566 473093216 1150060 644046925 766766783 987394322 173462896 86825023 956988850 842306760 155678529 662836827 972169810 779045617 217958853 885959332 497724834 625030592 191697347 958798108 728540366 103607467 312824679 696762446 715873187 314403564 588035263 270225349 827531026 516427267 832958528 544493202 436989873 950871090 307058497 869183947 578178105 966068992 167306367 760251142 829230089 35263415 150462103 105617122 88492450 76100582 221579919 41571199 168844585 958001119 745893454 205522689 399795944 574070074 110437152 955043345 416639438 985653072 533542963 888638043 399570410 836136897 586163484 407169297 909959924 321596655 195644498 576682342 176888516 389560448 952012210 515822356 644314072 461415904 642869497 822299863 83172306 47364284 270118990 154616560 554996216 32172425 1212597 1043875 866038195 968504827 716801693 455821242 430329105 156046 893844563 961676543 582539075 497273345 200704140 649500869 119283487 952934357 574990048 422956128 101915038 887272146 13227081 345400744 739720287 12103299 64493480 919100795 18802723 845947573 667602496 740697656 517464911 262492668 60504121 196411972 787211374 37340718 959619358 459532937 289287340 443986150 295234656 11451122 707474012 995132931 249181649 55533808 415947634 380792358 742613545 527597560 355289097 330625847 741964677 704059395 916335839 41679072 310203363 112897549 568507860 14332177 107526055 778496662 528033903 748182650 489664537 105921060 433823321 67894036 203478500 615887806 62681056 13682329 48477080 23348595 642299509 66964743 767178794 872393937 392662830 972769569 532724079 473147759 402285893 349057774 623740580 436340579 438029463 367707704 32850153 804971468 794913829 705530638 41465282 857292106 521795735 830415939 465186709 654363265 613269172 810561004 497240110 37839002 356597228 647801830 927382845 445802946 791728846 281643086 179747543 957803433 252932498 264741382 316614641 379264515 244969616 961538871 902183145 70993674 179331783 270866378 53528573 564716539 297402967 609639406 15366609 29475221 970468103 460929685 552901613 82258077 522380480 552690678 131750716 522612316 166526480 42850829 21490319 337811743 23620776 450224406 670052632 558855350 736983518 624437782 2367215 902329078 422324524 576247122 136549777 378819128 477820591 642461398 877671516 719606743 286150569 879605488 554547476 810681013 735434495 128446642 855658593 388139447 968519612 44712051 82195023 109386308 98490252 137419342 30901452 147940043 669012290 994164897 663113261 533271866 974544722 661377680 813594538 14351751 936414808 285829760 644210653 962340907 60575631 763169948 473791816 986519714 360506203 58008916 278761676 253300716 288478144 858347481 939288626 886334223 74743528 647650466 786870437 595419539 221720993 701788138 340056374 935119876 669536732 724357167 194544983 128277108 632101167 595807412 658411361 519262967 178806612 646013952 984390414 592261157 338982056 450556509 347256831 545511323 656772269 445411418 565875768 20387449 638367880 991838538 906575519 354118118 795963780 38225859 73478016 19857800 68596621 674481695 575315212 399884 356165558 62388478 910658005 201494948 986930868 111020482 908045140 389105796 299015008 601963282 253200995 797460324 40021305 58974552 466677700 187201026 774494944 584261955 109319832 16881565 109436058 480722501 323383016 253236090 181462737 430078230 306540576 180057955 782025875 678329903 973699982 550326819 670532113 40344144 699649768 116747 631777057 501037819 323028675 280294256 762249661 709404918 231190813 422349611 575144066 479730381 263679956 165288215 849878322 627638606 286927660 832028823 784193331 887332875 366236749 434803981 112377358 720989147 535017411 188743780 820579312 799340890 161505277 959592839 943673388 858585956 133957582 381831912 843786679 375378334 348331247 312322298 496931242 987211501 14439034 995809463 671364548 993533949 780583793 196716059 482435813 191830459 865903925 518351527 987004820 16021467 601000463 213017567 859248251 50856787 49689515 769595851 253554918 586602718 523236759 139777402 43448135 475424634 323037129 593799035 215834036 27997419 818293015 67960418 41978471 917401142 309719484 288509258 666293309 344207910 375305689 535216717 882178873 503657418 2889714 665095437 652864766 502765301 56748909 512767278 8310616 317626557 899516183 35436249 760617651 126156285 685254558 760539963 300827810 312447443 765649432 419998468 25033306 68446754 30334075 740346089 473262901 518846481 213078562 903071266 360686383 33622154 90165839 897700589 574813548 105535676 686315171 250942729 253589168 151981722 446796711 648248892 51199462 734840153 301602119 636105421 263647386 40765942 884547922 659685386 731253118 254321582 423700987 181297860 11676904 716972676 818794587 838507982 182219602 347274686 431355629 610197634 92252634 731857512 430498832 464158011 770416832 224350672 72755848 938979292 797946859 526004232 800218622 470578248 500473699 52959336 304775547 831909096 442374616 416472585 821218801 359487784 591953690 722536011 943436467 735419386 157977247 730676048 554869240 482005585 244720128 421558398 60597083 938703271 735457148 867009281 291173982 25175672 68436596 476293190 929449186 634112709 610335725 502860929 682845616 367692946 774124817 485460265 273690356 198913128 292289967 802397047 732223677 918977492 824530102 528081642 213086078 255747046 351710397 255963078 72898192 327154610 126006911 223682960 881384110 733064915 480459607 182998419 177558647 908325859 531433416 14474079 560454384 999363332 699459064 571176261 197428735 190774362 531998768 930386652 109723889 71263375 419447645 210740095 317697269 712813902 759986578 92381900 952603551 673744840 722605188 49934630 817785189 493547314 901885965 846361140 915988517 448355653 201757866 107887456 58198430 682969788 906371581 381375065 806750706 13511641 463391051 682720146 57446443 327694561 44701694 527538369 251173554 951251100 893080101 338138977 888370649 800125654 266247407 373911344 50153555 162829537 937146676 332771505 476353975 563823120 963857900 697738154 871216897 2794045 237060789 459273639 438591760 676614212 182037073 877590646 898753833 191996037 910933286 252375210 144326002 629667686 119628733 101053464 599547768 25505743 171757892 196827229 70538410 629313965 821767692 720384342 4562651 654497903 125030923 787799974 493606596 657541516 314019675 870494003 916923008 925227771 387058873 517801385 213444111 606136761 105361414 45537014 603537363 734789703 366450890 305685964 245222166 410823977 27254956 11990050 519303810 91318633 472164347 409601971 27513510 185732881 146988073 16533630 72671864 322035636 100324939 561491781 703850446 357374694 565097370 846614030 686138852 986358976 989460980 101067940 961930201 725269597 812647004 38357783 225291570 9978463 912388982 257469496 389144150 596053867 353848332 863326238 985691920 261544616 252968331 62504100 680623375 65300036 794039942 610106345 532082281 23263216 66433843 410947790 404505620 856591199 645413353 645003643 348652652 641293515 771215784 637201370 505111985 750955887 829632657 472309275 604930181 217437198 873112682 59594030 141988466 499585899 517367579 16087372 289525858 185958606 657013043 630945391 45566245 32111238 483462244 459478741 565827566 78982753 542391811 556316034 503654102 664121398 20242825 821357242 611303768 881926236 70032149 869958795 422131412 936927792 292620775 574113089 972836109 872768146 183616230 200618479 680280746 46310505 177724187 147026157 479666616 51288347 142934580 274544724 43702310 829534997 693644546 986270852 672767048 273272905 879185915 680955551 298781525 973233835 839068089 320805644 570138601 15912115 834116985 80115701 681599620 30174 948542877 960091081 22439432 954620717 389555755 632345530 496110143 476616101 679200587 690844224 920768083 580985037 927481804 616230292 690828116 221765427 218769312 1276982 888549046 926903015 669559388 5079911 697904336 292858878 419746233 772883376 931963742 108920593 179953686 232621914 715109375 120318907 786217715 709546739 205348536 52306207 352118135 769657807 766035056 789167711 681741035 250552453 440465778 887969062 395385149 668202862 834463726 878396447 537291647 926117161 711934584 750177148 116950117 138240794 998508167 890039664 911792330 48979430 792825591 542282933 55749163 608220152 491271816 162155271 478867754 512478208 214993500 144539558 543184908 564357999 55919229 224452056 455886140 187241724 550766165 621982565 763459014 53357858 637889332 637298457 443394013 645393055 178604750 63962950 35425110 448102646 34965946 199899200 706739754 852271854 859563508 160508639 799113976 24409362 515421532 305529600 162729857 521898031 355531829 968050180 897717546 505005017 394804646 780970319 808998269 251275493 79468605 43495114 490241192 783896048 874915943 20647266 341789692 580659159 934804217 799724423 407164015 544348221 104599466 489513390 880361755 54182409 228223894 492379855 63418814 761899493 756169661 267385064 511059256 354128064 394102657 354069368 813888527 543401548 496038700 699307524 937876206 730035585 538514024 728408726 718607649 482680089 708856518 87505977 100370203 616549905 868664887 57070974 46168305 647125550 189363606 267779834 897900765 136729206 679322396 382406086 333725115 711964083 645141737 301388286 586383759 162246387 634830722 39392066 226593789 94495755 388597838 904288568 576173263 300143631 755669016 937291271 981034611 235718107 913456529 286341342 123881595 100877966 552755146 841273963 155908635 439728138 586580158 727999845 761519278 266268533 235229126 285627651 337112625 155280315 150916131 124515202 61925830 636152841 844953464 928925858 681554995 183701075 712218700 710141993 68204641 322690511 95489165 246011999 272881629 665872760 652028936 602474641 280248154 65761421 22723314 251942799 402935597 142435087 56945762 379071022 10103248 924752966 676459732 120263110 411126368 56863549 852634792 64174260 246046 855216449 254755489 612014809 39926257 225998438 495877735 41659929 140003 548137986 606835461 988749534 273977504 785344816 698384747 484339859 974150394 711496526 924814061 220574249 990621544 512248959 45298627 414327445 572040578 57378858 25351559 341418319 356620678 549940089 571359674 689857749 792278 435693531 779023423 141082918 699880056 173059459 379147741 139394632 863745429 189962215 580587202 667860674 53587450 143255105 215836923 991000098 999738010 70299665 73483005 68003193 511840778 695641497 386044447 416375770 60057348 146098784 62453022 867311839 511238885 599459760 886232728 328974116 347350575 604403992 574267281 105441481 670086919 513606890 464845296 1912820 171383223 72465086 991896323 543683917 70249261 973095405 51872759 497147520 761822587 416110615 188683873 430759103 243740245 375971742 376603320 504775486 328734102 357334568 957519577 5533109 675704252 486230817 692057730 772241121 565659751 977505846 481499095 557448963 348719326 125636060 318834144 17152095 341175946 482930119 131576584 265994174 393195384 676437363 222256031 61845229 128197339 781112991 232388697 777193276 926612360 847129548 925057230 262198784 64538745 99264194 196197880 895460625 113951051 27752204 494234808 125808972 791989440 634466423 804810833 12707602 744513341 571513239 43898091 888810184 32936781 97946178 48587281 21420885 702221852 413096467 648412468 207334567 577448444 439344873 777067558 817544239 616378596 718797669 255117215 881914208 48375532 464567663 95759804 771007539 774218962 652086449 261342331 254202790 625754745 265185562 237632576 449932344 181768549 729266525 279675475 4791919 591013696 278702448 107418463 533513555 992852055 805837070 419716597 918871280 903627293 349215285 784692487 872679640 53331368 211091368 348574317 872852126 40388655 935230318 289270116 624101468 846667666 29445457 498780426 337281838 203389138 22708576 157830883 532110773 743028372 13811309 55175511 363696789 675318179 775562384 209578545 915159799 797332843 866991011 310110498 571180295 437803647 932245955 827733564 726579831 514683155 81078741 502881399 354572027 821482371 456382975 946484272 909881035 132085962 661633579 101352869 92054820 197951244 597099144 332610426 237990599 752657933 524335624 10003767 206044280 556390839 802100450 793299399 816134529 184929431 145580818 556517883 223390252 121545312 999329492 941839109 700177997 593209960 549038893 552345854 57164214 4349990 657494626 626757984 472757440 41826234 218731647 648201612 845930184 745808997 67627986 66063173 156784816 145651469 602111341 246911283 456626522 41594042 108811175 686314850 423132721 835470620 875131035 859073472 397578656 359663874 972085927 625835683 577356184 492316900 224490735 868195136 952737295 517313882 483728856 573719605 841578363 376677283 128966029 34130432 168367451 372701215 50551422 51651973 341015727 467534037 198744540 331860108 429737595 253984750 56654366 326955073 459572807 670606904 457213310 380991922 5423266 19985317 735051389 989047892 679080346 952361929 401389659 211027583 697672518 973165663 490812832 420270061 860787773 400540612 209802902 690830400 460582428 288606586 698947532 593468793 306187268 579656358 876765333 367568513 50169625 74732691 396124551 690339235 38440708 296490797 51643132 969891600 642808946 359804807 709813140 456560474 789232531 29200982 763127473 25779706 411562140 226453107 697651962 336361419 985491525 987914077 815661273 660556172 365678155 93038516 702814461 532492897 104756207 953834431 440328920 993642066 558409334 774312935 340796194 67313867 956962215 856063802 281184852 715245338 147540560 394464746 781005614 137796341 155069633 610675659 456044850 146726129 750721871 963644120 586198822 28636428 60133587 328990126 690396566 374998820 137485097 996008463 141455696 99041661 326001073 451287905 451899878 165380928 953121745 12735276 714807343 506838262 180606832 807830944 158170311 390896913 115601277 455034892 296474250 605225571 707957350 752740200 237308189 945127077 761067682 39352013 175358821 519629042 687336231 371975671 188427789 876445769 566589940 449480650 778578437 134094350 22345865 617672906 863215358 669939849 474695274 60507553 731797999 299693414 580309408 221090205 305396627 233835572 532312375 409275696 214529768 820787430 621377985 121879662 327098290 107740757 25107922 992561042 20859126 589691067 637768834 380772217 200995711 522813498 833015790 737339429 619842652 941710163 635618231 314209084 15416160 462520687 48020353 651250311 142131617 421031258 195248502 775670387 808806394 17970627 846075073 662064275 956759433 283242941 752955411 69048348 408741425 153311041 810016801 825368167 141605145 334999977 366570019 156201331 8810283 356389431 653607510 385127009 355148182 141642892 292016764 12712438 7788621 182794545 61100119 55536924 306899077 235407378 822682674 393221985 143844155 832676606 42276184 7452023 260281260 101982248 349880986 39538610 702385627 916178089 550884557 2950285 19582222 462264060 865569098 35873573 503177809 882573696 282195565 603051453 137638642 185468154 580754454 721951800 255182595 7287056 364952107 80729762 976529372 718072015 501823252 753606568 543903382 451895589 569316925 997734171 694166161 849573736 269876888 458013808 891455471 619987406 441012504 674986307 747404822 67726322 442552119 894254032 964709938 996235606 509333873 990462329 657246640 840390619 480644551 766325059 709400772 354345547 273903165 997369432 290822373 159806159 29896028 852314758 484461388 112584057 486293169 279478463 69339512 414116540 833810764 917315479 122357165 172853742 63105602 159103945 733283696 931705805 89315627 921600691 137294860 128967928 515111076 609952981 993308433 263018609 580900046 80826454 785293008 474270241 712712654 391691134 147756256 609503572 446014027 221626173 51395227 588520249 241606131 405012899 733515682 441888100 751921142 547106918 225933397 19713612 610399625 604949344 69964380 2961868 260998245 992378638 522769697 396832678 16306502 134745873 762080339 368040443 933944940 210981041 434694757 932892117 995707421 681653589 834647309 358010781 547501344 4515084 941374917 43049893 894351683 168454408 645136462 968602272 345075671 87713309 348590376 847390757 591792175 403990342 165592090 135653680 875851301 370423841 864957104 157713568 340492437 774852462 116640440 385806266 55381472 18106772 146164933 759285924 973872234 527201052 28117164 380512491 447278363 807035700 19117578 102467582 819221986 48258093 151981756 419212721 470996526 816216061 173687140 27112634 126908275 632065725 186555883 425958711 241398699 4107052 444567034 453996327 130837459 56011563 820695935 83520748 997600874 47761471 945280815 593057232 35275765 198808595 15514878 41564285 868763517 550904051 54969512 151311747 1571087 764831826 212493356 976949717 376842299 251747652 995179084 540637516 945838230 754417925 614873870 506843427 423342648 9747824 152873021 717240954 714782783 40783752 879841257 839050451 276172618 13779443 99375843 536989848 31033854 504002426 547302210 316318099 924942725 916014475 61164257 889553268 37283850 796663479 174352862 66766926 920335166 745196852 348941597 611709210 20592342 773143900 395676867 548194355 803079947 409425964 344261307 916058585 735464217 549809606 984074549 272083630 17328064 609136623 781510945 156914748 275276742 639450258 984504504 569362285 265623667 897759291 660597236 406828817 911681555 11677341 996034835 724345436 274826360 889372428 602540824 74635109 7682933 153420548 84724810 182977960 225054564 393202848 836329139 482107524 446679457 571940644 212666530 834228670 810280205 621441908 259052330 629390332 766669452 338870938 3841697 702106955 151112071 28483651 865436449 550658458 999554667 740844867 951610122 522253629 371845416 887745037 365692286 374384491 26636722 44926780 774599396 654855360 218081412 835674637 909688166 457609660 639015192 780399330 329422707 145206594 560002160 522478528 631253565 446538521 745665936 946514130 892564540 79140462 231215618 524936420 224868265 484289616 286126160 925733865 999389444 496074291 458485390 406766966 932285838 271522926 660027598 765323076 873544144 523018429 700411817 677298 381968402 274387136 492560061 237680704 413646565 656560249 929514281 247273493 239320986 784884946 63349267 48582266 401167561 749389333 692596514 845589853 972318923 981566066 367346437 897479631 487218239 144633981 318726634 723683462 911905929 137245101 27480583 390448220 400497230 31161054 53278741 689065166 681265145 974563536 797835216 690814591 81561658 61785254 897531512 267675570 108700802 136551527 181497171 63099603 890708872 3634560 111287849 59774702 509425607 131960640 154827719 523842614 373472765 577257307 273436797 431336064 524798893 879600232 859085983 459319237 984927646 738475107 121257223 238383268 551433819 916153644 734896529 128488669 559987889 591264518 53365150 518678999 728050227 751805721 951159954 723686684 37842873 743351792 821369943 699737815 69647325 856899067 170713047 209667165 5965693 219061774 106596229 806806177 527934524 722332128 53210581 973967550 498191617 888588941 506904000 523194993 346827894 67670293 20654401 297765532 391439754 85911771 375697370 398423493 975397359 49027622 612889872 153466005 56176797 406838435 325199594 908519001 54654029 172014050 400389238 896488324 343073279 179437525 139138116 442935339 67882869 573490004 413719274 325959303 569790902 40759963 54630270 807401847 958819212 8320970 56357407 261205756 802737157 923560804 527548524 915546811 265624822 278484688 91446283 233476222 917365107 969213659 956889892 144623283 771581016 998731317 292257507 841634027 732575428 30821872 155010042 616903261 975388313 804268548 986396956 664809569 144889085 512358349 72058243 891727093 594277596 706552971 337592171 691900731 336329059 723932641 487633557 394545145 698018950 6073430 848574149 160614424 687465851 721356760 218666564 624766757 622131005 352716340 905348191 986704851 59139339 661510559 475046885 995260535 249471718 175266096 280173997 382051722 852922390 862608739 698664718 40170539 144476582 520413848 265672806 652509339 219068131 864861074 845230995 917798079 613655009 187028473 587938429 742210209 190682614 638419672 444773770 807552751 765955645 81653023 614484520 662705019 670544916 717682722 883261767 707670457 794684830 131419161 562093532 553491780 565345346 187655838 168231776 200873562 37675306 492092722 557444174 816188507 67177925 39841720 579023016 809736270 38110278 608471800 771218547 101320539 788040739 85023517 211179063 762180946 752241302 422432311 478598528 811267875 525233951 161244858 626846047 494458212 683692032 507002366 341053162 644339407 911561408 267949757 546527159 637803200 943823529 53313432 392929381 245498811 33769290 700417426 278320916 5321188 312525557 225736339 175755752 119147910 82551106 36254694 778253705 20996493 666930570 1479867 19964326 763364875 44662637 638474406 563423598 558996151 673594188 599534111 810321429 656757097 836766928 199700736 141107541 77973663 217438562 246297866 562747882 687437308 808774832 466374752 69290517 50176195 536121646 752136714 263295002 66200160 509013651 930508915 722063554 800682720 59144280 129526763 76386778 386953076 39789116 37568807 13927602 567900402 984604867 243354556 478894239 55888980 896721842 689584295 17707897 6511927 823502997 502802632 246922782 130691676 397821753 715481954 319984877 879295531 50072114 142973085 884919371 528581419 744017238 521614341 229270818 486068363 88599616 506609416 317525341 86712989 932102351 4772731 688563821 724510549 226308516 883301910 540007367 991381199 36491431 833745139 410110308 2981318 968919426 791307795 236073535 322324509 564617252 141201881 230377179 816978778 953630528 111625613 281148346 924414246 1234636 321741274 23359463 220160463 304384643 296008017 655025006 804277958 606335075 575701732 982007262 695475489 766402351 206330987 576267469 780927002 959319278 265149731 384082516 626185102 471317866 543537194 783965071 324863615 388464818 121466628 316004127 872027538 514195864 760812569 450515880 913544594 178545716 232234292 290958931 608947691 792573024 271599110 537254221 796943151 483910713 175440545 604463685 684167573 140696228 731021821 707299570 500430709 462918087 227459191 320923019 529461198 758793612 801712717 533733197 811498688 559428130 423382563 629224185 442581522 831054459 582754177 707316052 766513069 489492174 691456338 681876901 647986207 28412695 670306407 23308858 6276377 449594770 987153906 950509795 357202929 716920132 144296460 515743093 688778273 176724082 353639983 138850376 50452934 575169320 997525436 812884666 844790306 156745139 277332598 685672362 537311258 245281576 753910533 902566398 217071289 684601307 527075701 309066525 943264683 245493736 118522804 487913845 763380163 924843437 362020888 730449655 991597430 30851150 964800470 121124758 274390365 119609904 813578636 293003212 63658167 274863998 25844664 264555285 24153572 944188584 524295998 537772657 554356459 856163550 840145382 350593766 609370613 51091098 177389788 969655292 490372048 992805907 753966 63808575 9756781 720549323 483304530 265150913 106581858 450252034 879357597 179891349 869927529 847335488 166499789 701469013 906720223 749183951 539488640 216219037 633440070 927352894 394590138 774770830 428678596 4906720 944275299 49964876 603388065 265714251 617583303 702952833 969006029 208971993 869519892 52008919 2766936 258332458 849765856 412302977 52979447 584707232 259162528 811504051 330068614 231289826 729839154 745710117 232911488 205031770 359519316 384819093 124614025 796203447 729161514 375447362 632224741 643182699 632131260 167359089 469631486 763237934 138535542 232377580 300915426 664239993 35617191 659127166 831462082 496503564 423213058 419064440 497340788 654332009 12362783 524958767 267474162 974716502 62755835 343879547 527391706 607455583 65144180 24054842 781428716 703851090 758425807 2724299 26116238 259714241 6529842 775183252 15561547 146607491 789041961 818333565 165961807 297134387 125373221 185982578 679428333 782940848 850021880 69415653 569394714 342550940 510054747 513491273 684208367 948938973 261394537 24792216 517142315 163423518 477392417 777062094 55881135 266421071 249522151 561640299 156041984 879980321 780818435 40116725 364202440 850688395 860014625 36886644 633279317 804259656 523326416 765478389 488200728 2180438 18291459 757933320 9368104 943253881 512869523 359806529 45579197 709782710 106270907 559215802 539839413 837885400 175405978 971380368 231757330 710897134 580317108 715215714 956963450 845056203 910231665 34533589 396625589 478327685 252863645 924434 161569587 124107511 855705831 772306758 662590852 502133311 648106594 121179681 947022558 66025280 392001799 183398488 279876250 276087585 767271473 475932451 396271799 837874892 127697695 250178240 908505173 579629936 444240757 442099950 753278524 106842880 34506172 925145971 309728083 390649009 479595485 581480086 967417641 27024256 285889962 191756197 70457455 241077418 627533653 627506033 48875900 931078706 55468023 640713933 73632968 203613534 803620875 693193490 424050033 54632762 839798768 14605982 74943417 25763092 145450603 331637073 553690502 227608318 182520098 636877071 910872289 338081360 368009506 817633856 435717751 377759779 661366106 619744339 42837531 640632791 529141021 987118134 665784130 221805965 727044772 777537760 207589766 511200430 385172874 592297416 423930148 768770659 132640078 834123115 551778173 813036570 524827604 436218314 830048152 85478919 67817445 557598953 323082399 607908256 356272042 359258961 783218782 946660385 71705397 967948943 447524295 511692038 388609785 447141810 316912497 232031380 314781261 176509393 368312852 680866384 218668524 91495555 733588238 871725957 659170936 36203622 327762657 946979267 812787442 271445913 443636659 168980826 793018180 538460225 427528141 950591459 345924279 466661128 468360221 672185016 364427901 684738457 763103924 275744120 778410025 939073829 279375176 645179524 189872178 30962913 484157362 731516804 474027124 719570053 80071281 644044770 240486062 264016079 76152102 43847501 776534788 963452926 940046614 429916728 850309759 967431256 421008300 579705433 775230857 789648037 634247412 177261866 702813810 829175985 783693344 891230827 660513773 636298189 219689991 607689374 186624915 997246799 20267425 145137034 784215135 247288589 948407948 977066169 455694640 918809062 6990731 404268538 720096075 954099770 106755842 283234784 342443222 621886061 37176187 319420992 471860062 441172840 813127203 621575351 786997842 849761047 914038605 632190241 607391110 396569836 341360366 876629027 676266929 47469659 52547360 14341539 245344494 203466076 992001696 77758283 199600447 569911020 572210000 570658569 410774278 295744908 563096757 754413970 982864266 963536832 620281466 457021658 947916664 144686737 522987 480471709 853870943 731749388 21998458 456998618 654723122 540690881 310871358 598404690 419396554 837979973 46174063 894857486 637898082 506288305 548430316 984812758 51378202 544894240 55628725 696128443 152563060 651474228 96612721 184529550 726741978 769692050 830301161 743001958 31068950 86851937 949939851 913700894 603633368 997382351 438577128 787177684 301238067 852707213 331693622 530182764 860852000 488402766 3277263 658106635 58053370 537119307 492191664 831488668 832057089 560603586 982985723 396934478 786474456 999969907 252927093 672933396 213747462 428387617 937677577 390870820 85839736 991185175 509352003 396641913 273208829 558173857 105440725 433685585 656424393 579711886 70344982 892045743 761329907 655053749 462841214 933557978 65034999 214144877 87252780 509059548 47102772 870836755 490550624 899831044 469116783 856801415 966968577 560733541 620439119 864481199 676162328 224864597 161188319 896865011 358621011 89011950 636441103 10107072 427269763 891753104 145235762 579492614 803972383 293709149 491926657 383750586 353188286 666309564 49889431 66212692 208045984 371944407 812511732 118664017 251513126 747365405 41469307 274392754 563135062 873441728 438906099 318393980 316263256 532234039 621670281 527408182 566946556 613673662 856577612 191052398 198279473 972305618 950836912 99076916 51708303 29062837 960822540 330972829 213302735 412186864 424455964 864057666 118538317 237674955 412425856 705366718 402175629 92582871 881300283 915764275 50195379 25973349 845706804 788758214 665342729 63473676 294953912 69444127 666641021 982827816 633753078 770636522 896957728 23155797 424537986 70027096 164441512 855142136 391630291 616181663 45281519 189996982 506072005 62720117 693194866 460702970 962939928 200404377 541986003 699256180 608396271 685889099 973641816 970065557 332864849 516060623 920232297 32157972 693143979 246489582 726936854 745660780 204923981 586664308 243614095 76388955 749405416 591952563 808722601 844709732 766206487 822082047 388043360 555532622 927736787 727967792 122208079 858560163 821970428 4927267 807312186 572946995 600525527 174045753 47374213 120633742 77036939 425093334 814585274 188617613 643876003 171497699 280146439 61824202 343901327 161409869 790543805 479883299 350589475 596317316 40440275 754800955 308262166 68167933 170041697 453891833 785562244 93582768 353817637 711890951 31739245 688329370 797569281 403555156 624925492 506400061 964368507 576898706 717730337 903892251 618942267 967783609 585480159 567919679 469244049 406729858 213998078 553870772 258154733 44433133 337414770 330247179 747468900 805662140 999555602 937111513 3937074 440801782 786289434 225300023 651892275 912034405 24002986 578182976 649026920 344322583 985753669 124812439 438491768 680066785 210310738 729798623 66956589 972535767 419366559 548675904 826509299 13836757 589025241 138771945 124934748 265367546 208707861 651497096 985631646 680586791 63896138 548505044 744310035 535200645 26063060 504418052 817253561 739667708 767307251 391332948 34940336 11308989 376374602 155415943 15236286 381842361 268092769 290815584 502910670 490190375 583865379 837315880 347498349 284782082 632197472 48885548 258709836 27353737 51532 807225660 421577409 599788477 335558398 558729772 3919429 219073766 285366003 849188183 113802999 12257039 766986632 381544215 17837336 631498117 174687619 113714510 703370893 170882652 993860235 511735264 586683232 344951018 980419499 546694455 711974463 452992073 43649492 585227453 64291580 604429786 284014168 581314918 332453131 246626237 259446127 13603364 711087623 585002842 660277429 640974448 489747501 158094299 991652266 265661640 197133024 747273391 147897393 52263211 827326243 72666633 879767826 706753438 588847650 824101214 973584504 400361131 915362730 67620331 134112371 880602589 262055084 28746541 22502263 294730822 384743870 914989927 669932252 643216121 404798873 41231392 783862108 871671696 135246748 994580130 872929688 297482918 856711752 511712891 600095891 560275038 322031042 354691584 28599349 727117019 243090004 604360901 464770505 584978118 490073837 67191335 603655295 309670347 404230044 574309315 861760491 805130012 781953049 140754939 864436869 419676653 87150140 754214008 825973799 922676726 998573187 728813731 379364498 193918452 448439440 614847530 224745961 616432168 733075881 116145537 153636660 960632534 893627191 46788191 966016734 750353095 578983752 221953085 615558456 5268424 284966157 199527130 689986292 285994793 116889436 291585722 677300138 73108030 297125678 58386850 419578966 712142562 196210210 251937566 16422360 208634863 182458617 136013563 399648627 810111431 921745944 845652941 283987279 184805071 126661642 828037482 231282424 9242606 714503163 544237421 943632860 268379922 308976702 325954484 79682512 668690859 740409031 50841315 479716748 575553327 36789681 120106207 808305962 695142292 750008250 992178003 826357931 58608089 731926210 838885422 892106866 119929469 286148176 347532835 59256775 934990342 360217613 235457832 846414165 159069052 965766215 583099640 751158701 231744235 344218735 838258577 140239297 126667748 171611547 491251638 106026857 657201149 697642757 421422958 551412194 789960013 850290826 619583107 93345866 71279345 85628203 729057540 932339749 208906633 908760464 184151491 434712539 914820539 254173824 93220056 565305655 312654511 865150827 424547868 811914218 343893650 795372768 10411951 370417670 591356692 761418519 443561075 1134212 363836393 355523688 981176975 892526014 377894220 297682898 562346477 7157237 816075383 64336245 496593595 287650252 55823404 40238872 307246062 123701963 512298799 79103652 688607674 899996126 119806665 481856679 691411995 289179603 590116679 456588498 948372816 805931487 236207225 28864123 54306907 851928090 351840308 549383964 207677314 390872062 450905297 503635154 637967057 851999468 620437419 583028959 294440597 335872168 249860005 836672040 131731938 229074392 652282785 642435000 698373391 678219400 840864010 421970747 395991093 30573225 418781771 806353796 852404659 945541773 992617813 324869895 80491693 29570412 740772381 207611488 267214728 290078691 390324508 195194570 127187567 670094448 201374158 388670633 812662226 844177399 843571507 548879873 683120865 316628032 649001041 67192060 409735189 338240119 51925168 754692712 161082280 51826090 889083101 638818358 680916504 824864079 34037991 242277372 742361769 515884987 39562981 942866804 641807328 223145132 114370414 783680763 994990600 966940608 886261279 617596435 56820144 42948859 278720025 185434593 302586411 489146693 353471104 234479024 646994958 855275754 939619581 12302188 72693686 274232856 375647293 358761000 855430080 16401253 144415344 58200729 649534351 534550086 515189706 609828760 276651466 359925145 78116102 996239012 374569691 637308956 244558302 869221469 864428913 699391219 755147668 218316043 15574782 312559654 153761645 341127445 623661626 520074529 153656624 190355338 753687966 861073715 11279275 907749531 186870762 482158095 792101166 291706910 22124704 993680462 676648462 821157901 801150598 333450730 199780132 96606981 230940200 186599620 677448267 206171848 167308372 117563680 714780390 582420156 310808732 963327012 974697560 120790634 90131415 307886684 28280457 42390015 142491296 438708793 96962151 543079118 170502102 868313742 613624931 293750220 691041050 116921617 643433200 505242130 86759253 313575648 934435592 33188191 918553903 657100025 828198055 375313555 802842009 138412736 210009422 675919413 66250820 933603454 56765569 917751023 407527975 656976860 65684041 416347661 9581053 317836396 839242674 206383105 690958532 63098400 3596110 730881249 728915008 959937489 71957937 201000167 836655478 7008186 52850163 69785840 107458865 406759418 950408753 439239935 776755328 66128661 903822348 433775287 844267318 326140020 251015976 318178276 252505705 395078880 452562350 65798898 219576052 198591243 539071179 302407540 22343669 786433031 672253231 732730527 892847439 672566221 8040335 984336333 922261033 436183992 157547812 7221498 299590509 477832455 761056297 71173450 778915402 520334174 701257824 327869313 449177266 854382406 19259278 740129418 986089949 34166440 986173946 912459761 542888133 317929814 255576307 698978408 196710056 926580611 14172999 39688773 329310089 162955333 34287052 172976642 899335854 381553178 92972507 183105725 238738723 302042976 513872848 259867318 962465846 952637660 191561611 293162964 443346937 473499700 212480242 843417631 211324356 328297077 705664621 562449991 991750832 375954062 510835560 727165468 561935901 56011218 739659477 781288212 869112876 876074106 417773991 990177992 786719814 13002273 314262872 398227319 279256979 921612870 999510628 826060418 943630212 56567502 500866764 801537774 778546250 896937599 145005716 898681829 362910556 863153542 334583877 84903734 41510389 609653233 216526700 254860240 2622868 136631350 169547545 697985098 584985722 498647979 667431521 753731935 66398256 889788684 739604700 990196842 238808062 694491384 324218151 758604270 875486580 62342771 71066467 714180625 869657829 79930726 741660597 639542556 117634023 392727835 59528388 86006268 999367637 719162049 968501822 760485060 866550862 888493038 161592147 993086249 233963955 475711768 902786360 539510021 904793004 181733403 750329254 686094037 471712675 662965942 352323928 730590267 374225735 958524686 28261009 503071356 668451595 809633833 242931603 336507650 836487333 429091956 604014889 634858971 193283471 941436990 604664094 38222393 38419849 125953594 36628164 259433201 36326677 641572865 706477934 886463740 636405754 669384846 264687862 897271288 795568066 258760384 263916600 878386343 666733116 827914204 961827220 103105903 663584763 41314312 647385456 797037785 122415828 873623249 7287476 190097939 930393188 976580006 720865613 419076462 13460615 569065051 431185067 847980256 749076450 293651367 198032962 722882691 353818203 375113126 811462668 350775572 491051420 524031063 849582853 801440372 295490451 511490591 776639918 59907627 806794484 340835908 195476108 144157152 410252214 17201011 66506406 968439266 612366738 61547579 228816906 918422435 676340360 105992080 813614152 277728824 444910425 340062025 33930997 587816666 612790286 5659297 161388585 457959271 449436271 890600122 215636737 636087522 487284877 313345814 62043167 87212527 512963385 958433308 885901349 258969944 376650890 982428057 968366654 354678922 398855771 896474428 724304533 793522712 301097162 382979353 894153947 899633208 954671291 78192167 333633221 483329857 358452819 804553410 917022348 19578419 25141629 253173033 226341228 55484719 858372712 684545 17944613 878160379 807635975 312584912 959049597 338340479 308960912 986441859 215192252 565533002 912821246 718349801 45264430 985977870 919914639 361966134 993672101 232760352 351088966 416156545 679844596 948373753 146598506 257442118 849131637 225891000 961957381 190924516 61817732 48417949 488057446 951307808 12430082 146487183 31953056 653459873 266069459 115889303 31353097 4394354 141063520 59637603 92722107 227275651 861356054 826792132 806765334 615455271 896148964 627966256 465006140 651408024 118415553 911369025 69776276 681597295 412756772 25038388 614302536 672400172 512652939 435626091 66369990 784969396 97858037 511525355 285168195 473245645 268640359 935866079 683627315 400841124 395755370 53577747 708839123 733917512 10384267 183889786 920091039 105353261 922484954 678157993 442796252 618286762 379370860 911201625 462487824 636309115 599890906 754729449 873548932 55549248 758869952 205960665 820097481 879535868 11088958 834527312 982164016 948435094 817910906 384506007 89987152 150934107 92188187 932313244 699729540 864733818 14557647 535693169 607671659 477937543 856660423 586675146 41625703 687954681 508593718 950001282 491220510 291398572 791865302 68203798 20275451 456368224 517280867 32513064 218012590 2179128 583255837 513632765 968616 571150140 154335050 879800576 611523488 693036247 27653298 838720061 688288785 856648281 859164706 676417511 827916217 695114614 19543017 20068307 334158875 694719173 88756318 492977658 637861374 353639490 906832984 450653947 872112108 232839116 41748916 51683991 560677045 383282088 477477331 557545011 830239209 517949181 276512281 7919449 924857953 854815830 167489135 305143351 760393911 409762851 66414018 10743326 928604617 255678264 121338498 255582724 151172922 9873228 313094436 616035075 921283057 992918395 326190752 629028569 783379608 427183813 122860788 936630374 390507038 937467533 746144671 364370992 421680181 354663195 498671142 186854114 243597781 762906 382794387 474557384 465231287 834808602 547917809 332885845 794338523 268985871 630430929 959703454 712946947 393884112 764313032 784317661 823536438 768492697 41866223 941003758 571675197 471093386 14381410 676138197 934453545 821442086 904827329 942846774 263981515 184075989 671927474 76581595 465688379 179902306 786391133 879307314 962518098 758145661 899593710 121267405 846737968 233831226 183349783 188351968 629032630 291753872 488164235 999955142 363526925 923925211 508965252 113626492 591450653 333113435 285639230 17237284 734899991 876086707 5916538 617403012 308913132 645825899 110477052 21351557 804638675 756789614 28087053 514818228 727567815 416763276 32988409 243779524 970404615 185862649 174671762 829369866 119643540 537757132 141094828 728189952 96916150 18506114 571964575 632023747 660204919 518676856 337981128 22389908 18731815 331784308 565047304 396710234 45099479 768922141 812952132 607333663 10943198 559027582 220802531 60951695 920163158 584505224 396601427 31426428 513118368 697615757 388377220 938645853 15589596 429412293 916340587 44860874 42609522 369572812 685871744 149402369 58647948 996263714 888219201 291109476 328430745 29514154 708287149 752617209 276761292 119293996 19806666 178810345 298110874 25011923 161796127 439390977 15683136 424618928 49430331 425906996 433353787 730997045 71657516 182796055 315826126 874768570 249155592 341435748 756366976 536415483 768970856 77245816 751795099 123888792 42667496 33440212 964525741 273269908 951271080 546441888 640137739 947110615 582156494 543143971 564119881 129861804 37664514 329964876 247586756 710915396 513716465 758127149 78792472 858574897 82169290 912676474 924937642 97504235 406484676 767462414 109577504 688855118 202625942 216310119 946548963 17548570 739396349 922539045 395756708 830354546 272681274 249967503 13158612 670817630 961746577 897198862 22544683 238165577 350764491 801873071 91187490 606674820 701039285 896011173 407876216 42157505 740812959 647386821 915588529 79443096 971065566 714507017 805484690 459956486 52473674 904173070 460506791 108868584 10945216 947257494 922750909 931118213 335505314 871962886 810772072 466940674 935885394 974595560 350006910 251366123 435209147 313784427 706268058 885740976 59832776 170563294 768384922 1829669 757794282 664041273 44912418 118070786 988617622 184600980 715444759 19507809 552361668 867947181 721796644 366459971 795449970 780818023 14248248 342700043 118458144 736793158 58424326 975052545 892543313 45907444 981372036 607728081 940740624 8509374 568174701 711328521 722869096 597191447 45018559 551981470 454079211 629223188 459348285 47661928 41845804 790470383 395184878 74348449 768024901 445210245 474273948 221948266 125450066 559457496 44486742 442999366 210916596 853227149 97321710 150518941 682868943 844722287 519585404 134985275 980312076 492233194 836690137 857313998 64905943 433092497 585524261 338923115 687324386 746370456 989706050 239443978 397826017 386728539 937417815 794201093 7052812 510492885 72292174 717620893 938983072 956463914 408562773 999220853 665173598 619306269 26717793 780363541 694832651 641613466 325672358 345209705 203632878 760380974 60804128 486879295 71231829 619899786 348278286 398237389 704655632 682000901 708715634 527789864 565390324 586134294 750321554 738486989 335114841 327696605 407190394 211459869 268653981 34266779 406972535 167907289 996896927 43799350 261462429 819919274 779484740 170234294 150094659 65971355 944914422 345265099 252881282 373966493 190346272 488617540 754835129 228783618 290118836 639617945 373412364 210021379 664163749 316977250 926510560 76961594 59865965 771352030 759645792 819461672 52533127 392445037 655972347 937587120 184703222 451104278 753358308 908758938 251086525 774867202 280103057 809440530 706349669 389859839 109460541 755433767 554955898 980911870 616087398 939853644 838225166 285641110 204042576 194318809 276720180 118241663 948002944 590173323 173168262 31586071 947190081 899510016 323127200 241010144 234898466 391061308 965387427 923666175 917288054 75990055 34528435 41714623 466224850 329543693 748473721 426510348 716550035 257772317 539851170 354045177 353622358 956564970 59311454 897381179 957674366 851844076 596393698 65766315 833704114 300426752 56451302 56671176 250467676 420183268 18637607 179377202 907490859 443083708 170213607 785850160 704988817 34927249 517682536 388768043 995776326 138254540 720897652 524449073 549496003 191614911 130320600 623327092 925783496 314598684 200470757 67581384 706939351 943162748 132114670 477277224 65599414 988303065 701609932 110476081 634526705 960656149 171538269 343914149 679343957 323938929 535911168 46425065 605183351 888321558 477988379 475938952 545346347 137114256 810381974 215922863 768015629 257096269 922314589 46052782 606641660 660133923 193199841 999614077 209036697 839535047 77118872 502420533 810012365 676106839 416266361 67564178 306368064 341925073 719899521 334036088 240357603 874639002 41162288 29723243 569510503 54618616 303416332 573735189 476058563 764321943 666636061 643971524 921262514 691172872 753638000 637630186 354573106 955109949 284526228 360095387 757856262 375170063 14144032 606340370 401477430 70677433 192348203 44320556 157166986 143197530 770035410 286012651 817450002 251693942 127794614 892029941 12951201 857794934 918758524 415908371 538374733 847644195 476354891 267132850 21404657 120237615 146532177 655256165 591132331 698287789 258594110 426205025 962949726 995102611 62684103 791199231 6416433 415479359 485026852 62726718 541440782 333084655 38856339 873131839 953037348 369923144 69424851 883902919 34759013 716197840 564534441 272868032 19512841 825411188 963055199 228348344 838886666 928763394 159994688 40564065 127179173 999155888 436172829 864428047 44530655 386156436 879120332 522174013 33040126 269901097 138647971 386749704 202979340 343113681 927545345 84114099 800263256 459611213 160495302 14045473 902300148 806418502 165634517 952140382 596291128 598934728 165850009 60028695 238360125 669335746 242525054 50849052 458042723 282635143 601275507 804526053 685990859 67009872 435528559 875136267 500188382 877472696 682124777 817080011 569877956 141895742 5529182 739698311 49093102 288028359 674557134 680695620 641151885 694287897 109963584 576684076 629669400 606643297 955805242 905017101 990236874 652685742 379411785 775195353 394648354 731923059 995199 986758692 107478369 724486665 462064624 241586601 37395728 797517099 959901236 617651910 386024823 234863736 526572777 828703227 778797606 159168245 53437998 892491119 739840368 482589832 248637480 27701610 870109419 749914238 298259328 148240604 32975858 578948102 19121635 397156309 358452259 772038835 566861442 540789259 66028514 803523326 4578960 771040088 516051156 199822530 353243078 662963257 5773412 590530494 281295586 24318543 679440449 914042903 275885603 47571682 76491998 810929875 969626575 428184409 531218417 393303135 64310957 6349763 989439732 685112074 220717708 932074322 234187175 438630791 472225466 206910170 781953164 64685423 793129102 855062870 565623658 864970173 927983582 216981092 320462795 640587089 523462537 389104836 904066942 709260653 4887535 7189725 213440277 708350011 50337652 659334968 437101672 512027460 219298561 11689731 945636624 671214074 432666754 637179023 443309293 304234544 574874985 188559314 864771233 26716829 799856426 495653605 131244051 815264605 991646653 154137735 610737388 353579119 969918495 669993625 68867869 385735224 292900561 390677664 28713303 814488574 878675543 917952071 875141010 470577262 634288058 233492954 450654599 774276119 640224519 454169292 870518582 404498413 121804750 152320049 534663520 302666695 681076644 231894853 842414094 757479649 462418081 812076515 694161672 234906714 800686563 929545486 253245023 247624119 655428617 59287916 10935524 158354782 305821624 937623494 522023598 170428188 348359706 204039050 664178072 694400160 291923290 787758409 863627712 238248958 44642601 301564729 548730890 411213357 556382013 65785268 570555547 861469065 869145548 917844407 925154654 253082705 806484501 767208292 220905602 62066474 71219415 337385600 111876858 453328794 793422552 988922614 738742012 49943182 85128544 66335058 61684355 668575445 446727867 432063303 307205581 914778019 442899643 302909481 53379549 112955151 8444723 536374644 945071866 760232085 56338557 809117507 47506222 913572757 167204341 319349978 51120328 133219793 203293308 307481373 820194523 728419827 45110518 805535510 202048957 10466821 31191244 205176946 876566920 396903927 553170539 865571845 696614044 859203101 248170947 359726658 879550491 852861358 230500553 571919812 911159404 623655238 405262837 286619080 563119033 37406052 747272900 259094704 433952880 228255981 30365239 367649409 13916614 549491624 596372306 657937254 272969775 490362048 910064543 911055403 510430184 116374853 596572585 882499267 842680173 107139754 781193089 138566851 26100739 317722952 805287228 711470564 24545328 84770523 981653362 761767044 142073917 277499136 652905921 722744870 448706747 651267005 141713736 452883950 107892987 19360760 150774573 279846694 701966228 317264383 760894232 568799164 123056865 600799231 25302453 887493313 93282177 304865420 752335669 916609771 397614805 26218272 778556877 957123860 230360454 387107988 19390518 961575609 212531708 528655784 674853932 236072060 785380072 95748481 589697264 35066531 201409978 851374630 170127814 15513495 702612780 3278594 307229815 321349733 337309621 13424485 972230607 748511040 480505367 414286595 482400800 212922365 66855378 665236595 806690749 774056597 158106542 89925041 657852800 149913511 592024117 222501533 66750790 9087731 523243574 13276025 889983597 975416800 709350212 767855 505384029 451140087 25305653 302331145 809442556 774761318 165356452 54385335 738340152 870232959 278420591 7971661 829143425 378426166 864566841 679648898 9281099 164398502 826656233 436948339 130953361 275085964 561228329 401389341 471765069 714981578 352328168 23570662 21222145 745816294 509709016 33502485 470935602 4685193 31135729 800203093 843598311 924491776 230125548 960671030 382661422 46874302 445371337 47728812 39689368 5897176 863511882 903860878 968967352 740875655 644220277 61046040 504394407 600961706 11450646 496944746 217436291 342572354 425711931 430658823 720175084 281226484 91209142 199780439 991541893 262384010 470531999 250853669 596293753 302951794 617559503 432350753 427337459 830631997 329203046 32417375 897953445 372515106 820791365 635259862 805243458 358035833 703511445 58428387 85667076 928329536 149626430 477713347 20642087 638791577 359585649 75585308 891782764 53561674 479296799 65498229 307689623 642195259 557036159 166322105 791078385 53050108 876746380 780122808 857755079 941881149 888291972 145169318 724934377 71154260 956520555 781927835 100879915 628637882 486449542 62029073 940604647 521058190 14512864 849128041 135081850 666265361 307092937 262409318 51614659 71492392 15080018 585956015 417978279 804095965 41142738 448018514 540839823 780808158 20018019 630445628 48573672 785367805 396676197 884745666 304514210 378896046 954091259 641350427 49112498 481036940 11939978 389283811 302989201 253711061 739336253 505992602 277698746 24376041 958166403 758335523 399611184 585674703 797877902 474468422 636636405 18626735 283811542 460564014 569094804 408040281 817622421 220177388 132663704 229016253 886506569 139311090 31400722 962323825 33684277 47802264 232547864 454217263 909451743 599351706 238490176 463865939 215337363 27416216 702192169 996909665 318400479 793714069 377599987 678586493 95122198 833819257 814747074 19408114 35569869 105368719 62505535 614476972 134375009 323260168 558426390 751281597 631853934 628852086 541959545 951100892 878625881 446252625 770778267 550210273 50439368 862184821 128537142 952377162 870709796 234493602 51796230 35895994 151502366 135782395 37939532 748334708 5968167 156228744 266571596 3238884 436250359 894439093 597137872 395641623 740556551 102908624 237408418 72637246 591061782 241598862 230963989 11810607 709129640 597299846 172734077 234323940 990564482 810684085 964992179 983047930 375468847 780141305 727661202 277637426 610615679 162308758 43715708 729913588 19138563 691833268 990709461 924997831 383700114 581799902 433297543 357621210 574691527 332933764 765625725 745181823 111910016 623763323 956037928 495374506 208521825 872105848 705425661 582331511 748732495 614867096 55510261 356732577 157840885 485388507 299213836 468999947 238189378 640563364 226127042 21462843 938854121 932853051 153905565 834000090 91526368 679457612 220824996 569582646 259675361 176615781 54592230 489454272 152873197 737284731 890598129 994568590 670757828 31268966 877783388 59508186 880703341 981343840 318244414 484750721 35324853 929377162 93960883 672576901 261010600 800896359 321935710 705394827 253804825 982006367 828435682 537673566 383932704 15080510 146349672 563903850 955192470 407765682 552774685 783778625 61698459 80924112 892366769 639056154 705389329 593467536 809333976 594176333 331607839 6324556 282107852 94149337 362405294 6976581 902554570 487848926 295401199 410512414 309856657 32398371 63211476 405222495 181044710 306526097 474428050 100740596 933421074 409718966 62880037 189663659 319268962 422501187 796729292 837780666 208469670 169162382 532662665 245558070 82716851 799062033 730914978 322710173 865253602 596346345 956548387 149779533 831210638 51085656 494308185 847212554 779168409 84918595 634473048 378994300 210430440 947952821 113539702 837847982 621086690 713147738 889938895 296153489 876185334 883945989 632069311 359262839 770370834 862034219 909580394 432411545 965007916 602487653 23755576 174260113 375271101 718355954 24755025 473848032 670581313 35542322 474118949 804492394 708618680 261095212 66843111 469152757 230690344 585010697 662194701 517281965 6736153 469648023 838038994 964158883 61459735 962328263 526094772 828404297 751487028 236804143 982679799 988466424 891362948 543470217 692180511 193809770 877895327 797788722 605749626 337098560 674398754 577455788 387780500 586443901 687420461 495889693 701528000 778514442 93005799 25160397 797211286 114194480 129482486 285339564 66799216 820105505 544686087 62328522 900392940 670289775 9540428 644295388 435319917 137335443 55050489 624073918 828705946 551343975 680682950 635433451 906500317 781818540 559638897 202597639 925389284 34013574 768030521 187408982 563908388 872975867 185347171 612586050 805840209 66817399 860293305 229356505 51729640 100949835 163734790 51936588 565790886 994276649 791624091 677349489 561292301 934617002 38775501 309573954 915448294 879796425 775594357 568933469 744538810 165989989 579902830 120979330 92441431 303809730 466051099 344454679 69063506 855255304 358764766 7231911 438510463 276724675 164670882 907818590 26158202 654277473 514523474 262058383 17617698 225416888 955492960 539437103 44054296 530313086 962064703 675743575 971214661 275344590 544026345 399077574 474284113 605576617 452232026 5757789 726451501 310553459 907582483 365068193 242341258 291314802 1261720 405929532 56312927 108340819 913550066 242474620 539336807 569594020 508631597 708134610 66733216 546875227 748305627 970785109 30044877 906149197 407524752 114116157 478055925 518405816 977840996 463443560 987009763 458494906 430293108 845817304 832981156 284562136 534485089 184276530 498722572 357581688 890212047 689750337 262192945 536916071 72367591 986796914 603400685 620710483 668300502 647362134 60982881 383670866 27751500 27380514 202557549 285869145 568522494 774239538 528521017 705190342 384726053 562885762 489716655 767097815 230996476 314314803 28253950 66815025 472957509 273895693 789879064 619952474 413618885 55558647 490917685 927006015 512123843 62599808 841278030 44648878 978785933 21439833 32484771 845193949 40956404 596966617 929322294 651329506 27664587 47581560 604693582 468631864 830285420 34981972 947387381 963010881 108041522 621360047 612897146 813887678 238503680 568952687 530824431 107501912 496208825 163265949 419207083 106246171 271997382 2130150 265136842 467769334 888554643 87531805 329018792 356496444 571900690 735497655 746116202 226143014 830735926 936304718 725380726 52358735 622174073 606811934 566891765 14746934 852178775 292593547 55617880 366726592 957289425 467587225 747037648 533544627 452341483 430896499 334344660 660515900 75472174 22202341 571614367 200802922 382927911 934853345 835252144 26935728 15259366 109491454 946960200 992231783 634248831 979327732 372633327 15628362 752352397 689728033 239634416 354029816 569558442 538092295 656977880 29489270 71175160 978502604 853335803 927155370 133067163 518263481 60566767 343708897 109243197 655063228 772944143 17560650 57856137 746826726 898931961 429080184 7496368 69935085 141373201 99499492 557631719 105005738 639000316 528327273 602118887 10744476 320001573 23179718 50832747 957336932 959458875 643056672 632552118 426031175 801554353 854132349 98058 696038576 737640508 667929930 23019826 896170667 418279769 7580886 751144185 465150826 404758213 524836309 16930225 62120900 697117955 603511773 183589549 999806641 6565338 297196524 89724871 55021007 625492180 527531233 623573979 612855265 42462656 364069886 230731593 892716363 6575920 417357677 757066359 697809558 189769468 460781752 3529805 277869810 667272893 944641871 58742456 494571695 847994451 886674181 827574055 510646723 150004320 727979667 705390865 444601928 420393675 492057108 743985261 402055419 436848957 761920903 930819640 177804222 743372711 33475409 991912179 702890518 567654074 256371384 865618722 794117038 778011758 160627305 774191567 16843986 69077116 65831155 892263172 702915316 39533283 476565834 612844628 8386859 867663975 307210565 631966035 52117679 510052621 745941024 335634970 537040223 645312673 158007034 152691140 862293563 67783472 29139800 284114163 865322474 825896847 473957280 103227468 718647093 105345490 742618527 374281974 497987466 635925973 71152388 773816607 421251450 327220150 940723171 230431352 685004603 386037848 786173747 82841780 898159911 220574691 154992976 393423373 186956859 531593279 831786105 153451454 118287513 632016796 970751315 307310730 778053638 733139693 636011877 5281076 741907564 606472296 497569178 600994052 937983578 64423944 123885762 688789577 591147903 743107595 167376400 1234641 280759603 72724852 925467549 788239475 300487406 107785354 499695844 835667334 763190479 986931543 67563845 113156455 229572118 662794282 162369154 577038583 376176554 777974294 845286213 201669914 597584532 958210416 400696728 567182649 795370114 293062741 71649643 85648832 543674437 561266466 876413714 782943905 72897108 463633146 22479300 720136656 408680774 190524484 876128797 43632581 992788059 218328361 54980252 822458365 795562484 776372250 518812710 71947129 131474455 912170569 667709570 227847998 556153068 374036011 890265819 996495571 139412291 18446845 77625921 23391942 146624267 740105787 956163624 749008679 580451292 926394410 59098343 534914571 687949679 24584783 917323834 935603211 139651104 190733558 4533696 387638466 878851955 52152493 196526462 455089491 52683404 550611142 206000219 934931168 351364789 751927256 793977506 1722132 649873372 326518846 915691139 24227482 878550802 627470999 979063442 757085604 80536333 70658628 332712006 352198245 66682023 481256942 793167483 966619543 152019293 184889853 105995248 672959734 78921169 253809441 36587978 705213378 390492233 718840525 99763728 563373377 253629229 231684023 550194733 232735547 248534925 766465114 675318129 925960316 459861912 107930997 980728720 54333270 313477414 42832009 677660449 828368925 157571120 190108254 136626208 54867369 293794130 18361726 790990445 858576343 679490640 460679352 343056459 337789960 227247758 831741343 451816673 38065056 70472598 711218953 60229308 23550600 615192982 350486417 130416204 250864557 369012703 676814869 460018786 572248447 408970600 747499064 391396537 9211507 962681161 169978593 191328362 581677953 365731648 45502650 954421365 661267623 132590127 288953010 883103807 479050596 34995356 841050747 828022799 820685629 924919087 330397453 836251536 876556860 745305400 775154465 591618130 57937772 473861927 71207863 526258249 484182366 33566481 183615121 382035020 477332647 873545522 976660661 590240408 539044448 705507942 83909871 27880778 334864037 722038446 965515853 887145704 644564758 601081777 161684129 257456857 614867289 624298297 987099395 632155112 52092821 171184562 52768332 685349573 869421305 105512110 860246428 678306436 647889971 464444771 182055636 20705052 426131962 966002987 481477917 429539818 308330885 40169988 487969631 127430699 669919505 973410574 32816843 122354053 886690910 471195919 892927826 453367935 882322226 439249138 821157419 959946500 126224342 35837508 732350545 648599781 523087252 205465526 781015810 951746132 310497087 294381469 962903106 68037737 438183339 705263221 313964886 415934880 881432112 854746458 1504585 684663897 846522667 23172749 643999595 40271703 721031293 580266486 302115276 444863554 400457226 103326620 656775109 647425061 433031740 945285678 973716592 181405168 614951550 104857469 255037739 845371127 329693121 800556288 62098458 895194993 633046266 93390415 492994210 719312123 565970337 802608040 52675566 594482450 581485620 470674542 488996717 186910620 200042674 326465956 488532817 871582048 630886177 960878710 781235986 132757130 548613640 821245105 252212714 594562344 56495349 745157446 240786775 394829743 26411257 575810763 921047964 336549750 593458471 743176185 500551231 972638009 353938713 221365295 459014284 362253720 128638827 525960174 720853521 13911958 986679869 718464859 867095841 762499867 351048629 598075072 945001809 391225714 659566715 269868300 801297918 514398668 443734588 383758926 86010052 172657595 37115431 897259070 1852424 836972983 438848371 509135540 355475824 272090013 700344791 59290670 501230693 30265130 278503440 788575822 955826328 288414852 986014303 80693850 315799674 757288114 22656776 359165371 361679810 787386400 415665876 434031231 22576620 177903388 688183184 35971543 749051060 214535771 903898764 357742745 745918111 83353973 825662749 4027326 613593458 398118244 449698075 432769253 70565560 956465929 211200867 320983759 273316929 240769447 787193430 495598049 397043358 958665062 349277273 51544742 929084326 148874705 3606099 846079050 149540596 358920281 238307890 959090464 504013414 19225296 189548903 234441500 689120415 594338286 799719269 82497625 220002183 446834640 57071653 290106261 373987014 109401715 717317797 870181040 436934220 711955006 442772324 287542577 62564044 932559990 866429672 798270145 787146300 61537223 146871353 501535150 731310678 220664001 153204579 20941673 309306138 696083544 362351608 193840392 51672907 56815204 17399179 430948805 804170989 51271199 514425910 968912253 376543181 68181674 976877333 424986417 526112761 932288904 542029513 465296265 653535300 781691169 277680630 406802252 759971012 205525825 32123845 6388201 780120403 537043862 955049058 773820402 586418193 670162486 132676479 439442844 664319968 989397526 524520144 977736000 237488870 455023507 129383053 122426844 358878479 801351405 706691571 732298643 157043337 669041352 63581635 426966057 195468870 72020650 44807873 147616136 61165694 166687103 161589303 503612478 918799658 471241752 481646191 938101756 146307722 50885031 895001917 637766680 599857056 5265476 51238003 114392588 149457586 217381740 967579754 235875317 138590156 666892925 160623743 854711061 556513083 226238779 670547348 107480657 176989203 53717582 18861707 828106932 588675754 846398402 943253711 451876842 159614747 797134213 328979147 918531782 484172741 263270380 285955696 992217020 615286729 696806447 569628596 64175464 558982543 581875944 262929165 36239109 69998914 707060888 129227770 391671543 267069263 444893219 267834235 52528962 549866218 71453007 587779732 571331600 482235529 535506248 879310029 994024495 199202919 677968671 482303669 582969232 411004162 490450502 773758042 95668169 930888093 750811414 809749459 71167124 948016319 107829065 81067959 934870606 44509363 353513600 866301347 553191545 515564550 555322047 518462648 49556026 729015307 449236204 529034266 184718044 566114138 209195347 156453234 588724299 49732173 887490597 390119277 336192922 348258178 157477364 68778555 298943358 156212828 538540601 817483793 358591696 261689729 38836686 877101991 585042191 195216733 648604020 14947514 938817243 918124190 324762703 401180299 570443387 666140855 679221861 230464607 12515929 53886045 305795874 571909117 378884993 334097933 589078487 37780019 46061605 180634756 373708342 418077521 194916891 658925380 968043224 175471020 318015325 129537302 7898040 421798941 398237320 560943747 23892149 828963968 611010910 554149977 57241619 505265717 623927109 849965613 864161018 617026722 640927685 843398355 726685174 164889006 970560782 64500967 556510582 21105224 117354096 329688392 637969997 753151710 60735713 48610199 262997556 76946919 25244026 570398908 184899653 243940953 175146490 348625762 374247297 25195571 243027777 113607286 593738060 883110133 608081366 158419372 569950188 2916387 414235747 807419 836451598 732618694 285533236 937578524 26808896 104289003 417896379 680020750 985910648 247352353 415466766 471771796 405292939 104681983 871745639 66325429 202775223 261746588 253445795 449536316 278844186 4890901 44912069 823348790 90925881 50283019 457933168 153966711 973049466 165474850 66027888 497734933 536538026 314276740 3598385 891789546 626235255 30699868 278758214 579444502 916324087 832176219 610031588 759187324 692316704 378137398 933391717 562349376 231476813 930288933 433858501 144385360 706162879 263734885 468595240 152048856 463427866 59241144 645396818 788279243 565679076 640123360 940684845 474013537 265209098 707121704 193923143 550062227 665619035 564433627 641540178 986368673 464760330 681040074 237206178 57328525 958376240 479985354 675391922 688038046 977712712 20335668 54093472 324413662 14218161 202943332 797928876 400367516 941594159 425553978 31593660 402596074 524299115 130592412 624310747 753846815 997715054 24008434 388918198 72048215 845062186 301473448 837279262 174798574 203853298 651633328 574137481 49521673 501022716 529752573 99875984 388522253 463853030 134410761 841099378 270331174 318940974 539426641 558553488 110753730 218953145 275321811 162212591 22428947 414806093 98528662 461188025 550743696 24804119 914810146 657750460 933159284 327713830 227075076 733768682 176917822 169218541 64823628 213732567 955947567 228174277 110144015 819471679 219529167 470380649 116990949 132585085 873411433 52055160 453142379 960546068 509994634 747014903 124179650 972247850 136336774 339918284 395015183 185035528 688973299 247951940 566090745 532699547 219338028 961257870 863447086 735820022 340506319 933391677 630882270 433072846 459965248 511156682 414395454 688857853 199898659 93440272 423182087 876823040 340622566 34622671 734775541 529645433 140604725 145565993 24518728 785999021 696155012 939339559 334280518 66295558 382044552 179164981 701399734 83063442 627221694 835134370 48492647 711324803 550198499 384504610 744385959 898741678 855562874 110502732 25244620 246985996 885456202 39772955 971137199 190132795 636914397 993236337 564316460 475830269 229436674 866149263 565650340 612267704 42958923 168304543 841247867 912428789 454161040 719886123 433624730 988638178 95301994 723219875 451740141 64996304 153774265 168867546 115605990 740435125 752226591 471181705 988443640 569727659 147492482 479199691 68544030 20852335 43095182 675314592 732384594 398646754 392681265 528485738 726256662 922869900 276133149 813935219 156305646 846492180 118864458 160994660 486315235 97332425 320150641 862438095 984932866 590984221 109642641 322096039 139151835 698445605 370235502 353759171 960340995 48517914 689349389 44785247 854748306 706592218 302856506 659901082 419003046 434364520 783449346 510409209 21874398 579090792 810396473 831498979 278118879 675848100 200358390 551384354 46100691 162815113 314033938 952989288 22664677 767809194 839358124 342951112 599003846 976145469 466592167 129397049 60594475 832937369 382317610 832641559 563663181 974399422 918133792 915606946 414791272 182365901 17964470 579157116 652443964 52746380 523908064 860666927 520883343 671037155 985926356 181803429 688981417 180478561 699814541 158022574 771515094 389555384 80071497 267179389 742320616 166376253 187801099 706177323 871777970 240777577 855964442 549509683 187216270 88142683 559007872 874057717 973514200 852793427 175530124 38821428 59760241 352605496 979001425 4124567 735682109 565778195 78579236 27534891 675426981 756409746 489693218 325189087 532434454 934776198 400755368 667218183 353049728 620092261 290963161 307811034 513450967 421586377 55355163 365210612 180513430 69836271 653639578 503864533 738307639 971320377 19919044 582832223 222538172 876742316 53704652 827866716 236809257 630546291 986793255 526843382 655146760 886066522 306565393 617670717 364518628 123813972 612433417 504973989 825833422 930003958 996226385 916154757 642060251 840573433 462540655 986518169 461707683 35865276 19527855 310361984 36678340 674249151 704209311 589056063 877572701 486474793 162867601 434546109 22765972 598994755 239804700 507364421 814802960 101826811 236373659 735634951 789943424 508931171 62721709 352982423 870844690 225872943 913207987 754853996 303390716 426126650 170069845 435868002 412228599 860793089 937415422 262128441 511762111 634802214 770817115 824697619 929738645 727327982 405809376 463866618 260395452 741696964 272446275 407460952 804137727 620341172 902013439 916005501 720288298 884244721 783934931 246957341 809082253 321766224 262088768 732023503 153790844 790972106 733800974 493677455 23971025 882263038 224833991 864596797 491032936 989216429 372918842 520074268 968412834 460587068 123638010 18546515 21907939 792273461 835081437 128543088 809878805 900212934 241976445 858917088 677761826 580824384 50045627 759303288 424428157 347248793 873678647 145116143 312852890 863399403 25024728 256058465 604557170 900998388 309911626 12538062 691433984 263263380 200414331 516165272 45986502 158133585 341898014 590773257 474179401 21330390 67575593 108941003 481735568 10674543 26576214 801358958 647652521 540205199 745655461 852090598 37782820 42711371 820707544 975890187 363249047 108683741 747017461 429817623 145947416 180933409 10212808 137643306 292890054 740729115 406447199 43353545 677996352 828638063 475439244 357039707 615711020 88680935 941615975 250064811 6370226 484005617 120595401 443433065 78394366 93424159 292384465 23949225 506868418 464075429 860309091 374347619 424473265 676372958 771135396