5000
308037633 310023119 592395946 760547856 407980994 306897444 172990527 596844464 616733390 832023232 252260547 985968785 285082684 593070315 209349745 347884044 280264297 239291233 999696098 919289055 179265002 346443374 874486203 646709697 159732754 603308901 500845159 898797255 221978276 912535257 214146864 603573737 868824342 426936011 91166300 591778205 676135362 307969298 881120159 507796529 839697012 774059912 288838074 122415864 697656100 826577407 458826432 183251178 154864166 983249153 262063278 424107522 353816412 767493250 420502028 401124897 551127468 407720305 110732887 819023669 473505653 810149816 196473259 581058682 513864017 206843949 323288540 693018875 763267883 927620462 771058545 335682123 238121986 186324404 644410235 813649022 532913341 918246986 706709175 217471326 344950440 200154439 944166613 631322647 576840158 357657147 850036228 310398944 790847338 345738512 796633374 918795437 680811650 828596040 578584616 847746068 749455883 804859871 213656119 545484824 945841438 546625489 303744366 880596728 402010350 958187046 232105275 585216362 718838291 759263783 843588948 492334512 398726260 359863548 468142608 545900370 375224626 395256375 841527101 999778224 718015401 481790820 915315502 697053555 989294839 163817783 487169711 484168324 442531931 463677679 30096355 361523127 590518125 712463165 630055057 887338990 974428909 402164337 120772742 536235200 515382863 207193753 100383060 519558936 997050215 75449785 248008622 287457039 687611757 365782764 737850556 305677328 723562311 885785821 494015168 471172209 179792566 266193705 872133392 320507082 178697138 530185528 39276139 813650648 387808390 294315092 915921783 228560412 458960603 969305866 892715598 168266792 166756231 662644351 532038677 11657319 692978687 725816264 550389355 732222918 522292143 366313207 163727635 781935473 416873626 339678895 821728025 609190959 343052762 404374097 144318636 278461209 769464795 592681038 197999975 862305122 530464860 857887762 624218339 248258836 242008547 318449747 737698698 265393579 383391841 422856714 558223834 564723837 193915173 60855816 510702603 846407474 208437018 811250642 67525388 230099564 286909714 242224868 266358906 108293084 141381975 67942176 713563960 910301992 903170106 61438733 810166454 149164077 23624795 137096714 623400167 913063182 738893826 52400156 386635059 660530267 482867722 518466276 547189793 443936464 495353096 728758445 8938510 502938145 400493119 258856775 749677044 74604057 513814113 969043740 188846810 911531100 453324565 612669901 66355838 247110090 559046683 215619747 498980821 422810927 128378609 301698579 679941549 722827754 199685566 250042804 72517788 81708447 63460940 208173513 99434058 377504743 300132867 874192799 311457048 680821415 818045738 897589435 746666488 549479929 953867678 751436060 909349739 691779063 757502770 475402000 818329380 232640697 533844583 337983233 320843816 320283540 968785700 189687080 562996200 357473722 865202825 75330435 379759698 845041033 624740125 319020145 968134823 -327627 697295481 253454306 47928101 188431398 551086976 134128126 684671172 748702298 741476304 224180773 822814452 162552001 251997307 601982496 839525544 471254983 484520526 710116930 13551107 987372935 129333704 844984273 359057203 140653061 677541149 75035816 806821236 941150360 348384298 483738535 934582322 866023469 341051416 785039850 721124726 328760141 583402826 409545629 920184096 598570097 50721443 12479207 342368693 801394562 121966225 676972490 820262741 151269654 288109857 731240481 390243326 405386146 69437226 436004306 248930026 65935169 635663913 406466433 734742139 169135322 762256 553593552 917464881 255988902 777132477 238754048 98979425 93304080 777155859 927366967 551621795 96641139 331961543 37318099 475780171 438718490 637117399 684580898 706341773 849639873 735813485 114099782 200332699 211034370 398064849 225390511 68682616 25182648 518834975 594960027 180503479 138621636 892600998 931109816 855132025 846578478 974262451 749561662 269562516 964318572 729770055 596716021 885169065 887882137 641264380 585114987 631625558 573075101 424380153 877279898 989740753 522727801 729979108 562839935 728970198 406540970 649624133 405158170 594987337 492091500 769539794 570937513 426840547 165296138 600643174 547867707 773160246 325182344 388334270 601999377 137400766 846676339 987063800 439759272 808773223 948461794 372639579 925884286 145217006 319451373 797781393 161960408 413996728 513574971 72565987 592438975 681837121 438631956 251932256 704900655 882741769 444619181 558490175 458191133 779657672 878828931 363433696 178440008 101661959 243080422 611070705 636765845 30525399 418189634 703472934 180278318 764504428 455918879 393881501 594356653 287360593 42302328 282217561 244322789 316505395 820804363 965999567 725098429 943502982 946436612 514473456 10456225 375561047 102350604 16119484 322948507 583039562 441020907 846654324 405207481 820270257 193241130 15188867 99769465 573251346 228287090 107356424 775233312 953774687 416319331 800520037 62824195 278767245 326755216 600831016 377418605 984328631 11442589 884014083 797159443 331140538 699473753 238867905 252247706 155020822 340336271 61299243 315662544 412711973 278992268 610256922 14745678 1808351 158418734 175553751 937381719 329902383 362242462 237785073 174110735 419815868 949468173 671392693 637914703 572017046 1871554 987308024 248940984 321256116 212833115 101342951 203172471 396560815 188661616 824393524 349564522 892333193 954788049 717137845 256257090 184358562 580316910 101420693 899149214 88394032 497215952 986087280 337683898 489928607 424512775 507080361 841653084 804113008 925119381 937785420 410498053 8902046 801019071 857305407 572801303 809381211 450504289 419627492 997339449 655600356 703308339 168371382 226051256 870039353 107709915 891092348 225774873 134562437 800734971 126517190 107699800 874111810 640829743 222957259 149912478 434212582 177248784 275784753 385057755 22725007 222248510 518349835 687715885 822329375 472511585 933233430 962513455 564392231 895182898 557958421 671723434 100167377 681761350 209615878 376644552 684585197 838881900 853657936 411797826 975845294 212038691 728877514 91909284 719438227 644140392 894815729 749319083 202638510 74775098 366521408 545376946 555973383 357356478 895298328 932981923 505749518 222504984 700061808 143499733 918877523 989260568 646496430 320297589 850716011 88343573 299564697 516603064 382131654 385373127 60156847 673230079 441563117 457360570 754135174 603224616 335293370 646022479 680870210 599725593 805223702 747137561 4425098 389889702 342238931 991199 128129251 682568381 312543834 489065013 882705875 771793970 243181916 206178246 954658099 993183319 535172759 630998606 865848679 929968378 121410014 588189054 626449406 870347359 372526338 797215030 762785902 480212842 891379682 827739959 150045511 93517170 39218694 848415613 24126528 467247885 494621988 901922745 547086398 751780964 860276156 906318696 858155465 527157373 721373583 488722844 190002359 818906628 747821294 980191506 972081564 271558042 762390297 425405157 824963040 773226409 131746640 471124793 377982209 900912513 371042948 256455586 608212299 947349769 870773192 139038017 679106711 29713175 123320111 87907085 7100008 260809644 844630611 734948030 118880637 344940998 474048206 632996245 782705054 253371894 787658337 205102272 561460353 178601170 851824146 929185096 588268265 489099906 559009758 991310493 33274792 864998617 785916623 565564809 653922990 600243979 980933843 667857136 963873310 430518856 956910493 781880814 317143901 796152184 56748211 320972488 451672414 685976850 678795597 22657665 958822752 374040162 564165669 321286550 782120221 480744113 161380732 965130218 945544052 419390667 539556169 159774141 737494079 454186752 110842500 599690077 84319464 186246698 256500206 955654678 991341508 973792870 551000434 422021962 129790210 336159404 527136181 522117608 755507117 728647727 933438696 822303222 363486070 849697044 858036952 603604737 223785646 631129818 748534305 710470881 80180290 514291314 270411788 862473154 301120711 450474611 407990522 284602176 252205177 202701654 139476229 832641880 203820322 468810343 458724076 832191741 866978581 273526828 440773377 117021884 737758025 697457471 781512834 714542046 164999256 619976148 569523822 120048922 914480895 737551895 850233040 829616429 664053129 608215953 179642767 139010611 328643057 671892808 321923421 171952181 435697416 774784459 84090455 393604771 725528522 978579946 767080440 304455480 94199972 510586018 312737888 214814752 242575317 777967274 715118460 538378553 3677933 141332854 215523205 13922541 668298841 947856847 643985537 956252606 6432949 918595657 884885132 212169776 15809514 577912605 808516059 290359028 188393328 476661866 588487588 795684074 797013762 183465821 4183139 315813014 307333986 127222122 193301324 801181016 372069235 177263582 974533933 890255151 230025232 132883197 276228918 216327083 673098806 990541395 36192980 363522603 42685613 979172821 207905088 719495099 358608665 259622639 457170474 365307219 511358391 595195076 961624095 660378496 835722785 434647329 835633842 499455256 993928085 531916686 785023956 17965812 429344885 492752439 669113608 139662158 296470717 755989849 489629536 780020880 56677008 437035004 70661531 869093988 645071177 473441073 837180947 244269989 85451456 168256358 399512485 455832767 690923513 900347516 177110170 179125680 971726070 214046487 451328713 157905132 500485094 887230371 92632684 821472217 838168292 230369939 46717524 145488033 866499152 369007092 817814862 902781210 427787265 720969442 86395104 829101654 337342790 518513729 238157913 629589147 461066371 270216333 826268519 204213518 216426495 239532570 790213080 963235867 519404207 466848915 928113113 541147542 405615818 21557613 56559452 971004997 126649148 678862978 920410533 488105258 156637954 334449337 577655382 768632003 177209102 761847573 152972717 177291301 820062529 485657601 710177151 78292489 795637762 732924559 66665132 6838201 869254141 457099923 91427845 717428997 492307597 365304659 524356871 729158574 544144936 497223064 442181703 775618409 456706401 824229360 435407583 785445758 380347873 756902335 342545086 522601148 487438675 491828512 446742892 121014670 479610847 854115613 800171833 412430681 774956469 65866342 193799173 412932163 258240583 678735561 880591848 933949972 812668150 484286058 351366887 821686812 715982387 442598249 354096424 24096292 802340444 961823872 663663594 970881410 169386285 299025446 561637658 220138228 83614904 78164768 679222580 172468927 108164189 278930764 272073690 521773155 709455816 669508716 772349730 606229471 364567426 533895835 701831352 891793326 457872706 575141337 695798167 282495911 958445086 961916777 455120514 316540537 507891319 861088554 612034551 950799218 197475132 199668730 294770887 437485547 166791412 684422221 297588640 300432449 223042660 886771446 695503328 293586067 248635023 741911503 878917793 158155256 741472499 433227038 964250210 717132429 791092431 210850354 877728199 325882027 467676605 189866967 502429773 733176506 430633782 167067313 563723903 807062833 911465266 43051406 272676376 735466792 810331713 351198495 47153316 42997533 851178959 269117408 608693889 975762477 919084072 541656868 465582888 613877669 577522921 928078024 356725977 513839726 565752014 360361083 648559317 867569247 111257057 133306234 919061031 469889222 677695277 84507130 882823016 66314924 300967463 991427245 406353645 508146211 160240338 335371434 280045741 386246988 360909312 151545697 583779250 843353289 296649667 13471518 259050712 503592557 468350350 548946263 874074101 831928582 18870912 3880405 688634467 261728779 847181512 204555120 87688646 120681651 955242449 431872912 565305869 879573753 232431783 835324225 880146790 374198294 933935880 95079841 287254590 204556925 784772194 409853907 747395302 274780904 792822597 500941946 143000368 490674247 383546202 854158231 909230804 224045035 766268186 260352564 296085279 699877090 525415592 474198669 264845400 623013943 505988569 981802267 285857672 209116554 643603418 595596213 436714950 600523103 735701806 360227 821930230 908059539 487261840 601122885 400965454 457090440 228988675 802182482 393921580 178413926 869442745 528564475 511777758 537279054 207663641 591737309 619316312 98785831 306821136 55417386 134801331 76548351 587528939 274757867 587410940 314949497 712857983 931193563 699365932 412122628 393641101 520717004 314162999 352543779 686363091 545983961 846175294 53006062 88632996 465389208 671261464 784425862 314881699 414311900 879325441 87238814 47537532 802192785 325945025 388115608 784618367 607107962 44544542 630924816 799048773 618982473 239806355 809614513 157962879 632880094 376754363 600493382 250334474 494785719 326794039 432311328 551276418 438667000 154221161 789062509 136238823 721505794 389265957 764755197 497567427 436689251 867212478 748344846 166048595 327876190 611882387 558216645 678226082 146113400 722550772 828761334 338182638 413522216 665660144 625215990 352733444 579290336 741031715 721312723 986279391 484868327 738400956 610806473 337607626 759882866 92590326 428390127 349688779 557229113 852058471 610329531 216296152 515781695 611037890 700786131 622450487 505303354 76864301 638961509 332184442 276356880 704353647 706977842 178905937 718135774 272189169 232190685 483790096 52796906 578297444 600451606 937413239 848860306 224901266 261181924 536844353 84998086 986687406 950833760 680314641 755937437 283938417 688615019 308053695 641322525 475333953 594379908 875509576 951380557 452471012 449598049 453672289 693196505 955081084 146745822 223014495 274516610 125368476 599355988 96185996 903159203 126638240 173202286 80443100 14366935 455516489 320046389 417558422 817212394 876902689 269490763 817304255 906132394 343848148 294242628 574116082 487356878 77183422 391905615 569519746 896327767 458750442 358180490 183386099 442279432 792437607 569609725 662720971 198321842 376134225 323258836 638509331 731343420 318421363 226725904 803226943 968789744 48975476 310272478 561227482 443519087 923568345 163539734 678721322 553631536 376000776 323888977 608487498 836667532 532838115 519911928 205578226 26570500 509446974 957856714 930435142 316778939 414009576 575499769 476780877 688591438 687178739 947725745 186215894 595282020 949768713 127943483 429245367 612746292 479561973 346347569 930839477 296747520 697030967 155669271 709242105 156403490 293836916 16027206 793564548 770394776 390032630 991184241 948391003 800754960 431546242 563124672 386541291 390235411 426972703 12167307 27449478 106977535 972028833 80305630 639229619 985219782 826544655 700060061 714921595 579990860 902241394 698292487 964711581 643748205 6579280 206546212 921170501 125423824 250739500 366633143 240691914 348709222 992720624 800841860 500140090 940993464 342353511 384750746 484126226 279716846 791411934 635060583 509856337 100395309 445452571 362318079 915873038 514596367 370729269 185890525 717739645 4846890 130127375 678894671 797983408 491967763 887787982 306327866 578594226 160002009 265743508 635575678 404628149 5948792 733148432 492661507 817983449 475892718 468343972 654565544 307278059 214989641 437479143 559107223 740698333 226394260 969307949 328049157 450415528 592487793 275849437 79632267 715535833 943927204 203506207 341703410 742855424 63051504 251523509 665542317 775583003 807861538 223967541 284650712 757852314 276042993 279587135 377471601 702861049 185120122 113472298 843987058 545250610 600552474 344789567 837139824 558935069 439195351 603465241 156251374 548966863 119395092 487769559 181568860 366605811 32376406 478495418 220227598 874468432 400828930 20366433 684018128 494762213 8087522 146792602 669748801 840003289 972101606 387475814 489676218 360031710 788395106 471263521 340075914 80742462 544549636 699764619 722045850 922282950 40822211 210756016 937643494 351623327 167738549 64639751 976984686 586348121 4822290 283371713 815486199 872600596 549898254 817366709 552923973 350329486 978966728 501169059 735454268 332416067 311996279 44734617 163180325 751663351 817026942 325873567 682921480 72082286 155673392 468541905 180557223 560231923 700468056 760722827 972480125 758462094 922862183 616472264 891458054 759903698 442142753 737242701 849576915 375186440 42492210 942430645 779767973 176883805 278161421 294975017 628866199 618004324 178514876 985960309 567869896 599227860 508032703 191867708 20148802 269302038 160527486 326957556 314363302 392225134 890183624 118229993 761990332 656789685 903742282 342896130 746341494 244456294 112495259 16029688 189125835 94073071 962870546 212154713 288878579 738796152 649973790 182776981 913568482 36501638 112794190 140614714 832679113 274274455 976548462 735366576 613553736 767634703 597686826 977209239 576983937 344494075 249743855 507102032 2146181 357579611 677631400 740835924 648521924 166857325 774760906 246630737 183378622 16650438 530493336 725693411 113368998 618765314 682288144 490696904 314455016 956712990 73915540 509751218 92513746 246754920 71154626 419121194 485124987 876729461 598879392 842507172 655595814 672007060 327355892 981976542 653448004 437448029 484851878 894484231 120141031 455109404 774822889 567386345 913265386 592098875 920195656 404575007 89386408 255022789 995409419 754101211 258459665 136092674 93837732 836606850 84988569 1589578 272372616 295191947 310098719 798730451 659074409 346060015 911381479 988778347 451896677 707165364 661662931 50899344 539427189 28046520 623041497 132549931 344494979 998305208 17048615 170307515 342772965 527281252 880720811 822982495 288350515 450522133 934213701 705617965 568175770 838787385 974949110 777981398 518978575 401733456 55000166 560026397 379943985 633444159 194821213 250097845 652323876 132706421 317599020 279788284 210945092 923905656 887004493 689979055 374575248 174914678 389390757 562582458 787736794 348511303 942230931 141179294 143325672 362643807 930008931 170836075 68024552 628684765 732660756 5309742 335007209 362939431 319483930 87280 647573432 125650812 867998214 403641776 329396368 552139405 387928786 191347670 503891900 918152452 241534122 303351938 821038902 775556156 479602025 939307725 779212555 70662612 202806637 249160814 974732290 529552901 208077304 209032889 705375580 640788811 235462041 525116696 717744640 384742557 375679595 467925811 287472721 36981327 878992810 599062867 81707327 220025150 933780206 805305358 350780006 680281142 138829029 76830165 386714174 887776927 619247362 943723064 962732151 247618877 644522041 486275561 276502333 483751691 367312427 896755900 469049424 580360082 957756804 607913825 522687905 707753132 105800359 114809479 745874744 72055356 291703242 561967479 435011507 533376183 579564469 208518813 833307469 311025445 73335189 372664041 426959559 916326970 247047604 961117860 957509636 85875359 879292404 964184891 658503150 537023928 797107421 946840964 755077516 404420738 411241564 984434387 675444395 764777353 661143517 35578068 46547808 327978978 963008218 509632419 215400296 284180315 976108375 529070479 964042281 374228705 895243546 479289845 445709112 811443047 339647274 756864380 264921394 41106101 952503210 518574577 424607634 677729147 324421572 433491990 188263682 258446962 946232386 788093440 375914093 565264632 648946101 200897085 677757689 369741141 755786642 4611136 746371554 764412206 133973399 145207857 271968232 278741159 857191686 285784216 277136548 409848211 993046701 654233841 156574417 767640805 774631664 490542167 582230089 452612734 326013397 248783652 36301573 306471084 267238901 887041098 988429104 1861295 583911399 646254408 930278588 796692212 549767744 970756048 398781924 251917442 894566519 2085311 761091114 157327005 758839552 880470093 353340053 596544579 633968177 432604334 834033490 158890089 880227815 552188848 306204367 705180311 311900489 184199695 315397396 151403083 604751792 153310217 720608109 24237255 124669392 874883940 640423298 518604200 694838963 403820517 473084432 536438758 154196914 230789129 364763353 315125326 521973230 188578478 975384224 237581175 741217959 160777134 411194978 798453443 917142859 751109150 835129701 127820230 795230084 441814789 128896016 240014523 521834871 839693454 263278076 278284143 113143953 848172802 620475161 377681779 379429025 381500750 228982209 950714415 470263349 489871940 155535228 229676851 110604693 251166804 878858264 728191840 959821254 277815212 536799718 205018443 934765710 497873551 66325386 214651925 375297653 378114064 537541204 26159719 642909858 828881332 825830479 23841631 282757832 194923212 746174834 349203517 910038568 372880451 219451784 309620599 568372072 371976155 361623480 424428727 855828582 728704156 270629775 164925572 379381513 719305264 829621685 767068600 675661855 217317707 654766075 897069394 159559441 270421983 108650037 358851580 416743662 402641293 647950965 859242227 415991889 559290626 679215453 570692224 529408915 3184563 102920832 794277547 929543760 962770004 538969906 952390355 664867660 227522090 761789227 923502708 297786007 909892719 907140203 277800625 709846847 918908891 52894480 327771143 17426314 7189410 873794143 578919114 92405831 364879215 826573947 732372292 354463472 12637056 5334203 509689231 81397835 182444665 318937907 104697089 876359916 396534055 724786527 681725147 849488343 945623089 550366821 387089235 976164989 755392877 761164962 966137785 671892702 366362991 955203098 954275189 532606082 370646733 517397996 681679638 939188209 820726551 522664554 731751300 75992311 953536858 89884029 190660857 126094039 640894217 266736462 318096167 884110618 874882950 705919688 334548333 316138054 937452241 558866413 988895532 380689177 453695326 369421239 278937328 387148619 938072155 430278089 55660839 690796518 566346867 186531429 971665916 784516530 829857295 168518351 23173876 326408107 210828990 525728258 399492967 872797278 55684725 783315134 293762202 460349464 540111830 572552549 70392102 9015617 551085054 754986592 450893930 832411234 85571086 459447715 387630912 259882791 955540196 664401053 706819328 439827217 723220012 198878856 194580091 654957069 192553553 383597577 105459266 954791098 780775208 379114302 956002237 88541391 64878870 284281488 151978323 905899351 771051604 378916324 928235069 222400650 199587069 771858013 861137741 302060535 535913732 316771139 82667203 1273474 607373885 638778028 573370275 353487670 163941973 756183124 258510149 860342542 805149125 533361811 549503927 430015282 196243860 745801458 31695081 68867028 574871594 699717999 28535172 81217390 50362607 393045052 611484524 42702375 783295579 745061064 296823953 628985482 447932812 665068517 336788299 856585709 544893043 50801040 9063211 240348251 134466899 202327520 486003539 284132323 310946179 560654031 431808259 816602709 407874293 921443286 337901077 307984197 77360139 329964591 876343698 450387553 955588827 369214032 190252914 428500866 412427771 543590398 261070874 738454944 831562730 257793473 128906669 650068976 437663215 701403725 495161090 685468598 213282330 124124757 800100528 964241758 501408311 884250044 754694959 293172786 245564164 463231002 925088622 138857418 990454232 411170678 543634533 729367889 84986020 493893544 525881482 288990570 447089643 681438264 115319046 169403618 120065202 534934798 883307021 806513278 -922730 138191335 981088815 55346732 202907012 733547872 867143460 183593926 632432795 552932115 93458384 15178884 179516146 -257090 6539748 487787264 472161709 534075006 316468453 901118216 321707476 615363478 202504891 193707610 852497869 852360080 44438666 554980491 397946332 371533556 665866384 399125224 765364050 833349593 809416640 91378912 869833523 747970899 120919366 461180615 767864498 138985636 593464733 488322230 951543643 761332350 87498025 445961034 461697654 521389929 648361652 204491771 878824169 337702466 241636079 342783276 436505824 845436198 996571770 110501580 327556851 602365078 34415295 450145308 11936785 573455347 456738358 21998782 231183401 256071992 22733591 958446322 646982437 437633731 204142079 573177245 662761926 354184504 82644417 651691175 403445509 468236117 339265254 707506875 237678270 825431003 940353025 427487731 591242926 183070651 412806816 608555131 705725951 362296743 627230685 307411564 369479820 548081911 590805588 753979901 609525167 116474216 973215704 274615107 982336560 497465800 131012921 207398548 782354466 201398845 604135932 144880474 628986972 877701509 427153668 758908792 144368841 135716390 314781263 175511994 601059645 40678013 302169766 477681563 147969847 852332466 11303153 366020689 772163979 320520742 766582151 95764922 959206580 943768361 325177300 160020326 598293499 249306469 289085852 571090359 11788095 765903976 717695192 312433640 319423609 941638514 954844766 885201301 787395500 181978942 543049000 454874133 21708227 332393513 82563036 710915006 855746253 370095092 747646749 918636257 821443132 21621947 171575308 887204472 746397400 765328416 857559883 400736985 666309695 440485302 902851182 62188170 593452730 600194932 717205827 323606322 337118097 413973948 853609819 655367885 697766268 351085787 420677713 93188117 478916785 457984628 608932763 283295487 887503614 12307227 58716643 115365654 986485385 580762975 528553928 886271083 671694450 308280096 313475782 935143129 537676098 400637626 416458303 603979051 750832682 128389993 432944012 929410467 825703903 197453958 71524622 930434250 661536894 528520730 51856619 266631205 331486548 475083714 915974586 217301208 341022570 698367540 115194881 490453060 198404465 292959923 680916643 286070876 420044677 238200144 71892148 214150082 730501140 926295106 413543555 649129257 988240291 620549005 18007619 172067682 417097323 182161342 745068294 226601580 437186588 148549568 952227989 706485597 948639693 260039920 45711461 279347596 472574457 260061243 468119906 912177958 112297724 866248784 108137212 395009198 905648809 919786263 846488275 597897376 289681686 903754689 202647684 824923291 600550898 271531232 747251167 896498068 380692275 903751799 936129265 373040717 916476688 404094879 262491390 992727982 139609437 917586639 894504962 351094965 420404732 369874041 477561035 344836260 183959914 385954073 236071490 358350597 526400009 159042819 689986023 388223077 292432799 419072816 789576169 249166914 273737522 301505710 36003120 216338751 429244210 958927398 644785668 647621781 577577380 191668157 344818084 953305303 243400426 259453332 249109052 221325407 733123136 508510574 643557967 174171782 485137500 460375588 204577454 169072037 354180730 804058044 950297300 592744987 953865012 392840459 683439328 787006724 905481224 844176518 613387126 169511268 796426904 859334619 128267494 635225461 151412773 606159131 117574967 437324191 305160996 754216094 690286194 229309661 208304811 818717039 418068055 636523119 519140099 697500297 382485963 396401300 182755070 699665698 270758572 197765813 135566842 900725631 23829043 120617343 745920079 41242356 191539556 605356287 587048158 63692682 984155964 651533839 382764535 752838024 210765449 9272451 568028556 467726356 972507550 845210031 457600746 398559545 249916943 445202838 903871563 435529766 935557003 500545586 860026698 848366243 995283053 944188116 531673402 262034121 880415611 737961807 440661179 809545273 692463205 558995112 78965077 633102139 910276040 209068873 882102879 915310622 615628785 982383170 51776653 210550909 497525238 575549592 522009598 62868892 75985944 385535098 612559601 402441658 305657825 488664259 80684190 162397061 149585589 708609510 210096849 349343917 443690116 413520592 211324227 965279712 492273322 229986920 361288638 519347878 696590305 412190610 390278130 259330508 839059379 393845064 153850381 392022760 396197161 50056376 3942287 371416582 775321994 758457580 980546768 42213155 211837377 569316207 799024629 265122679 153237427 964552043 70800869 63413074 990914862 699538409 545979435 719082035 900298327 422152409 419824996 152716398 43698271 430041761 335478339 234114617 362544338 990559790 705714859 710823115 492617992 543934113 893010934 360494642 896613180 503888889 287519843 977793014 659687551 449901640 936105607 559937222 863572239 687885179 636246948 378565119 312153898 995666241 389597214 733673922 591030764 36631139 320420018 845488846 273596718 262006530 45169365 975282088 772717826 312616658 660239290 355678674 368035910 233409331 634560984 836266319 951480298 284797535 819979957 645229569 952251370 582950129 368524973 875691568 84932427 956987061 760843523 683592707 79455107 504952693 599197923 331965024 778280297 904977985 560649609 880201536 729164355 592925988 743055194 989158678 274934602 949079948 528388576 505281832 68808914 660438450 579115016 380479437 354471494 785418930 273769047 705934453 871378507 493355015 323812950 760071773 626625927 621879334 541656629 674254289 457657996 677872309 728069895 793056849 775273553 145143928 328510895 289599622 920895663 6489269 321015321 562619712 617350415 370245803 138173037 485193349 416611714 990233309 223680124 346797034 838428367 367280522 263323676 741446599 309215997 950242464 222207649 316687999 131934408 590585362 416131854 244245399 430708825 690572364 235703367 45902162 373398564 925153519 186829311 874331953 816121199 996337688 135547958 820929451 154490837 323508099 900418096 558825757 919938340 749101789 457602273 231043669 426347563 70471078 321116501 254464298 463397515 116356273 665887863 954238649 85390943 941166227 536475196 469073163 958725858 153150199 643394787 993144630 354625475 807032907 270460464 518119037 948021155 437558270 480834031 637952956 969067777 39929282 254985274 487503356 755592279 67036059 992578613 757913904 450442890 898351872 185361789 411403821 614569497 262184381 858704744 181879002 527596182 436439428 792956030 467309314 677731952 306911152 191966436 299112913 98611472 366555416 581277745 141956587 112004977 55720241 113931367 288836138 881869173 205091585 979262169 910286289 621654618 188149564 715701863 345449785 524057668 331124548 837249499 54294420 441772449 161663021 854589270 207494614 821135524 730465069 995626186 960346514 88512431 75073304 83893257 502112015 277898757 793459738 273824376 436370474 589914970 544792464 106299319 542994889 732466248 836023436 157638889 8338053 685181556 410391887 798785057 788664339 512049712 726804690 640718918 94733671 438434122 533097354 4148871 603921070 979194827 24124101 319666761 366011860 529377682 623630707 865888938 173877986 853292276 67149653 843110989 555402440 899012708 209884848 749338085 240303802 709935450 776306123 544677164 555060006 76641608 417208469 328467121 941495020 388511652 137665060 733120161 927086469 607095946 649486268 266609367 446431679 593295989 781120108 67063354 774556874 400698153 446778407 659054309 56661890 814662487 165754909 66548910 727716172 275357313 148844931 158550832 397991396 768497581 838174882 152241655 733349609 674867046 401032744 329087442 284162838 681828127 322936368 970472701 640590764 178353939 812163291 153852850 309717140 148932225 137341725 11647362 982517527 301704371 915795235 717311030 961507827 254888760 472191431 636750442 941676925 726737599 130287438 558543648 79774560 13918876 435704108 53599422 533309029 742350642 590535301 256787231 762161225 704739248 330815692 793681606 762316478 614386187 434719269 868656694 666475577 626762744 947405327 5808146 -965991 790205054 142139545 734043308 14528926 516747124 590949392 751888049 508735307 360089266 512016186 695482730 878142054 355510626 161836817 762002933 669881231 49915882 214225271 478198974 512361223 101777635 616503935 135118928 769218953 913734423 832622197 765102371 122754697 872708163 742306090 254115337 623040549 539105397 128028005 930714694 461923022 855768678 783989192 712672835 757530481 522802888 314715428 993945441 891678983 693868472 883283214 509418603 377643560 779188386 581841473 353359281 895734465 678100222 826803704 852940774 339394454 208746523 5119833 719174946 386568312 435505669 619997601 574384573 713034871 180765183 655396283 555243917 361135850 995212333 178759177 329081144 161228100 960365852 137393330 4170129 199444209 731762766 258017683 523919775 380195313 772270330 39975363 343084395 422047822 4488949 144488060 371347339 438234457 633427728 897529752 771949156 243991488 521834930 839582306 371426423 388997208 305479667 500969161 447293903 653906734 783017122 344095840 185645460 289870527 568325206 680931345 457674003 36956610 483710110 821269275 380834250 491289532 180037197 143912361 938919969 235372071 897651623 72021502 575832349 644174461 395512202 9441037 380924534 607270390 788078639 94238253 512839323 463122848 494499457 189260152 170114658 732355238 709054668 865702158 111715474 827524734 746663717 675390633 40118182 359877992 638933349 599251860 91432334 181916586 620506693 437405208 65389952 547292144 315168322 1260010 306436875 658745454 684034536 176330108 368084879 990431024 40201405 648592663 207380650 15939598 3825831 768668102 354502985 6614774 993980664 734342856 869792831 634750218 314508786 61032497 542303421 868036277 686587975 493174675 979519637 161746879 935327518 29674610 837315784 539459631 917285586 252419039 474402409 21742200 646095800 33801346 745336207 135272902 40563077 475601296 953250984 197573291 413811152 170204001 258616879 178899205 531605525 342409747 464901452 116393334 283624688 195611664 246762362 596973369 54318479 885992053 829542099 627382181 780119797 224291861 748372301 675654150 883369499 263428430 30169234 609294278 471212308 634312178 166935134 710526095 127231966 648139854 471071984 900170757 315006942 596357936 769288817 946215005 528813500 371558248 767430972 414131759 598418562 922235873 626897224 772193083 87596030 701581718 363093807 687835271 556739116 244142558 199075633 840624004 923485565 429310958 877365711 334128269 588483303 675051211 418280416 505801048 496470381 218708670 324555415 833152185 745215993 690120968 828763597 505788346 524426645 636383979 145194618 452436580 483242131 363470644 793178856 233743925 170294388 647180579 318530704 38825108 179394208 226695505 830490007 362305356 986734110 132646501 303623541 97496828 883090607 962774581 65005105 552715138 825098629 612002533 996412905 751922745 175213827 912945993 876014332 756334008 992403656 903567962 760585083 121283007 385133815 671511305 426572584 226050046 903617029 720421052 806214028 50684383 351557422 177370064 533553359 923155726 181409158 456801699 22686752 439761743 595446251 831418202 154242054 966458221 943181008 121270242 760199642 68235724 540715824 671018153 477997399 272154675 895886956 485188722 474691601 16237074 821561709 616698305 446285568 933684050 45042471 110048089 963152517 547844721 720208533 754360278 799836914 831620174 725592798 856964704 690602797 929253359 209076893 959289201 946209408 379679085 408785007 691157237 148569279 563533220 384989418 49820979 55957298 800355567 426552417 204020385 87894161 807798939 566455853 927529914 12611633 468715047 980119 606722329 191053814 54634964 384252376 652901396 32818521 468794587 343089812 582356777 285405637 455395030 847330188 662705147 8633419 48151345 203457918 918580746 234276953 48988411 855954269 266020035 685529200 164452417 357992660 598425299 773308375 189110225 247704197 583304158 311942999 855484184 559198474 34994573 535979816 573860296 339751523 781366804 70270815 705823741 385722959 444644891 816084107 881737226 892010183 748905759 872883767 780218639 485763290 533699028 615761962 321134409 215327415 762562015 37519764 521223606 547706291 165713330 495967121 178731664 571934343 518517798 695619326 986087735 243404418 258949613 223199123 975489253 742981424 419130907 403303380 990062828 342502782 570797752 577072958 156232377 539046769 638770209 790855469 515161918 510161177 607229302 159864150 90083211 16500710 886962021 790780041 241527531 608313437 141135313 504062041 831989954 96786769 135984233 52780114 554547830 127162758 164322672 922650352 293678105 159001297 52093975 858569314 628471301 206242239 712683513 513574800 787638398 834218070 865373742 882514269 782943250 591090899 53356273 370824063 412709283 619517723 324047082 438792250 142318979 345981330 317051830 490833023 562620334 838938184 975512197 326674380 852402811 673032247 555880873 216377609 23078038 276639640 878044781 305936472 945236536 679851125 508441392 426518677 341066329 180171940 400222084 304010206 926071344 584922923 621574094 320661108 738132880 687785422 60232308 888394282 637568839 413731749 496313428 914962103 834320844 16685661 668954028 112873532 426746424 140327800 851623145 323662014 42473243 781751180 431668326 160916767 888884434 856681414 70066249 536399120 219184912 851746238 267925769 548113745 719163753 985118177 511712581 186919777 461023326 226422004 615674953 30931652 377367460 218611154 716586715 190327897 31464529 218039627 155922811 565853852 28853587 829486178 130978097 356983200 664843088 427485125 803962770 980147380 14200162 785352634 324273532 761726049 209519706 8433583 920186013 128700269 208539605 89376874 860410257 918017806 474523599 290442543 137627116 467130886 629349526 383336346 323317111 40192119 306616769 994272588 935933041 452995075 93442318 774744729 567019067 284513338 827057407 601885746 272153243 407678089 533165598 948580102 539477046 557997357 210906187 579234588 422425190 502870262 355646751 608211906 987679948 671614549 922217391 942687830 385342807 593622401 294113361 406174445 825741001 976870543 816633768 330916690 342609074 538864267 934517328 371852211 885631495 841430203 91333870 193571178 706842895 186537477 430987805 613379648 765959409 211982568 292304463 617622367 554711522 553815168 227156261 450709382 416639280 689476253 629861655 773275906 73677648 563102046 268737706 201081877 851584107 207018338 803614705 899781504 284351349 319454507 492763473 622961841 410455178 106140392 464590141 765957672 622941360 691007605 853651720 8094811 914991793 89854751 637728339 482269147 24182157 739370393 460612300 448366385 130054696 341643961 295252851 497144628 373366868 373022230 825659643 910473089 793599689 472875136 14703152 941995422 541556463 696385290 594996159 85957343 441748133 550668956 285593728 107282013 818176295 649129011 463236785 392540363 288382224 290932788 679479025 587430261 177695064 816169329 899456998 304742258 453995404 470043345 195093019 325496972 763140605 88738317 971287277 479154146 100911338 778775099 275523629 780198126 946067077 961460559 816746825 800658436 386560022 228537468 564685075 510058956 664456672 764322046 769937168 361106044 948584190 49776356 427419332 540803800 542939683 990219918 253269771 428414051 30316194 320388241 592331995 935731891 266680544 560856626 538814458 393598133 479620807 884745555 913035785 290465800 455959171 774670154 9772537 387109949 354144323 45629632 987191776 490878899 321193798 800424825 809138299 935808199 933369545 781201012 740211601 333888120 920433946 989587629 920569454 228274237 217754647 171779339 228485182 521129704 117220116 49612479 85090920 140614376 132546008 789799254 567259105 363927991 837579885 310638584 819110531 278588368 240526953 354226674 525138525 287341279 328684670 300649257 983733679 335063720 809714385 301523565 535474203 188924963 460964727 752229473 967741193 911765877 152791800 437455326 571157363 390394674 324145559 75220421 777919881 933864425 615254749 847189860 199083253 459039475 599183880 802727308 617703977 875570080 308938009 39170017 425870728 452775712 306989728 242543962 360002958 899995613 504199156 243110116 403591559 951774077 728645568 116331837 97799647 924039886 930273382 890234245 214910286 972663268 689097877 768193068 884696526 684827870 855326759 361821907 68768035 641153268 357285611 598033316 565713978 386392781 892035257 410813212 25310746 411739032 503564737 118483252 937900251 597003077 283793696 469283219 942990341 966648951 694010471 769319184 426841921 371948589 16772236 799984918 618489893 833090569 803545410 761442797 722312413 639940470 900125060 438476284 604749526 95144556 174453010 507901971 272011801 286169450 916803405 885982137 191367206 830303609 914329060 93071308 219919070 446508326 967674815 307020310 975749017 626954512 842793916 399008768 348432913 917061016 16194907 306029380 179859661 385985158 292318618 59897187 671121731 46758928 816938302 326900840 926325142 369500811 834209577 555050205 846541629 753292431 305829869 275201734 716147399 856751341 759659545 394506549 415035999 429830665 251585433 568703558 85463506 890564246 355684425 154988260 195866222 248116589 76165636 180271171 193903799 152611346 169758748 337832372 321509498 669906982 277861384 128103989 170274660 457974216 225579537 667653449 743590062 819399677 204330670 88311076 777303875 130403351 431755870 763931523 977636339 39980670 231453214 304146072 621308420 17172997 212126159 864304935 61944693 550141245 310914177 659340316 902742313 429676109 795117080 898793983 977340216 663831633 737042145 676628431 445516800 343545163 403513965 213067199 605528229 513005457 698186100 542585755 643975562 251717621 35198093 244925410 499656725 921429928 40581935 105402950 943988187 377709637 149596510 464081869 337049294 507230903 129385479 136230292 843517180 314770830 308226104 436673050 296084805 888085450 782084005 853571948 778387103 101982771 899944616 720632226 944262879 453396969 366654183 781977102 -869865 554787385 378887603 556507267 357816290 180544714 299778807 923331958 358232633 649432409 840973351 655178638 693738065 72468639 819945908 487999755 589021855 973626576 519378266 394974099 338555909 684777288 969792896 277346018 22572231 526184234 21425865 776782418 193526803 709203837 239766848 128522736 760769511 76850830 72850163 171574243 542152475 543799007 543997537 550064347 525638850 15542058 867646397 472739400 293199751 169832766 475188933 625405287 380476306 687420788 193990917 982919043 477064827 454103607 655252136 277903514 995165120 346927363 969671440 219741217 668359933 847080428 176268121 43411112 911568799 323955736 702413 989749015 150363456 858869944 885013950 478432497 456804771 440768513 664478811 544653122 809573047 558493854 433781803 705338752 467881710 118054136 800553174 282571798 991298790 779298951 953571564 434637762 956483088 627849447 280159422 463526638 469467875 981009465 743591307 130176239 952767848 974294501 429435341 831934192 188477005 701636520 95422624 692169444 522792700 361571932 88878728 260016678 17673019 835596197 236063846 866237309 762703588 675289447 255004238 147793295 526692198 614822124 122178718 411576843 829571162 380429456 469967574 301302558 620405935 295656560 399061069 899026115 671246555 818571696 184964259 143952358 589595031 768083031 908926239 606786701 736398432 742224232 817501413 503120623 55670841 94963381 460021276 298516548 498986409 54943083 506861845 354970883 709211987 564342080 500703030 604545007 914498177 805003819 813022771 268250696 390024647 666627984 324265807 241781998 456339849 875570759 832300063 263739996 52210385 297594836 943369128 187533696 48632834 39069333 753430034 362198927 421979546 775034166 678936259 173567952 399479987 108654953 27353574 823807595 398065089 354912970 347081883 42848300 129506027 795558605 868746293 719981098 799143600 840253107 855579086 442569331 628011822 883591186 641728773 220249882 193100297 18003769 871950075 132491408 469996700 595323451 599698240 361973495 809889911 264845759 476138979 236564959 551155712 578669334 129442957 28151886 190293763 289662947 253117023 617392140 715544349 400221268 588063169 521019351 23343615 957536657 459391558 966442589 752619956 546091763 114482552 879496130 623005667 544018958 120924573 62097470 536811926 704568512 704399297 619187592 215718576 140314840 939839816 380958660 291346086 132380137 886932297 171182101 161112130 648550231 312268195 387526257 991718365 329956913 618571495 484748020 581880676 495578669 386180700 640925790 836085031 207905032 89923460 834834432 816316624 259665426 892709875 814429829 750328605 264727123 490204435 807048020 580782150 376991185 659047652 381288088 179638805 931408817 756364156 454231998 272123662 464739485 74423855 212319599 835419929 727009775 91719536 390655768 823928276 225500256 192884703 76219878 603935079 169371840 731031363 266018236 472959698 507313284 700843181 853207820 311158550 650966549 988639760 330666638 370217547 912983104 777471689 665265355 98417922 27463572 878467321 343206377 753199099 832052372 375048375 443750409 536153218 761902984 472261688 766778554 49927692 924532261 134797528 388957541 25090526 957324148 774519567 202939605 524087597 414437193 687958070 13933861 592102665 341765576 128600373 342107342 295404263 924317875 283385466 868883019 655803774 236437310 692079854 68956926 288217969 546267374 820282540 798271280 596353347 290615677 365271336 867300802 408987664 158019088 722735416 736602614 301991611 164621695 837154971 762883854 936750067 548315774 693043292 992313516 266814125 709514986 55151315 65790658 271173005 233904109 980152843 163568856 395384175 789367197 436258844 79285287 533023063 131509152 293330847 811636745 78696465 279954186 516485551 14993900 704433608 13487792 868569450 220907831 258306984 222619215 756251546 175982257 109930806 489690728 270502656 266131296 175972887 245280426 967183660 912846232 543387285 89480114 862395519 462791470 634200196 798375289 415555034 97462866 288255856 51649196 494166804 675748055 453742180 465560891 25549611 468699682 294156533 5800795 485186681 201910595 725261588 557463010 34922370 848836101 205618449 322501172 936189091 550993596 762749918 829104294 5171600 773724804 418674075 357955618 201783383 386684108 886878985 741925165 953054929 619911047 242714619 226179582 161933364 582290737 539011990 769379324 381081979 537292947 237806689 697888271 514830662 693949465 597730018 388350770 989983659 832680741 619190130 310922608 303584227 545354900 372837734 491026054 196206405 266627254 992848085 206054620 999693362 311759534 960794219 13066065 742958936 304336230 294150911 49951839 334587023 673697063 806345072 240724220 385929956 18119094 53138262 561296065 444569245 915948081 960389732 153002835 857591564 649721503 365089265 201396322 305039845 629580056 49563062 960370982 275146694 923926554 824109949 894572136 766054043 722878987 61585697 402711095 472979047 729731397 557804370 457265019 643789580 244851728 422458090 903718130 126671000 502808252 570257303 914750319 728982256 736108788 386030225 293015921 987794150 467424363 246480407 378193912 705374927 641806253 462456763 311652789 459804791 641070762 823214574 797516798 592731726 481370681 401616383 463250771 135269036 199480658 222382320 342836213 209093620 865800394 261208588 683455377 991318566 687374200 630359617 355587208 672015568 640357892 635734731 602768717 854862683 481878329 620125489 648222427 431234795 135031776 118410333 527696126 446944610 515474041 310014460 352330680 497401533 706326547 912219190 857680337 96533495 526196572 744401010 726047461 776015869 286538831 746565350 886978053 766827635 566910805 37284208 544501168 986672999 280154968 611689642 901657916 275636220 923310862 38710898 73828985 490962978 24901432 841430946 969836282 698838926 241887187 368444939 78053471 852437220 970229411 301012051 553438054 238329445 150656941 538245291 787717812 246691728 718684539 304802157 500900597 637935609 282020727 766766767 359841095 48360188 830357596 60197964 211228559 166678223 371886601 361442483 821066052 836172644 712718758 943077672 565581064 240677811 34592142 459137126 586105950 911514404 5474476 77092442 905430173 573243008 476784097 512081950 914158188 126749678 426361312 210489730 448909816 825954477 755295552 151208919 455954935 314468745 278783651 218730834 200932093 767527245 494118445 797457617 648953148 464323390 526714324 644609714 407002539 628366008 498517093 720724021 673873153 592002133 930787118 169306591 275840729 482496521 838618616 533662425 996118131 911106267 322703103 79366611 504116666 643146173 716521756 109912162 892230443 811154963 788980134 537805922 216295633 117866669 623842953 485164754 264228535 925834069 614623128 768793561 443842172 103389969 583151254 698717833 580850336 55245250 545587034 924579053 961265779 861527332 571123936 734656639 756829526 848528081 530018306 188003330 517691317 40209240 474237386 315939011 320906818 78179403 360320418 126375165 851828919 86111623 86472097 971627006 215768250 464336710 910355009 475811122 833612407 426611022 108085871 654722166 924335410 346877409 760995493 378754502 576162707 434941565 930627607 167189831 956647844 774253577 658389045 622099192 651047181 88625695 39243547 935717856 860550290 743104603 574971535 687294623 77499082 609218228 885274182 501840494 854064987 769151839 101918691 470510148 995131230 28153979 124160672 582298215 126277820 595832636 407642750 189289311 113061008 714460324 190271841 374425410 559205120 138833259 558569574 103589700 531984656 135874885 175222273 853583251 26546408 708528344 576823673 311243156 370707236 406541787 209287373 761439282 782716758 357758214 800753994 998487041 203015433 598837803 866904038 642325835 117682826 705263154 435271654 396724422 882153574 876945091 137483265 304129788 851601017 712602620 882646764 783484736 21058259 404044724 376241792 292188741 418943036 479815334 452998843 200643976 88082593 679357407 682670254 778554250 997755384 580580 508708623 705690839 870618818 623409365 370926461 734939369 921351131 813725611 867476946 435752754 489016141 85730212 723639770 447356055 131030258 957022074 327422905 110580778 193017451 125108267 650242869 386621245 709549441 820219708 68744964 814157423 536823056 21381965