2809 3632 373980902 982838151 6578324 638150707 936364479 553361707 182080546 710345261 340293479 567636268 753053273 846637936 274129271 79565008 616764767 354173800 362975597 626790148 255802600 33256112 184685631 997069657 21209015 701865245 836844265 513017333 360825442 70935267 367784455 14905687 445409060 903581039 974220124 303782659 699521633 988098504 612709434 910636085 8405405 601633214 308112890 955030833 783365724 1152615 754196745 281483199 486357327 362796803 240204840 936374654 513341153 770355655 950751719 824366874 361161464 754787521 720940573 179218162 650176099 534576516 71571454 694548077 824893154 713761650 887841536 914220420 155535770 572330882 2560264 328683648 530293012 352457451 104158951 444299590 743411255 603531880 671154074 747695707 810649410 618596284 495851001 343155145 834797477 807010906 625521705 426750579 191083159 439439865 482702947 153424065 897027008 680048200 618662352 381830229 429270331 164957820 850182953 105127910 528291864 164136784 582456817 899681608 793812344 664912347 134365222 901317888 138461566 124378338 822191123 861952702 475020052 276479334 223623097 71051205 953240003 373160358 364448586 530805117 899930297 905814638 992429246 408986578 856876335 484210086 340206804 298421473 536444267 212250640 145122947 353394191 487772855 760558819 586986487 217944002 946671479 497823543 779528934 363010442 371980074 827601310 641808810 140100703 193405166 59072788 375666755 540870547 817077448 593959730 551824079 462222224 915524073 454849736 386229064 80204829 820759302 143912089 218889169 494041811 183364412 236134841 449692153 424598680 486718247 150742691 25712210 788993992 599982560 628506038 757962636 903097261 516350697 823875473 475901791 720133907 981383038 20984575 991221594 449971750 939902962 219758906 848765739 955394141 964416498 380034779 394289796 211599989 78814855 235021875 879154139 27751357 728054906 488811989 724517371 242839961 728909962 866376825 328750025 682629419 577069248 980873103 322202103 871197485 853036819 103591302 892701418 59296624 585730876 399993604 91964284 664810379 223841483 208807357 168186448 448093903 322180909 492358670 316846653 950949078 270877339 477300681 365951018 300390357 389952074 179266550 614675934 657477985 903609160 670414056 828973073 533486595 241042881 365547014 67088662 437362243 333631410 586653464 379589492 403611787 240924688 330192597 754179943 441623594 930858542 452899609 485526791 686112796 500967973 201023287 614139647 789080046 395645266 95344673 4197281 604129133 109373598 759089124 237519589 793351475 927105575 894348218 173744486 590204822 948715934 370743091 799721154 728701244 547350924 204349146 595662871 263241460 924922681 425142505 57454062 777495707 426997231 789240735 547014277 705385168 51608844 818855887 81524961 364698486 442954794 128372919 946175764 658949878 582935599 947186266 46647414 833399356 699626797 31271802 341089328 796074886 822937507 331439595 159401146 199603734 153720072 131047570 359063815 387657751 181338552 521442484 271926799 411252488 38265878 470332572 133368095 349587443 531967122 886467149 356336521 821248559 888987100 513415599 758648890 690473527 509081907 697825920 376433617 791064714 743517451 882550576 575406762 5899840 179123691 322853055 490879824 210022319 831805751 358188982 254830804 706002701 746824088 983039231 695596364 215867944 494889901 636923880 444463685 836001421 146832974 463818465 381115089 56524295 12043476 656259968 773481411 681863174 595088473 282067230 609467182 485227646 347547358 371708032 570205367 298205709 329436706 408563274 643632589 948826698 202248481 175077111 869127967 340638154 162188597 108184074 904168390 836270597 429610935 383792801 305244781 922057553 498561599 350180094 326048066 825203070 74107490 496082460 327468544 801458437 334964702 17832772 503621928 226568923 454726052 359697660 569939047 763511055 133427378 949537605 78045987 577597937 367995077 301375861 570665359 870508980 8115840 862521764 315914803 390911919 322410008 192985871 738247694 114686125 975232575 687430322 635597029 683083480 753866477 61048440 909656187 25073766 27379166 900318419 17913726 546617204 581674950 224246715 809456850 875667666 44634043 558099010 804854758 968177203 594775392 282781617 964704313 457560298 103472319 206953717 364825200 875432852 705911997 624133088 392492674 763636254 731392141 937138879 489266453 616606081 357619451 180739794 88930608 462592503 147694613 369448339 973514901 615747921 541034888 988931438 716791504 638064120 340922923 967760822 530743662 844617327 722985326 667856668 262322501 123931740 821529849 197810712 153257397 320567349 20041187 878976492 650789174 15537041 916004008 520396740 124042554 150458287 222729960 943369932 164926129 469153093 753768703 75307828 688348847 417557965 631023797 41894051 284623563 348654837 312590582 662222656 12321533 300635171 636135251 601695788 817388547 706934248 541139612 257879972 287111565 662116877 714134505 581888541 495645576 625572286 591588481 295155590 229868494 499347046 444304413 512802660 850217349 943563990 568160853 783619282 959338067 400860975 199391231 549296481 638788094 401261913 53494840 104244507 934602730 702187193 176851410 100336731 609839729 664531735 127665371 124967287 52353832 476610652 787843962 888582003 566245509 451706639 710804018 977288648 888766382 551427171 166717392 134781127 654047148 801657794 154043332 799837256 487240861 407636241 936101957 380110038 58388235 90311552 808169547 733756002 389394193 171783315 796473965 553098931 611741824 751704509 768543760 11283034 354746283 596400861 272133638 91651064 245166901 114822876 169220078 711717746 9206862 2544026 977127691 900267153 69249538 234719398 173878067 55451077 160582706 327439812 166062748 448640901 636354033 326222924 148170080 734146586 698721953 294354374 874619143 651653801 531561423 224673341 192372829 708179867 33481879 251580172 297908743 172772173 185909313 62191518 528467795 139646993 936940935 578519902 228491236 943137206 220935954 19746649 213420587 103232081 715488815 61825293 630399271 573235135 466033297 789678564 263940513 951788086 705005942 255751041 218800211 879800608 624908097 445146563 375111153 181146695 343230309 58533681 307989068 38400329 317655084 981941278 737858465 144209349 207651239 285032410 998482028 84230419 787981932 60596108 327104532 79033361 86516347 28067366 334324390 897664700 237756833 182804042 618400244 976788719 433741006 138216913 550099871 213584703 378381579 461217843 589887024 5694700 487919036 416224372 415845040 818275496 6120962 268985657 858788838 603862899 947392658 981508646 261119451 728840460 995855080 318580165 195684799 7182134 163887801 146779014 303688450 783862446 951573504 140700913 882629965 160098845 566732288 188638606 659524795 429633463 662637813 447272105 890370095 696146612 705645385 9356470 529654360 764273657 425087431 202139994 31607059 651408483 430293439 936320474 3291846 189968235 924175673 514692127 158523609 987772160 697437503 248356803 805457487 663121130 963612093 675178333 323561833 874950177 188635316 227081791 597666565 104225162 532206496 198102153 17645977 929596463 929102782 608760091 425527238 277540473 510603828 729806024 807127786 934214673 263102403 344963279 878046657 46673288 90560820 343974573 107125400 366987520 516806300 126274608 936070661 596672785 614593427 655750837 489631141 452653097 908258388 542335691 306106986 290525006 539123288 285616352 664706886 42269383 144642521 857073816 400947776 646384393 901727189 311181701 561648053 911302977 673729719 797848770 593047276 833382190 23660225 815519264 440785518 605022618 972820385 329505259 280446856 744895644 410296393 252544385 406180897 636521487 23706165 567353830 183149998 415404353 137092775 510164592 450185637 966551413 904590641 414806575 284693189 866099284 830738938 811215970 888379932 448076351 550149628 383992543 542828466 756571764 952844194 409037393 746169735 214426352 784444761 675479870 266618415 962408779 211798578 602127660 644695638 474179047 308124170 581832632 298372278 697123211 803800238 626994932 117228442 164539339 887012252 91771820 460566417 291600738 150972361 435307347 898662995 710009340 783617227 686120098 260950131 291930076 167664420 674755522 237930551 99812778 804645306 33673006 278869855 511093273 367400718 846413297 215446908 765591309 229034046 137006928 613896201 414696890 539787996 19104030 162877803 535587288 266616492 794903257 393561271 10394644 6590906 274899631 627588782 986936628 922001672 905646099 928680877 786269551 35828543 139398615 996816416 545439038 358335908 519206163 967052440 451271650 102654651 163774756 512697097 632835064 288058409 654240269 647457863 134656396 69661280 493804339 305463482 728655736 354392796 325075357 455942690 443751966 777862612 241185274 727440225 723070923 246149069 85996783 761793641 655414585 916973520 761026262 45162036 50763 586863044 886756618 532049876 737042240 749426937 898277039 208153286 237759148 680202785 705436327 557431914 100371310 605620270 754990597 795916023 355720619 388711505 399814548 945950757 691350502 832052328 194923484 447027641 520183975 881387436 658277113 814883046 751906226 225333102 677246839 397801795 830964790 287217475 405925669 400093596 119433949 231479065 878105071 657846486 287576537 504284030 727124375 934623101 336284654 300756592 102145400 210039476 199627744 689388362 687761000 647738530 355703743 892713504 878835085 369526467 980540151 473957693 119258141 257518052 956219946 937574378 882940253 365452646 311727325 755199685 445724501 920297585 277557895 85439718 16151409 956139299 618864060 681068735 243672573 575800667 144499959 349726318 715071557 198949198 964650031 853093185 853801251 547832747 870042703 929366797 797168734 885918564 941734282 251493523 640706491 182720017 255923643 206189097 472728822 357667332 202683082 538604731 81094425 725151129 587198433 10612839 277100539 896920218 815589546 120332537 51273155 385507955 550804254 618062685 207902411 291433256 623124660 108686007 629921284 362660888 89789761 835615558 531680884 298135805 501897296 254758089 99778676 533029485 558602129 439903602 951356014 80542916 764690600 466883737 470702668 264015170 426323612 391139950 553527552 948410238 348212046 101923370 121804737 838420925 705806436 908327072 760085476 471514491 869665433 410593331 762366398 657852631 200331102 735526600 45091201 455102914 277796005 505071885 407726181 518167586 209759608 965001362 513384028 809599910 422101723 502995891 830445060 599729328 637460468 187576868 738356788 783372213 230861184 379116816 399562043 712508974 988211760 681678949 545954095 719083867 32919240 465164160 959573885 799905988 595374245 512285062 135011106 679270524 114128124 36084905 517845739 863036553 873746343 539170765 488743355 322200606 618224508 903003472 449095578 641984585 625089272 752959816 556718743 826301014 697201880 791436035 713400700 641259681 337884186 862608840 941937883 382225733 675762412 144521681 594745058 157393537 947326515 694607873 10049705 119398581 737110276 140109381 993186326 496867082 656870145 280864525 695782494 732452840 360056786 906632627 117802661 427058155 70056189 164484730 725004354 947607723 294863876 69097329 316874802 142659982 635670258 653394361 82650216 593707676 658864905 197173156 125325475 728922843 591981533 524851503 964939544 154938216 9768995 906454264 781740111 390742831 772483929 186133653 342198193 928538221 828533998 311344378 754834187 500457560 935730033 230387490 368092226 284731712 686276426 203607195 202982006 412998045 289887785 252040390 336836759 113028794 703113959 975504497 589493577 462083967 613072292 396798170 365856793 67952880 526037312 347508406 812182730 642950084 292856418 204124776 750472805 579089179 873471793 331634558 142811017 289378509 925863880 698867010 22039390 5851238 84557078 229485637 652700318 210862595 58662967 554360175 258497959 448055940 56463557 661603409 93856436 736953331 639144483 703479063 472936714 940324587 572119105 215750880 502969051 702288239 249618842 384323415 164406535 255424291 84119474 318201781 749123884 470136316 519380899 834951681 898651500 965180852 713343469 712444853 881654842 348755845 948520391 18986008 165924622 158310075 697185171 468037743 958783459 5460514 705131122 486581911 453123242 391684740 557033423 423912602 676639658 580679280 246246781 638032505 137448586 493357126 322497241 347080606 774494006 628712578 423943502 614231627 847810434 925145384 172651731 543449537 189667813 639382524 817753629 957022763 39838639 708577841 667251513 339404635 105437402 412766630 832241905 443339174 554476531 323487201 404875269 62123676 628006151 743559482 880586358 982946383 361370836 471420167 573213853 659744197 759454763 126144854 514965122 144351508 975694922 654664731 175633478 595144015 486896834 173700317 873544527 271205843 97396157 24926718 478026669 934736886 46899055 401896327 194512671 750775565 418395472 251206695 836990193 592742248 279913479 283246491 741164064 913602869 787654950 498359146 403814288 72136510 923131027 879926149 845835772 268590582 27054393 375047176 566828748 529060850 913754724 656361585 414934138 473865853 366906876 83753774 289789610 277101072 21340433 3079683 596568406 507062574 237738833 191055956 980574088 28246216 508173516 947259735 949436512 238498498 197885389 431124987 28439504 765331280 903011910 14161355 413309521 314817031 435305908 110103211 43582908 953960400 77885396 305858685 106925932 418416819 776657319 693154853 596139594 794630682 897520024 186867059 116999988 495442613 240454615 863753737 270311709 77918799 184898622 819008897 261127821 319581499 458780001 790567897 451330960 453189070 229219001 118699680 265831686 443006327 656877533 332804860 843373931 485647246 153732920 899782012 3477425 716026269 761573203 684760270 521013471 693663816 313828314 835555275 200163904 578194234 518248232 321686755 153333858 502025191 551527300 691901941 848267607 538467042 653311862 293696598 750127148 976134940 445093063 428657918 291582845 284145378 125393462 707711461 988474676 757828187 60052291 467752136 202593071 629774577 116527326 941104899 651260466 578153740 645077868 690963807 76942902 106807863 648733654 431169825 25391886 282298185 265046769 733326821 624336019 662616247 281453144 215717783 272936826 32573754 589266934 67370749 412665724 630764638 386959799 891646492 933350618 421413022 202882382 395646746 635285767 667829677 879644701 931483470 168166521 766496861 103907786 593328880 750985527 176228884 939492860 824485896 350092237 980183740 725776544 500460412 896362259 228304972 712127293 964971047 997922003 939015840 937601325 93791565 831067050 958279014 84121074 16457552 563840374 750300225 242416081 636432222 282646155 535015185 710722250 244914727 170857221 482523720 708339361 933969192 256414519 199463020 826993856 641940642 823010255 116624078 892233420 836227222 774426669 237317714 650868654 277517521 348069224 629223002 142641047 184282561 128801525 354069128 76973539 725466334 577922707 355288028 346620310 457019720 786201028 567119641 693140562 426760922 539273695 11913254 367066968 409466940 999375233 974240581 711865964 444454237 448337677 544717255 400721209 329450884 414737305 126866558 884537346 272640232 814214345 903785569 15152759 59250113 957215530 674291397 654302819 105592251 286278303 36168309 267680691 551019959 824526814 562278576 811790735 871012252 985155136 553305504 402516499 856073561 96981158 82005266 399638267 692710093 593423160 893942229 476123921 839689877 458009525 580489486 203049987 770853277 49794582 754228859 536677479 624909369 952925472 970877929 267847823 8005716 889228562 73547710 157616753 956632095 222334655 449491943 825420408 196710128 394219336 470773505 630691979 959421448 791774468 790611480 26493074 379333957 883611979 600327593 901720983 581997586 451595405 220085735 871998284 332059715 773923634 440303933 128097479 815637405 317253164 990415330 497256145 656470544 545351983 140190327 626008355 891984455 232636254 631047302 675068667 321217908 104772369 310470706 275454624 495845942 946122207 570318883 947498009 39285543 632220407 394078941 254748201 416006361 357782625 717623873 296741768 3843186 175426473 834607348 118372830 92523261 962826506 998438819 99847680 591465028 325024713 124632881 469512798 997890750 371161569 598704468 127099283 610480628 845290781 922598971 895874656 339331372 119648636 404430519 327742620 152763073 467438024 630760285 605305723 538783939 212081444 255303103 421777836 615938865 260867614 424847028 844863680 642170762 525801438 323871943 335850338 226263993 695206460 218522140 416485816 200167437 593364886 590027324 313039303 941755267 181658232 510898198 292442915 761507129 32544813 50033078 471862050 999436263 905906220 160787556 424184072 745885412 35715598 28741559 249739478 81268029 631288904 229677158 309382714 875841334 101848077 186905848 36553288 796439354 416949149 109949540 564007386 628113253 118752015 765768378 537379096 203500351 247260943 727394845 779546669 89002419 371623840 624409414 505010636 103194626 233210277 327206983 970263949 90862017 859827157 187147667 533015592 208800328 393936127 426739209 627014201 812489192 55228593 207533881 614932054 180943250 635303608 465074926 181349659 308677350 703939606 362082264 363502598 514849721 100762612 316754654 983841946 931326213 719762872 657609433 782082448 573328891 824189537 5433637 680198521 12786618 204315343 566066550 870289426 12681360 413223272 716813500 993229817 410886286 602096272 275963118 158626176 326943763 818907247 309964311 389515162 842178543 734966145 496674152 574602832 220763808 342643972 189823623 335270619 227180021 843183297 583039507 621459633 961895370 542851261 742236755 232797632 791534021 201861193 871529566 566948137 817205687 639555516 273909743 748005677 20041562 234669854 741522650 784874284 154367579 989663959 610668209 659824396 645933753 995173626 135658568 763832587 529467170 547637286 729080116 783293069 807315922 36975861 158007669 500097089 398461977 120859756 999809848 356821949 904538528 270732927 791959572 477641362 922937341 897995646 322836831 417142174 914761800 337216330 593653888 61852995 979542583 704554763 802160862 224696662 332331187 55784052 306686116 715429125 145862900 843629129 558207186 722901972 137977632 756274519 543129367 167489271 599035605 122734164 118070179 504991343 215128213 849292277 890387824 366472481 294037296 10381748 394677234 245220889 938342038 515176609 332933011 651133598 816236163 94497798 793447688 889231246 255225730 298983255 444815796 107980679 412996256 696997494 93486979 653292165 304761595 159225280 123087258 635627251 596771240 358804573 279595396 793490878 549785450 368069561 884815300 192703050 416109239 183407494 275457373 931829665 904256421 830660115 172650248 299096468 35032493 281227462 863323291 928890934 904776767 295090406 457344845 36329812 191913076 974314089 28605306 835954657 880916257 648466638 498754543 835430922 794370764 802243899 478149885 701539856 503106984 32481448 304511552 273837212 988451187 294433695 417649413 609040013 854312665 635039372 597113604 184550924 768893131 436263841 253243161 577986278 464061430 315350697 446993505 306280512 888252597 566060058 151304801 752119535 73547745 734535028 978779451 284976932 999014703 623823641 380902809 157543615 875751992 355774829 375072209 786429214 450073513 342845997 883485397 346115446 125742989 685299945 661488229 769730461 951800920 548820542 607621782 598880556 379612743 206733740 847708435 289596964 911938945 829895181 853566816 31508084 889088956 128563037 74713680 625245620 196864729 755982172 411207318 983074628 904117458 382026216 137192540 395391176 118983514 703300191 694953089 270212120 226755650 920094285 898369932 391071364 153998381 690504161 241178351 921760303 14259542 252198810 893083979 626964091 657153793 679134282 945295392 402232650 967168046 506810016 199147921 508569699 355086554 240570079 194108747 235209116 337880473 211041099 545820780 186201370 563675835 149503988 320254588 631639623 565543176 88110311 267865362 417851840 719241250 823135859 610435880 678634403 947310730 506560393 904857260 754619789 515366721 7215407 876772016 483248473 928905905 653629462 53852926 608352707 602322223 303522485 694565799 753089760 481375481 697189966 739660020 321788029 724960523 256815983 386242016 706791414 33445730 598193584 184083575 468818127 60718366 830768010 5584413 821118497 462058983 163547018 212479353 841735327 116768637 430042507 504931498 258436234 942101974 212198947 473895592 810520043 257573991 344576147 189844384 744000645 548822063 295448471 164479516 680162477 622432218 39381078 558598296 931134052 44771010 272784296 950168735 438454723 296075684 617127700 294118095 505161040 757511086 717812921 567018293 278074910 678431721 489918367 131836312 513699436 222590441 184432085 301310210 380984829 599974885 352359659 106223984 683837277 347307002 17837308 184762068 548495379 969851075 73713446 271694507 169181475 202305908 684507455 27870518 617557338 264382113 768236529 248186300 824096235 999470590 976127357 120076813 334119449 576938483 784945118 181212630 100326738 974587282 722287707 827701127 660205930 383454459 569636252 629163163 792181349 140873047 986535246 287641792 636408949 101997183 471479753 865000952 158027046 859731832 893788165 743081338 571191853 726537998 987359973 789370620 548443991 741821955 632636685 358958999 268982778 558269949 793017076 690503619 205473139 71589218 528522597 347479432 971596107 281809812 706824583 638951671 752766933 913639274 645598794 603385474 877899001 953329352 8312987 937018425 334329351 945540394 753360302 855326579 508398947 434427048 414557814 75906671 716737363 261810064 888078347 467181327 994279948 367672384 327548283 387312838 564790031 35868578 914089415 378466931 97972022 217857832 150161431 395748535 513624816 446962563 864468269 929503280 62327664 373882291 473548515 213237813 33717929 545676019 103082308 523273482 692924823 293110961 151244990 185830632 79215294 833595262 554431492 600824809 731933217 534887556 404239104 659445407 7742413 102584267 936894557 360072702 117399938 495378350 96384064 733223425 760673361 90957758 550058084 427835696 383222916 731226602 364682875 868182284 547657239 50657253 416817254 184873498 124187117 911751341 797197951 867703405 337126500 996510210 680075843 912351871 973660542 547271143 278054086 532692110 212854729 840481110 693989772 868840111 278483731 584904818 489974848 724095318 461226716 300038566 906565791 128075717 412313010 83372472 236164585 765015538 902164768 124357548 900753275 344928485 332211593 706926442 717960008 599972480 801956894 14578834 11375478 90541238 568110947 239980318 950954863 382202022 980942525 875911826 653828162 575198513 959673670 990457629 919145060 774961444 504379675 237260573 341401041 180504501 716049593 296158030 228438149 628979434 483036688 50573872 289851839 237504897 467470577 187127620 510469063 670605452 257737193 526710087 373014785 298614021 756644166 997167789 24760416 471608789 924842721 681988030 91969419 484134789 265742008 278295387 310225775 754868549 173688088 294559887 904952983 501998324 252854995 334115920 69465673 512187562 434204085 706417658 942317813 650232174 463532451 226726841 672249321 614167803 577458229 337884748 334977490 798706064 294350287 478589722 494231735 141440158 5443311 554546326 998223284 832273251 179839247 909832731 304245822 485651318 450002086 642854552 151886895 430597904 284979502 120428468 664827003 546792199 945250894 915855403 216338908 336093320 562378065 535462874 576121655 685114739 904076323 240113931 973882309 166448135 893203412 632737076 17293980 177975263 269807934 284723001 919658327 37333956 925997583 377667262 690528070 347694957 73880537 828433528 660573552 149041188 816874869 860676141 276446740 599300616 404682469 847980484 88721878 613563127 440680660 326105888 23401679 494231536 211786252 794509928 25753114 248544290 716564595 104966080 263066592 748202456 975484034 821369353 616336397 453403562 652713960 240809541 974612209 922166114 687449756 229859467 316320532 263869830 624200034 615140325 477610511 946783065 606445450 14647142 398272768 422136148 451836097 852797961 562357392 572996597 888373341 820653006 233731233 211542607 879307299 396705365 5091503 623416453 689253310 26583371 159639785 76618388 120007323 813219959 830907329 619344244 250045784 558966806 395198523 975986270 180058102 716294902 267558427 684443930 786981136 511454904 14854558 949808167 857161297 219366965 338769984 958655571 297567015 469716088 685029876 810342898 223826269 497601206 819769418 578603155 223382533 877225693 423831472 506344937 913522425 611178325 393965951 933746206 819827395 595497737 427842640 167696270 67324927 535599460 778582773 918431794 430103776 630128542 531591124 713546026 753873440 100563811 634738102 250990642 859811977 865836900 154106510 213328983 596922248 239127932 108352826 638502214 849710500 955104927 735941381 46574323 80198976 734075879 673871627 750044335 726431816 585128713 19620887 813235999 606307447 420836450 558677319 930653021 92631715 923732734 385039151 404244892 468308322 932946194 70227618 107825829 66202396 57876136 317808255 167013901 801045656 761749783 857480264 782868693 251675861 937529213 326918720 4964172 623063875 87564009 91262321 2690409 64375402 576923336 794737792 34329906 892074589 588689301 957145795 906429512 649455366 72209819 594288470 635690232 55577476 11654093 452937043 158093145 204916971 480627176 380770021 339467807 454955649 771969981 172035716 773806963 536430569 686236824 165606391 446943078 681137884 850441904 462864907 628921893 888168629 612628394 872246368 241239962 392442802 579722023 609286365 654794979 497855457 783356721 831661235 292664746 105225415 584715616 842171058 552490813 122478050 658649284 154324683 494592189 535795755 82597131 340824668 378817734 862430797 789809073 196063798 662455576 553541933 692937384 962020198 950401630 191096116 388551830 140642242 356845896 324514524 653661400 99045333 661291006 446125205 212782518 420090485 742972022 14180270 310065069 15556184 485935414 784155943 870811050 602911239 330194289 447510971 941920334 363300844 611127542 738623734 345906830 538898235 240354088 425020199 781516783 377370856 509524717 692722169 844809647 563622515 854910809 625838796 815135988 128299187 398076064 607323821 546630795 681052977 787817492 721923046 246951217 583736811 502065661 627098557 535018890 313925436 317940493 167781720 131505186 165497354 162714059 57762364 101054960 864546562 343903063 302343780 890239161 538317711 104463958 3861187 378949502 214002071 510800626 778689800 849561184 149403850 653588956 30551341 76418381 695562278 624238040 520835240 44837767 349484179 538568763 511406108 357705324 918527467 9232112 982425372 564428108 881894191 663394969 913823672 84267580 656436088 649863938 258582209 958746159 113781732 160657514 99037011 990217871 414266126 163801855 21068232 424552504 534730574 269992605 106597788 882598913 428680150 17328443 419258999 709274018 477272802 675286153 954692832 905099198 65038028 946463699 626966028 942946840 818420841 638782928 329032113 594698544 611739715 155656843 884836195 674786649 11142151 196590379 138425601 331361200 275615822 883262056 997929360 654304563 173070526 906131721 422725269 422747702 547019082 480333943 348007491 911700538 59208783 12464701 948292056 564886418 130608387 2305195 481628062 824139992 656533479 819289404 67755742 190828487 415545192 362087675 382948992 181147093 213362629 347227874 790037995 715194469 778289550 321738392 288324312 578304403 831537882 864072701 656511768 345613417 826412433 693802368 588451746 87992876 392786801 26943644 902909090 635246391 403624207 75523316 584609049 523569710 445312961 782390527 821573189 791070627 508342526 502967822 106773431 898136951 49887847 663757552 594541875 446787338 758893360 531496337 174086619 525428563 64417013 393972518 851274090 414786054 472842285 806626697 662018029 760180143 887456985 700518416 385818246 316947962 257375319 654646281 413465068 351456068 811566513 83179934 29530469 62683899 795674950 781664194 701110008 25766472 766291678 345441002 686308695 375313652 895148974 984609554 567078537 414705764 247231338 684874766 519668717 75311591 96751259 284413890 995418238 211473649 237858544 106244408 101710112 35471655 541655593 500563914 679256951 816118483 943224217 684120666 241828649 366517622 872871794 31699124 262317442 452747779 4176821 279375599 720990354 85393370 413099196 42503529 346234890 514883928 769288056 760134427 27400420 275575769 204570838 578075007 123433392 242483234 158531410 223409009 70429843 172748879 127801029 204819182 415852319 762313880 680129254 507523215 706449982 490408918 982384289 445850754 428152732 292423829 148642599 569593040 502239000 744140787 947922674 543253951 360450489 592280157 828094834 904663152 857654040 679634064 535902814 339905131 88110421 218854144 965029312 671744210 519408078 136792199 372683250 404162378 436481217 275355626 525139582 698593307 290939955 200108834 782572935 770275747 601229931 156186746 419049350 351134236 394893203 234698284 503644782 358205816 706771835 276385040 833965098 837560187 916548660 487468330 466600770 745398794 836983763 229880398 738721363 24226553 526028660 201477831 179376188 23047272 26056724 929573788 147807983 517649483 506104486 468879405 219494700 515326730 307529341 963826485 764704392 150980479 672525269 947848496 283856245 384356073 127975641 477418054 668043961 361750101 308672685 682277594 334059486 972085014 26516792 952237009 782343174 857760244 30810831 988005976 439562747 349507951 973477166 918589015 963617437 187261696 463460387 333247086 155343128 409214073 615584492 469810129 39631247 975961891 90577785 166449676 172746685 81180895 712218288 970933290 896269487 567051483 722047553 378497556 353422534 624738492 353909564 857765592 456128177 888605368 823787687 880533806 389105982 821524900 397431172 294558592 239705277 997250503 493013164 545867875 879980550 404829686 823072473 449150371 461896381 556675954 179897748 675187592 627144852 985236919 85289145 369190355 160014970 191603467 453228463 33662176 746296791 366066071 959877305 684932421 37409458 285523780 63378112 795832502 984580405 953790551 766503035 203127949 183674973 353868704 813699058 600984394 92088499 920826021 987724088 16660644 398590383 15187689 622013111 171671357 701953456 663819006 590298194 710286119 638533565 190613983 901206612 756429989 132937882 921828967 292473977 610767986 482342930 790331649 392041609 273486372 168118025 455783171 73478465 81391779 421761014 506578279 549544215 575129813 830895053 332451537 820065586 718427417 720651777 852058903 818229669 343535654 871112504 595640546 755644046 881052604 290952266 873863308 611822470 87189903 939247985 563337978 81696114 923404956 287781200 505949257 58165436 102861703 612685344 83624424 701418209 30423284 238429298 390872093 374896747 362090091 882862369 51722700 639889635 154691778 277836143 672649610 201663340 446304894 864610141 196022684 546908202 863812981 743676882 676361535 807953094 710938283 697013379 232529636 446387476 859291011 33468426 960488474 896782504 403837258 164107355 738139862 814628487 742220536 465992931 106439986 394993955 911469977 517228163 169999272 721763621 989773614 473116262 398928819 169305828 691350126 278526813 25977757 8737166 500829038 503687652 959753110 605504547 274296729 241917357 152205022 666088625 311943708 97908146 27215177 809694801 171271093 942006989 882288933 531743021 909762731 637684305 320980046 824616065 305951217 811878692 200167623 466104837 437316081 350499883 59798918 58055259 232251605 114658952 266676123 381693849 437766418 943294413 146489193 389193569 979806126 61044674 852754189 55227146 36076818 440606390 208050105 617703287 615575948 294155518 620837643 345768307 644705840 222294150 223208792 190793240 522684186 850831325 258270591 168144628 107904550 690635885 881823227 700266641 620378171 815677515 203464673 89847582 513882492 814680886 215103673 97741041 260122985 753386933 381301360 689978966 27403237 938313266 255781718 835643084 383610792 137159246 915373433 233474331 631424149 569253249 717592729 381927490 938477454 871841890 306555447 870319776 744237348 970918012 556081127 796601208 69161925 570804529 158105673 333286466 43727596 420807125 947919099 608111493 206635510 255506873 82055079 676576569 819058365 551508504 684272573 892253593 877371129 246889265 434787216 574293654 657771900 385666142 442130349 305592378 534620861 18536664 949544299 155481907 654170952 470053888 737829579 477491313 461821518 141639582 118855294 730687725 118181102 991793953 562253245 900530935 263496799 376318914 893756471 327166711 463685026 892551286 688237822 852839314 931515282 304956034 451307321 169322312 569970941 745213113 338723644 282418826 32428199 98683534 788259413 713371019 937095853 958922587 125832279 449458946 867909728 875922718 218007450 433317178 551774290 78256915 107167549 679336177 476318794 515183823 647266205 81247566 71430969 434979448 529120630 571960081 376311133 395241168 370366065 12884484 495596161 401576563 835576226 829238360 702014037 634187935 491240302 80579862 833789289 940464113 885801201 623087710 953709853 168830447 720845235 441597249 961751644 904876631 737632303 195581676 513503653 337671531 797622450 506121686 579266164 183793217 16692664 874360309 225689005 842831701 636429662 450765173 95631667 656644704 25972737 797763303 326444044 647585021 759212077 541188267 388426422 889699512 917072889 633584612 799223521 558049160 918665373 735018644 49880588 753118416 112648330 981874703 908538941 103080023 309259933 712945262 857065938 810828195 171109148 517564485 513052720 650471332 543483286 734903009 839282468 184956192 988481864 466318487 801255533 895487686 351888082 778336408 721368501 419634123 202754044 916701262 646092065 297707714 916771504 720711092 859200520 487912318 816912318 754364332 439765580 869233353 608368770 552308623 39758538 949838956 41138374 280464073 104152487 319132679 743251714 548613136 916880549 526138702 649262986 294790035 957148643 437606460 839696177 224449111 904882232 740862884 84636359 441132325 468236456 969848484 902575221 797939917 669513421 966362962 597838840 767906088 685359824 354534639 18521763 552254865 976322117 50805760 320597492 151915472 18665048 68471985 247556512 240884459 191119621 786478218 279125055 292632771 250431698 252776323 29118201 259130132 287474164 998364086 366458633 75386629 693088165 415012017 646965167 258445202 187157171 863385574 7456514 937135606 995449900 938787532 340135975 241679837 516301230 973762169 977052593 797360965 635925853 270094759 868114775 178070770 947790616 588901062 460288759 568919956 180988787 208688360 769001867 678976718 132160701 866774535 652111394 508507983 880578216 460843082 241810932 308774330 123848142 777166055 739189758 208531624 545391507 43850492 830718705 480118087 990103465 822412413 431700053 598096062 858952502 753569070 863511307 649102472 206695052 498088838 229365277 238729868 726614924 113158173 575745880 113328387 671527661 337397233 80880234 162457601 386310883 488817856 507834160 299134765 632642653 347972691 988605670 719909067 720366621 320645445 93176622 101994320 94853427 550232707 533956309 789527805 574428858 623802986 807780972 446760249 757655023 281967776 230779299 734575170 422931257 342911248 546488943 784064168 932873812 651282211 238766985 756624090 897935669 926071873 129985886 244495600 8366210 52826631 691585136 563099039 505894416 61607645 169725763 321066634 235297510 440823122 205805971 480721611 632181478 806287880 868074091 763322996 544665716 808224920 100161878 2417892 272591281 438999372 129149893 256924552 753898782 312137334 907673312 283969075 533842992 687475706 680173817 618731684 4753125 369892877 422351252 146639 761554626 296122790 946904016 735632603 393907525 536440147 582492615 628795031 693969403 584644748 753948444 545692846 996832756 910297669 285651494 994887712 250560933 545757016 74687463 768384294 421131504 924021500 240247265 908273760 715808460 180914232 717224808 270510575 969508685 383787243 674552968 666518989 931192230 746284867 84894516 1758457 359337948 482770620 232041558 264283564 213193842 378494426 758131161 931442389 116877029 619149563 630638686 973832124 562861978 116273291 197837380 647120231 967736069 455479488 253765229 601756092 302347741 225838738 8900605 872591474 991473475 425005795 101262859 408899381 244152867 974867715 168931485 220599207 287811157 745351540 438311693 814885974 42853370 530143043 284202513 622528875 889697644 608470515 277401127 205969995 929907055 664763769 652144469 172147829 170284615 74930621 225704143 769671963 987677038 765855062 834544502 380265585 420774048 552056164 156125664 408997786 640071060 216844509 550671252 552725527 724817140 162001689 254426051 473479233 595695479 241821173 102064734 397140586 391898426 604364040 766503365 45160629 568986427 683095311 759565467 171480504 301905234 565619269 113300761 762461842 755986145 139499590 545936806 265610584 638017824 681406991 745875096 15546291 207437395 164084158 889994118 335720600 906697067 715340417 550412826 930893244 344639474 270514794 366650004 882538673 895969585 510484235 190218681 697745052 769432425 862600213 358907372 602538148 2488647 8588329 125066242 340486108 952143112 926225984 337170582 846664362 419868407 567930820 639018583 582784629 475203377 312694419 208378955 796986497 233771863 524652431 167403276 309289609 488827396 900796437 939784859 965329890 633463663 154672428 727975242 772291967 83058145 467220911 88252210 12855624 791281313 490731739 580620446 9733104 603312526 645545531 687080634 546081692 294628405 616194509 639204050 422670389 998320091 322784244 425000531 2784791 556612098 376970561 171135993 557211927 736433 630673488 677563269 27513668 789018631 189491431 324959241 585325685 256596388 335172449 812830801 568645607 347621768 295604659 337669874 546396811 969482955 847104581 728857215 871902800 263003264 940224634 939005522 63308033 580308428 948609651 441241817 986539038 894797666 862083986 360709924 431161885 577692740 647700122 778160689 332069842 328957660 50399374 834748856 509163591 147453918 780602479 11062831 316330272 148586404 917372407 570392520 919140450 214476961 772788528 396343350 794397745 313313719 441960314 54203737 950621898 840452693 451087153 29636895 516394520 794946889 210036869 797974172 276479023 257807631 852164428 24379127 830237807 972223545 75219813 339593269 22936777 138554486 365095420 846808851 108771135 573255494 444843324 491955133 431918337 374384838 77862791 12846130 347727545 357947797 447789252 940819534 753999999 404299218 280147175 942337091 370687665 441934183 912916700 344045730 471888826 133487201 123816299 431099624 777667373 191073761 841477291 709870270 413283583 240586965 781753856 106006267 113092150 688038694 354186175 275306085 179076261 71296367 817345479 454940845 494833320 889564646 399639872 512432530 735950431 463638075 593748939 12370842 267220314 861552965 170753136 542690614 334670521 972028009 701055747 596263959 229074545 59118650 601741807 288408167 336693704 970151978 762055952 908384731 409422322 637664870 249574704 759204140 593792691 740823278 317989226 517709078 676829227 831642511 101068652 637623509 32277371 423221753 532010189 117004181 690679990 459775827 153728670 436408770 242009947 740867122 938566219 524734241 298351208 725066210 903825468 185438646 426881733 250782810 597435536 312721316 26914111 390642460 527144193 172269078 481866458 996033344 784451141 855498000 7955985 657043010 526887300 487085038 100280943 878770082 417409833 64781148 955616268 717681781 134545963 583408336 877205741 432545079 62732171 821143328 735021657 802846862 881613501 359833517 844454893 428218071 681148935 461434264 669050834 826948600 793225349 789989893 625716658 312240320 396429169 344926572 812461321 750821926 790907830 115685931 322533189 109612529 134961869 437541018 271787130 757055466 243374463 937081108 441707236 224683771 194228143 76204997 806338836 603326201 608303563 925552304 176520577 600081144 691484343 378419406 742179615 578816654 448114042 349970541 327107532 499429129 58452124 649968878 279074850 650774864 49192347 102949695 20379168 343360319 318802063 222345306 792778650 679146933 598125750 770573907 689651013 3502676 576724573 882761402 261115116 809897726 381241119 328016374 719699737 826330040 388755851 228048557 83551454 229040041 338693379 479627912 774393293 490329450 403116946 406188263 37683322 852622631 439153039 739526539 629343253 861469508 944603335 89532997 151727722 598271021 835557401 119298054 807748655 641522173 239497139 76451621 822490923 53593892 677522145 67057746 198003957 225857689 931157436 56452233 613199287 962694169 640651732 754839279 383252475 399640602 205488538 432488934 678657965 318278379 237100712 210925815 626163844 586369286 979762709 176845348 701104033 283528605 196458483 613303754 27996616 664184228 573726271 81274129 699077086 594102675 100394603 826713823 886553680 67173622 595736123 995587742 43128293 100597966 558061452 996909604 809722989 791886283 737999118 900112938 770816694 121939892 945330394 588358523 394736399 519853181 302478222 533022751 814963609 79922523 998944215 594669304 583677229 614170660 920789970 836324062 198554819 209141403 87009292 493822596 704316055 58321437 791080928 865900096 624050523 339398180 528742883 672138304 640915230 904489539 545302090 951385862 543010720 954249985 380929545 766248119 967213177 913991550 333800876 544928171 592331774 657495161 8688431 951159376 888571102 799949572 358731713 956467373 195706057 782770175 946193396 275158221 568802323 427563927 168812104 724014025 680781095 664767038 751655440 543051602 94386288 64148333 968200325 775182531 561603831 488829714 385122524 279896007 542759695 109081196 377463224 286259988 375637377 104796009 892798759 480548531 288336078 584653832 604022464 581688755 796360680 139604723 52861944 587322471 363308661 416160192 106604469 474576274 549614734 551642621 597601385 306764177 207321467 747092023 940748973 293018602 96609941 168304140 425136647 842476381 742437326 806775085 949616722 613821888 489479914 201880951 500793444 757274492 692797720 930616270 856247041 476080217 105562276 188164734 325149085 517643770 960537610 335930278 690285484 577919488 940735433 346714373 861479591 700710054 943599972 951101647 761538714 250141402 889428670 14880994 841280189 552801818 526735095 951551404 488726041 467687099 736036751 868308064 246158440 211865356 481726154 589680584 138263905 665939244 156725022 934075651 135039072 153639244 718203720 460304954 192894641 19576306 28685163 21737679 449654784 490413311 958705725 218629926 882851797 472920965 242048317 632263757 8990426 275091417 139573864 66269839 563828362 718205019 855714343 725510759 172359664 910921478 726713194 555844194 367277739 856550035 711982506 191806325 675297148 139685037 135403830 962136721 826869443 266369087 479999999 731466100 37808100 873599820 211504110 992361264 95274554 390996697 589051177 290928988 292336252 866650008 221798954 468071435 745041891 323309148 787458477 429342910 263264751 147483598 56214051 406134156 702382158 904521436 521753836 220522852 979906470 205043266 376776156 905003664 616885133 961842584 952052691 741498140 681485219 891963132 489241224 205774770 940461187 410213629 165846826 206157058 759113627 848652826 233813753 619053233 540699662 929332035 606621215 712079322 7764751 47054245 80535862 476130356 943457227 254986895 158220128 961122464 601691812 752059381 578394399 93468180 442701697 325093467 162403513 12651731 971021830 719296879 209820735 179003398 326542188 33509117 437422328 621070398 84095763 980476503 471268842 145012267 496525176 948260983 497990343 390375859 370104362 373565690 842509235 441807546 455481706 849576645 926739006 24677994 377353239 196513131 639556003 53184280 948315486 720354756 214490359 583342900 587639113 502123935 153927034 165055049 953581969 945069618 316636719 914380885 841431804 513402370 987484137 171873315 901240823 375640405 815060555 484909826 576666597 930273789 209600196 27747497 788434020 77986627 372099813 288730022 689988306 787645574 883711488 581161642 170791296 58563781 653971985 677259178 934095906 42560621 190467476 356353186 816952909 214113540 979356764 924886476 14994365 804770187 737385824 42047803 169240673 146696510 307823676 905972997 962982593 145455631 504457744 535046291 110287115 600262 237451667 446431178 701281563 439121125 260112013 469378120 868841171 477347442 784387307 617958434 639964957 981991626 63527553 80315298 971571257 855551003 126667934 802178095 647805398 96084090 209102586 898142298 389216763 714868535 583518419 653500621 71865064 297767294 965097487 75142031 91921581 509306271 396718285 625292345 637780286 934551845 831128256 542523193 277266975 215275156 208927560 220036966 981746474 378270222 78784326 698678065 267438758 178945752 346964467 665907217 947509906 540968291 397727989 679923188 345372362 410237083 524967466 737113146 59626408 471330541 794905702 730287790 48138965 88308106 518074255 750515382 515756488 453916484 512786248 932825723 757491712 32939745 287707226 810010098 668201952 765493401 932673419 968159106 221504506 502983180 612110399 244194843 803823346 961560395 925102743 757772664 386004949 630382166 518242545 614633449 253324456 26224516 795699258 348386187 837793207 432818133 56079128 210356475 84459800 927003106 102836645 765351396 301312306 436553117 286702911 885799823 470850457 947681771 878394033 210247259 961329379 762036303 746259734 767951772 441910452 741754883 982121674 15095344 39670523 855692749 660220957 459119399 793012077 270246159 382252206 434293950 937359323 846786891 403861302 676188329 612208656 335886357 171676643 488344406 604548413 411465634 171827370 909063417 670349024 470615651 349378844 237949248 212434304 63497548 617178021 940215230 6111925 641070559 39346896 159597421 23727402 665816646 621677502 815004846 912465368 89109415 808588784 559560954 138244206 101471197 959318906 177271065 128465134 371443016 399204703 775925339 514075415 104632376 268611949 648092121 839173078 397969680 381809526 921192561 474014636 614281151 481399699 960238944 221600166 867427704 873859582 975143105 979150457 775976462 837471910 429457464 70332608 235844656 901777082 675007904 164690221 949072046 293739792 136758945 827107719 993605579 260050433 380388241 929135198 210734068 266156598 704008906 532338778 318999912 828400642 969110089 936334447 157538513 569858653 976051401 5557611 100706993 654087547 551351113 318600511 540401195 600893209 710421619 536682059 970965619 86326542 857288938 77080758 873386200 542540640 967231782 209354665 872146113 444512909 620300019 168044975 619707193 250085741 569270247 393887278 12802999 62270004 964067316 176527797 998960301 232712153 375410362 658280103 63858014 350943172 671170602 906041115 890346399 253533032 248133150 740428734 616720503 938596117 789770552 180056035 563809561 555847865 271341642 296051187 878131860 188720468 264837708 24492698 838499167 918695235 832450814 528944649 330632422 611988623 395699359 591281075 410890356 107770475 329086473 928491786 253387683 317681812 87292174 59441412 53851334 49473564 565273848 255332286 220107597 853509991 875156784 540291481 308583105 685076690 742242987 570612360 613056488 816217111 807688005 527493033 293844955 307685028 156209552 820218073 469936645 332542172 716416273 885267315 181603539 149492090 279436672 425535077 676138214 81368399 930788140 30048595 855339719 587459081 415333210 809042525 129406382 261287031 662997604 109227572 26927349 857435638 461306684 693708990 574763469 875572191 848031528 612804446 842667806 775887593 390302209 641367022 577232695 576569405 89056726 981187396 404453480 115386061 587035701 524553743 451180049 803924908 146564332 322896431 967514899 205301410 761573397 180453493 76576946 343867716 827591720 331659941 535046956 808235723 62230996 261573652 559860549 202191898 588796271 455563625 304261103 519069785 368691639 378058352 522638874 467626283 567197677 530980722 440434189 849204482 506540118 395591659 333061986 169875425 630228615 459204874 123987155 260298641 833269177 388445944 273467057 410917662 214958654 585174061 163511307 374242827 426838146 429275925 943917323 584485274 827128079 443260589 20513814 489177300 858450282 441312531 30714223 999125775 494337508 620441409 417719715 560633088 128950051 841335241 633155265 32795163 616215686 907912875 749725664 843380449 745309831 575285879 526328409 546822812 841175153 210892421 818167327 351548987 118923966 703810418 443555136 767012724 492121617 96077655 970209976 765765697 804461653 815472922 382185382 572965080 96691439 273443741 954354213 543412682 656011152 731018534 128967223 575458106 785571246 88829899 553554634 935124010 90541083 915579591 956525982 193989751 571496064 234065361 564468293 879266363 314885817 301384803 377807485 720154691 180826315 551054700 647250396 46641287 877094783 162075642 513085255 531338740 240183291 171626374 612617851 250146196 877744285 192369890 860979287 662661113 235405118 979838344 620897464 755881541 792381193 316560186 210502326 855026192 78128651 102897979 660963664 877737786 512240551 608303629 796380096 43221537 184868689 41514087 269344558 954017647 716381084 148562388 161337304 803996872 249474116 900303998 664562864 530511582 580034741 923343581 889701734 63543049 863586112 217087254 203158037 122844428 774762292 597830358 238168582 4347056 492813810 803275035 848497449 425619000 8031693 674592362 329632936 434479656 5178201 664549482 264936156 519396263 463148075 696510973 250893554 825263199 260181141 820764422 599579673 57885281 856856135 72967422 790833996 140793407 57696159 591797100 696447189 226974224 87109510 354972583 771718134 439419899 915935736 701803776 446196163 468823738 408409598 29143412 706572489 208284457 661485073 499239783 295867658 240754335 948073948 194750452 906606712 645507286 489463584 97246573 907934827 796084204 709285033 507252696 679954880 178411177 410489557 521894211 355235851 788099910 974398326 383651627 164359269 299969656 809627290 916581456 359307395 854421435 26610233 435676218 725667649 748018464 592292351 35298307 191902185 510777062 750782209 79895222 723464750 421557473 212126046 738114906 61185282 427603958 964462527 522486192 984734755 324226477 419853315 182809505 236051423 716545668 635913407 60926128 802954894 483648048 698112519 21314967 424704612 194904117 725304622 198447874 717045524 203272397 593118359 573350355 694949929 711267121 720107241 400334514 794978901 353219878 325254110 320649683 919102177 757380552 588998968 178527122 911328023 751832076 622700526 77809017 415828912 23954992 581593554 215687525 277024216 677290328 69452115 141214476 462520288 998905139 718310792 824114343 508320133 909886141 14313899 533127094 509298931 204240274 46067832 795700928 921497179 684172934 930364100 376332091 959028430 42215542 967791498 32667136 114806647 510827024 682552193 248239206 479113200 234538591 118783100 637593950 662539315 41911414 800915231 320277400 100586815 513880165 30147952 88490086 495847616 148808908 505235208 688836568 609993537 861260127 349383294 499632875 721406154 332447078 889077931 433725814 96008988 471378951 263136886 439418182 522278195 235998541 470400905 567408081 764570312 551460459 755461674 108770912 658399265 100854113 854728532 320026147 278097947 317500281 980134544 100429038 176149171 882430674 788062554 774287826 444627162 25344831 947329910 203363715 105524453 490573332 930076460 468906043 581522753 719430621 796810907 21487013 601089564 269929078 620829258 943695032 743675088 690177827 995471226 406659071 752460469 999958102 807711292 984669208 98270725 656055246 104340924 574020522 301409063 957760595 462980821 533846506 712284829 802590067 845824588 24766051 140145547 20962841 875630908 168653244 648956656 834612723 50579571 548662981 900532430 971658056 787406854 285136004 275215679 334773073 126527360 671525023 156115477 8538858 276066581 616651487 370923842 580370532 208489564 785130162 206837571 89214450 410839576 9626031 689557292 13210472 657767948 700795267 647656043 515714341 674498297 918357335 721380330 910522165 486248194 494131681 22571701 826954571 803696715 89127144 347791937 986322754 649260749 480240934 438897864 142871518 920658357 882138169 707522960 386739743 179340953 240614327 483786367 316270032 313675023 42418785 824994344 697035536 410681987 117767214 713782143 668213356 144307548 584800774 959548517 348235757 607977471 450703575 437295386 345903658 323095963 671384316 312186100 518736505 553212379 202114523 396147716 746354715 801661107 701776846 866092053 69446230 815880531 988314553 425788719 582699804 556729061 353251942 73261841 37966440 573211324 705441836 90730218 838271354 692133682 227622714 586921759 695115947 285091051 224315675 780810312 154916992 623225576 97901230 54370734 76286042 487835880 899271939 501574999 927156226 470554538 97902424 481441781 995175563 417573784 897082567 867744668 370915755 187208176 780601774 273715300 501077862 821182385 417306106 995744750 610924803 244828576 44557146 943029370 806948243 678898926 345571275 896705432 854956826 940165888 941442966 469153568 509068409 780085407 429000917 181785435 621307762 704560896 36594582 948379477 2370100 571866342 507059526 860970854 534517016 942268588 834665222 350191919 498556850 718662403 605243717 559332822 751590246 71889362 497204058 64079120 192782228 227838656 491871862 574601755 217434336 811274772 309765083 485265418 975510118 11971180 91075291 115086543 155840308 732883345 364740210 386343583 240438307 734192341 457947038 724551054 574527761 432655429 715063780 233431425 277000129 269625020 320403779 392961208 843971144 122366303 221947353 331350411 73244299 196123905 177725625 801150765 890039910 441744725 759144327 538359559 637137171 100542907 44318887 557891139 949173569 6893235 367350521 312977214 622296649 522582570 248719003 223794973 742624355 704888460 755965442 947068112 835919416 41778875 270586836 449440686 901382709 53986538 339696468 962293146 282479092 971542184 716390023 783036892 880737707 183531685 725418853 90563300 435238306 891804708 617852757 846372604 530415323 957702974 724045955 544448891 150612667 71072408 199945889 606977218 448928420 244220505 624627246 168046682 924441780 773834204 810939477 360266333 683562551 941017090 481949647 37954628 582817765 310216192 935290287 929640085 607277859 471066804 675465661 7136558 262989709 105318199 569715784 435212740 240111930 44920352 672835127 118356740 955605215 148465144 661626166 616885041 807911587 961399146 540548893 853906553 351307336 833169878 277158879 707585860 4853223 428077937 515517818 948074934 214574600 515119791 83456132 58650657 192145931 782437460 58854066 74585901 901251627 256369567 267480323 236443603 374417439 452057569 394219365 249624206 327724164 240447095 95886761 156795408 261130094 925698169 308148581 595133347 338001851 18172180 385767130 765683905 593000742 315876260 848774943 665044638 827005032 690827596 429891073 122071918 433936029 259941277 888742455 433894262 975993136 964809235 274190039 286278684 646552336 560039656 431107796 843108537 821331440 980262610 274075843 13584939 115058326 719339456 289534041 255022316 20624612 345762909 419923833 743264081 35416198 794418637 949964172 888211651 909456423 150336957 94784631 277053413 267741021 434172744 314288763 596485381 666176984 29482314 531958089 394942486 546145372 845261227 715956886 874188347 432171702 604385926 61072119 272714717 907668786 491792481 287756732 125958426 574792422 923467735 985206357 786943559 36496722 721709499 472123688 521292874 281870188 29671189 965120514 25364961 788655736 972586002 969047507 175712681 691137586 194131693 910321716 174816798 161356749 977973240 669245109 201150854 278046779 18904209 748917523 172129090 466432336 634260857 665559493 229573406 122973180 355808531 811886523 987170919 656371509 404340276 1731800 306178864 931433727 594887661 555250146 395961807 802311305 21747606 65762742 719355781 343795711 120512153 819268188 672572572 464062624 245177344 841126605 273031937 592528948 525093974 25672545 166871540 767475916 799218052 471975036 739927638 903161152 861789356 986772555 461332840 852968526 524010323 285561962 218070974 274065812 588921764 44700036 901784462 587389757 580908552 415508207 822596513 630035888 585369050 514773976 619113389 70500784 50017524 562728434 571446522 976376053 136429586 117022664 849024023 441965788 951572281 790626584 859285790 684404433 108809498 254555367 298935071 404277005 295031786 422914288 906505826 79114671 113012214 418141056 491573515 65218817 618234588 245280270 953341372 343885715 286450668 915082507 971716510 558238579 87344012 636027391 847044229 490362226 905530840 619560528 246536770 357077576 176973629 764172624 432059528 567156761 174481539 252474741 76240439 54949178 515735348 797045294 523632584 237979929 255466420 621360745 445692802 922500634 227480855 777515870 613028326 870274179 961345537 76585102 680793303 887332554 304111534 830665251 399649866 814872969 60246056 641378097 977366226 207070509 324292406 168062392 3018175 767726361 926464872 701867632 624777480 435806954 72657674 626245388 675261473 185492802 617437605 169632198 390484723 601067533 355412450 994594400 65834027 325137610 676812766 541332556 324151528 944305748 57273468 995631234 170872072 822727480 685124442 543825263 850006790 862024756 941042427 125674692 473474391 881272057 121223753 94921554 364736011 331534504 901190710 423229820 655088137 311472290 993946497 828024614 97152296 255094434 204842235 80195558 154610912 167878213 944461299 291724708 246440578 352746396 143944317 823987644 263194088 307865360 541589495 985200585 484249486 754314800 907373310 299820419 59742984 50371087 801388920 661401159 455001457 879496155 288524282 936794322 395321515 104329722 417421869 412361483 56474545 430769897 729202455 672420603 47084672 511723231 683983495 596516351 126839549 525731577 976585291 43198156 340305321 372076742 635098661 83972021 876963517 639481065 85622456 629023381 850271472 565725114 133058842 17975368 272639628 154957599 235986629 270101834 800844290 263455532 372865842 466564470 705912751 340172025 574386941 937788682 505161285 657850874 372281347 740493621 130534362 151035143 166889827 50942442 67237287 258405162 673692957 88644762 641374464 235082525 582281210 267905835 431783702 919188441 224782136 333673881 578047521 323331809 553517275 737620998 862051225 568490554 330096483 188170754 591146384 634717970 284261021 987726567 167037265 983524769 471845177 668331435 643351415 241163871 489768688 824564321 636169399 810833012 966678722 569781906 556927780 931964138 51216665 416267459 874263186 231463738 455689953 470786935 578826794 30266872 750016421 453796768 240124104 205660568 91339776 107230241 248913886 604219531 380380447 410244750 512284225 242869459 795123234 324380939 275560262 204344247 863573280 697589201 700287403 99964835 749555135 110259136 890205026 642787821 793307603 109464636 321486648 592876608 10214068 692438724 996575637 490459388 708714863 312675678 995812715 7023420 673659389 422353734 803089358 387639996 677475444 810016714 122550548 2560191 688720750 133926423 568871091 922416201 470726679 555151559 658644248 898496484 815789506 164499700 980822160 987622949 454798137 540218164 872255660 242432949 861545255 626739288 356993546 912635673 659535616 123435991 37665787 668850880 996281239 913495560 537434953 201490838 227365114 561097845 864253123 16388284 192744883 613502809 877769309 778770867 328071716 393590522 740919560 734986759 686908007 22457573 259131655 257254776 688056831 467660108 337773921 879280555 811252794 124439774 850071391 475998916 280257121 695196179 245779491 480927274 734260176 831104683 114825029 13134703 39846262 235356953 654250251 418693646 94091793 794432578 744238928 979995215 957507167 919355330 613461143 400500337 129809635 204464276 687642591 805609061 142481016 502310090 321511331 54685032 947111254 610029703 319073932 308855164 708090980 589124748 743241936 656784468 963395735 189132685 914323086 386239914 353593880 438217737 46204589 930681552 771084097 542358937 301200129 938929714 403087445 944691568 93525164 81906153 941349959 968249207 598123744 530631331 628327727 741246021 556657365 169846509 357991889 460075728 61989658 457940425 614585924 610320648 750282811 862364782 727549487 442871203 511548857 560359997 713426456 581425206 504310273 778501523 691157083 194121027 286062741 568115440 732379531 877449967 950571723 128315111 143689266 883141498 596759539 224139264 964413251 320765619 245505673 784067036 624477123 556173943 55392939 52349272 385461834 968449209 196911714 604939410 951832748 120216914 876027791 269266291 808494688 36949639 847618110 880339845 952273025 564624124 761444052 799461813 549829991 413028491 442529416 847607632 374852241 253848552 525285014 201137918 336147966 210793904 521947674 886425374 864574112 539896713 663367646 180288123 261197054 25767652 788998284 935276431 186004640 762993396 866678673 57944205 988477244 943021835 969487912 967513727 519584322 291431191 481627541 667358155 368061565 900586609 941869667 835145249 10450894 167761206 912484065 383558889 466871572 83528489 440626805 725486597 623378265 212411625 815753883 410886920 423581165 480908476 527696899 654344703 102998116 999780501 816662221 155025774 782219401 943610342 731891379 878785625 375921046 998242314 707928753 758732352 943869265 157546200 393330336 641612632 584626298 235594185 693368145 62665455 683012592 40212179 262672438 195333253 458091515 803360793 736936682 227273583 916987104 890615332 671449667 925370987 780967772 602485085 188447343 728589255 460214367 314620645 275620517 989274835 925306771 761711582 913760270 535757870 936104147 757605812 842368578 792395712 244123129 197716486 877081786 831257011 13194838 423838731 934345146 879526566 216617347 319654894 322155404 137065360 348541961 23407107 225156447 59992431 810339886 313098410 339124783 817508067 153458249 775455744 704045690 908974274 359062500 13729512 845298739 680126426 937199559 156765877 613523291 796669398 812396649 196380301 831755939 949986501 518485265 894110587 550239870 664287758 170561401 354864526 817720350 389878724 906258652 291099280 773751519 123006584 971981326 29295865 757213781 679604100 118094784 952595593 230811513 236853274 675556544 282645650 205643675 511936282 866588710 994774068 36635743 109849512 895510018 344350505 291216967 990609116 693389558 929125680 719908044 324278361 203154106 944301243 866803465 995600145 790207811 443400668 649959945 212190981 256256718 960223838 248215669 230384330 652205342 835323114 960929778 785037874 761809040 285361843 356133415 253502610 901061718 33994992 819642415 105096645 328477477 913759678 336291440 775994968 241370603 600252236 84028980 131472510 683292033 194199432 971744559 559759878 288691334 701532780 251564946 315542602 884880297 849229860 443861781 613456836 239394025 689025885 260153077 461626544 576575746 756108406 360638509 384339454 950820307 886466999 602483134 455676075 869274400 760885465 241532928 638001239 148323085 809427142 135597466 379595749 303576210 569073878 546591295 420504213 674817769 661512990 815426909 747171530 424532300 396365226 861219129 214193484 221649770 438089224 558671258 815139399 861723707 673466154 102278458 520257515 119327056 360684052 539434008 912148678 686094108 5914912 600424732 894126576 291727827 925981089 356946037 142450878 583169373 978883451 338270980 22044308 404254699 703358598 892519032 718057946 78104273 643969084 386278352 121171239 993004998 820067449 378169119 158641980 171089822 231519522 767201332 648814357 186693150 125318661 69772096 769467884 653625190 856593110 758875307 340002799 738247176 802925104 118341723 640928314 872781235 664198491 562862795 302065862 235443498 73787226 977313582 827732470 750790777 193804359 729861951 219599924 764871350 227741532 234022462 902083228 412832760 540973735 322401287 483065907 724408565 891624585 295950179 119625001 718300877 257049928 373446107 805187843 773081275 745653773 737781916 94913574 679067596 361035420 366932293 206747867 445711248 227581424 355922413 321057426 653874075 133611696 722853134 216001635 121525348 594452112 919491764 683771139 821702509 347052297 493516566 949565255 767193337 420148856 111790166 653981797 647566506 668334141 92335017 404020564 160381398 758868354 962612046 954830690 339256155 929802526 917951757 405625748 778099465 283814215 23984805 366162844 428062234 447621719 434224508 659568425 715766852 716148513 974528551 588105990 539494248 473597388 919650064 595877290 53060138 911542767 767034442 795820589 404927963 723770506 242431902 221525064 504606719 791252170 213450371 195835987 956667976 345249934 221070522 663351861 450326680 838505411 649313374 5807725 9904234 712601988 13103632 11006841 936521069 927666691 206170484 41812278 922116477 972154476 950424629 253415371 875212877 863860757 440574917 804968311 226993524 211428232 192385463 299035296 354968887 483920886 76698748 562714386 938715915 807569491 905822520 229831889 472935201 77728534 526425293 652677617 393672002 708888988 110305272 920789228 867008665 795733603 389220029 484815143 315293535 482086626 475878725 741811124 897628006 974139376 746017834 767418856 20295927 181527727 409871322 145639274 898352268 669557197 322785763 835923259 329996759 446347642 762902757 184881332 638186264 555291710 105299796 999270882 592314936 383662 356648215 56163070 951685598 799861268 582664798 167499444 765130176 278779900 57017440 613343533 766420574 563156868 483577125 649279810 446841602 237939582 909643625 853128179 342292185 312412662 792739408 810810737 519033199 441876646 291465967 981897771 666956854 620002457 435539956 147813021 911707001 757486283 600656739 356926784 787162951 815029292 803292637 349783260 377661751 708681839 520859660 201117797 79987048 543962517 192438406 826757130 334366273 643692792 637947522 553539830 525810487 515184282 632273904 305013163 877242749 90702167 643552287 400560338 8374006 213239108 874302598 881899174 399018806 11028493 933526974 771300138 603402084 162488218 533236163 982028762 556066525 158724152 65314252 771125960 970457148 142270286 465707716 66262426 202374004 503818624 436712783 356201392 396154446 478494599 671920822 95841088 236593700 35515135 15614158 260001818 887351307 613859602 155359974 606041102 775215814 897645001 266236877 510797825 668165963 474347909 319099742 520382932 518239534 772437201 892873682 19266295 975116668 334778746 514518749 787997897 39691417 485164696 234474415 725637898 35648532 136798354 601428502 881281078 667847659 303489124 386883368 868449585 457687698 982381903 855951941 158383318 574169397 252795522 972207843 20765829 199547754 972503148 589758303 917447513 881637326 67761073 603987005 810555909 52671162 474607705 14978192 559172092 95139583 195721046 111312791 868750816 171815202 332564474 153715636 952768835 842558814 262986551 252162772 344310892 77221242 247916807 254579923 535113623 184489980 544683733 359680108 44009340 669513917 642388407 192063251 535533015 544268102 947528033 946409318 305593928 676667719 723534202 343979919 100845416 537536695 909033526 934933896 805929420 520678042 747158118 991828340 900048134 557225627 902929475 302842319 686408380 289449357 653592333 94648379 970977933 865594911 904584394 320211034 955421492 999669518 513193095 735824804 346674342 263498866 989094862 489300514 521454665 103937105 391126107 769777077 675484866 921261819 375363540 64136902 158202931 237935768 55613412 311120156 137643170 635866758 401138475 19034396 986569494 724724540 547007363 966458514 999500282 461115860 351824472 274742406 753595576 771547565 75308869 274194517 972028733 473087145 44589286 357613082 821527283 422950079 569651352 201587252 997520262 521279786 404196547 358979015 438546965 159561374 811954770 949767100 81450221 596684686 405567257 169006019 505588384 651028756 764659638 879628498 484333517 702229282 677564405 353047566 31434842 804268305 666160747 30075130 224390273 195489339 357314999 787430915 926253638 672609785 981918855 764492082 682709223 180938247 29668644 865353060 107943692 742220315 671181652 79861580 700598731 679874276 196060820 454100366 844761600 734388910 738189030 698118356 60379818 99014724 809666428 969563682 682970595 618092736 457835725 653243081 539333058 420955475 924829428 127127182 228740937 661885116 369513111 227933025 58881980 721096820 956447659 750764775 105968837 930102749 10246014 239397797 804556471 18981595 545098494 920429744 971209550 294198017 488224366 729480163 440851795 674502701 852651916 812653789 303860312 389388914 394310038 17168793 95109030 814807024 889246126 935617888 548103204 381235391 687392986 227263327 563405788 4512986 198824112 986151827 858737976 37954213 491129890 727827980 528205397 617317666 441135303 486590434 308962258 530093810 674738195 100346760 857238604 337208188 533624522 795360001 282925979 215777680 124687529 819870531 878105065 115792395 779639661 750671634 827226816 474730468 515970780 232585787 101871101 257297264 244660820 604655728 763168177 184814267 749734881 826814226 765734226 507676345 52504150 753193079 198244909 795634183 992295388 324186479 717536272 56172616 527310092 762162567 600121011 489459532 79246471 218498348 118662108 641582524 110130593 138597723 876804574 337247877 869797079 888551159 411586986 343503842 540810019 843780027 139893091 591932983 777508109 543972409 223183479 656352671 876769426 488740782 935343715 397673436 89397850 262305961 908374700 248746546 919556983 574803485 237498085 347117871 692897619 146869910 39163872 276828297 749349757 269663236 274392689 289156065 182802747 453842577 473796673 354778329 782940026 669774014 316528792 840646217 782438180 828632741 631207641 775364959 223809168 303571193 634313311 753801396 543138890 804613073 777371936 537001016 944200512 868810532 8861686 584721597 321168961 609438471 547034525 707490149 518592028 362174256 706924272 158772836 116750717 783965036 468188360 331580776 702700548 97891696 598107649 782512182 294819446 789156447 651358515 443982974 125383280 506323089 35100917 434504071 149951809 831589647 811490917 247150838 24138799 408592546 373002697 7345786 705914959 414658704 648176552 461996578 186532008 226238030 331927948 473468623 621603349 347359140 744591232 631536145 746915050 682324597 389238492 608717603 819636779 902826004 975617604 136133796 839629543 147680003 48968181 26110305 128123270 354370318 926124679 433930667 413440310 808528443 441734519 617467600 332670266 723585679 562448145 351523844 451329456 348072092 482646300 514742875 400200941 699705885 821253210 240905060 158260545 663949251 816249943 326765304 187408620 599287340 28301406 47042739 364553103 308306504 424011392 704286421 843137841 771739226 144776159 282410911 954370741 778739628 196995080 821701689 972495953 317212326 637217612 27878033 351448341 392255552 813603718 334592766 773253310 999263260 989035945 61704809 396189038 563175413 439812158 958463048 167786832 594538474 790273614 893772983 91152678 973260375 383915687 56192482 963579811 570144183 193659644 97738764 889350599 863369024 586503641 433210171 928565301 229644198 933260983 909777236 421439696 503015043 768652036 424294464 58932725 724781614 859129117 335977280 260584917 66804350 748213655 291755150 821560363 870431067 396848354 630194841 444505396 46472840 631788862 459325725 439626894 599308416 194926280 5315109 179830383 565522123 23955396 184975449 657791089 571839928 542654197 788576729 757977011 948555942 339782125 626305864 401737624 701526306 690631847 956051598 881527425 481250921 372452296 243014777 173312288 202053802 670514800 269083164 679133355 628483824 394019110 648242448 62882134 914715810 67101120 777141678 822812454 584739201