4000
930332483 482640862 685476009 887799190 871756942 648005528 477059906 27334741 714051615 757023468 985337689 604721199 575797859 376696768 566795443 687252885 287724577 305587103 149280106 678701338 290826636 143474708 582134715 283108150 642201829 957403128 853135405 845420674 419070486 508278778 40352745 759750934 202191126 938377966 737289817 828601527 81857645 590625110 289426867 579296176 136393115 81864726 853240642 910962504 549049888 886971765 706197469 714342884 332302738 149722879 647993268 139466157 222395842 605250293 567197988 337082018 795907968 831477354 106622835 887869160 830908574 308986842 615565120 358165695 196445676 272917452 250001217 819071938 376546245 583586884 231062068 171202 471398697 839486211 356017457 708787251 306928446 946212403 477033901 928627581 244252943 906172211 435481513 704425379 470162045 731949506 730267107 480474345 469488166 882759925 57145390 311496734 486738059 763976736 815030817 724024013 811462896 68708126 548721928 576865591 129074816 384634175 583638589 974971102 823322399 838259174 931706569 740250735 515522700 966559704 152015181 959914222 267456759 454621695 427286743 7187571 231733005 715131002 758805566 713524409 677996586 460635832 683336632 977789598 283256774 733331391 815001018 494718078 945329319 748804592 767460152 405460376 766708944 756659841 38220238 406359187 988160569 808921045 147325859 571683535 53466725 446780050 668545083 50495398 409461316 964089510 971615656 447078062 884766476 928199728 293637369 144036664 239099372 64109786 399041200 705084348 634834171 149301808 361688025 125609143 564872965 547314597 839418220 296368517 31488993 96440324 100518662 939561159 49183383 922981009 742316931 735770836 300406328 774623921 772656569 928946207 454829804 285501921 139811010 151799508 273993881 815982124 981153402 658176783 656668604 842617449 899404773 594966319 480240417 375604588 90783600 107165972 916200866 305763783 567771491 790216776 139801963 134208362 684404285 682484710 85720919 668277513 115371082 240867047 461255212 981049614 386065900 899101832 230745801 541506231 426790472 123051817 722364625 81849785 833202289 58566244 72572913 428869056 385597857 636663722 626399911 66285002 596451433 879541614 665930325 901573065 19621058 290718343 883989331 564219332 98922221 387382534 728089694 987490694 219644771 220489170 919635152 989840850 340762711 570983829 356986717 65752541 901936867 626555950 454146048 859821538 845972101 565845257 758373529 469848403 668567415 430514667 986674148 537786685 248873376 291086092 840443372 496744559 428428300 41147622 197233503 77862117 774830742 550122005 634225738 712923748 577562455 537244622 418140310 537037338 713930559 434327414 196301225 655544805 728249643 628373281 710241394 746129504 694526317 776073714 282824578 849897832 472074481 620833541 796881511 403197444 399595440 597538271 210678744 624858147 558989341 518648016 867681994 902141332 554146625 314263756 416796114 863471081 75170703 611116182 849245007 896133566 253875581 47924997 456183251 514668209 908564551 879087209 304058473 779487167 903319809 164360521 293079144 194852568 469152726 6753794 203825552 798440926 190504968 105369390 500018524 474829879 93642260 111282571 564706237 159936941 336732264 725252092 180470009 696132891 665094668 284717284 415595930 357231389 228615469 987075163 748375482 114376277 624241056 737501072 653963742 921182736 755630669 239241549 694011462 634550707 506120056 692779088 978648427 275269315 40429744 10924370 583165726 299070653 662123739 964638676 438322778 510249110 944391229 115187476 588193064 640021305 758773517 708469963 174494124 250931954 903677019 52591214 518267967 240803995 21645551 645290678 479971242 425797090 249349234 255739480 436033113 401644074 345394200 707746247 926163755 367571522 57110070 627035221 98260078 648785554 444624519 129389536 415795734 864736222 516845581 911489287 138103068 568415571 486755524 124527902 760120111 558362291 399323645 355220378 51268571 598511132 954051826 26148606 486656732 914480725 447884699 599887262 286041291 624794075 65113751 997180699 406055189 89006816 412452974 930615776 271199541 379519573 974441053 227454601 892783334 98585472 896468428 499832637 602649614 737191433 880420533 78857028 456854502 152255649 644428341 645295274 571500551 643479557 200822358 673829504 411307428 816757060 420177131 306693668 700393900 19040122 348591778 264933698 443385548 977865715 122200212 836564575 123415397 405234107 18819288 248327259 931426273 280535082 739547626 283292045 766702659 729171307 29488881 32588491 322668304 667088371 35304407 243103091 418996968 4304952 655996918 14845488 634208151 692800958 566162608 995155511 586546707 922490477 165633331 818682003 924002250 965359722 849106788 462325064 501063927 492496912 765349808 379849146 33888684 187492385 761413733 539040602 941238018 750072535 991145907 959250178 268891274 26253505 918540528 986893199 78311013 247271840 386272546 339133642 384938057 910816244 934457837 977915245 663859944 247948851 308181973 856249048 187944900 943055019 200399028 216369054 567000461 668786819 230636148 419727750 864912446 201929495 117020789 329332338 725362 156844442 332068003 665926292 744473653 846981744 853420026 559527178 273548340 57402787 679448247 562250678 20454505 965375137 136670718 833628802 390184968 111278079 901693728 307841832 894479600 659400337 633380242 31093944 41572595 515800214 870092993 589955134 417145533 280244141 446619793 105643381 615166602 44224560 434072674 451486575 289650379 695495581 875387762 900755889 16663453 625723937 526169007 402962538 401550406 718459355 199188112 222834639 571262268 845346676 571784718 453679887 384863760 635907702 700160392 557388781 887388949 244269850 169675020 424892313 977035981 267483285 904141026 150975365 730233093 206052774 652429797 736675899 142362480 567139446 774765403 169219316 900633826 638349323 815387152 456824437 96650597 766782860 1193339 420493579 432899802 151248205 566435965 940817554 224493146 20644961 643760731 948090149 458057184 173417709 925314888 219292031 797709391 745284523 81985419 344686391 610511657 172167758 143629136 461627753 435805206 607465469 511981677 507283963 894657178 92917773 328215067 127333485 282266032 902070773 986125478 148780752 17965074 358289958 842626994 567394287 639348392 304822072 412994819 142547465 657626465 820531943 633138988 380689932 754390552 785118638 896987551 874302835 700002286 352423966 554347150 314587961 742534001 188574166 980193997 388706354 523976674 997994615 187670725 85555092 576486520 477959190 398056406 547458780 546474025 925215266 985858199 281586425 469610721 985818760 166925983 168501257 994755163 324878946 93985556 62549266 817821974 35704744 558517144 894337540 603450277 375342905 679283058 599453436 349374333 42302772 993220616 627123433 953754148 980018229 808265392 150267759 587626785 232992731 605841870 333264685 17213971 278576263 651661104 371207651 538014865 416159321 365622838 798100791 671225471 896529697 340621939 80939401 158416388 79378899 242208567 402478982 360900050 77584323 295633485 729252268 64940792 743175401 647475250 887391727 118047592 994204684 323263244 608705196 123096297 751464924 474276602 114317465 720944393 933975350 806343978 636225797 810343129 728807829 111969337 509386260 697365729 808894141 492545282 575506987 534142391 937552092 628513214 192087533 832585190 232194431 358339720 450979101 857713268 629597744 600790813 82125282 433489766 252716173 744731795 309972643 431687831 11048386 824727835 256516290 637251191 860564782 796173302 767645218 505117022 669600944 443664366 636957403 398566161 644499221 677666212 417381947 839578349 74427670 448800664 338540683 135817737 882134683 820971633 121233804 170556729 646744095 356776325 615456864 561136861 739631179 412420237 417450482 797300083 443393312 51631380 310840550 609196825 332268579 469995053 947340882 140240109 329658877 136858890 42720569 164956761 244701711 174818966 64222925 271830156 599380432 598639226 144717484 6938440 306638161 736009223 910157053 288670743 91035508 747974984 604958340 707195634 753140028 529616206 411710066 622685900 637354783 455073087 236901231 761465392 990912831 505321426 310906089 961702232 663425537 621023614 485290227 715615700 403024506 581967052 548204887 901811961 133372983 709596625 591576532 137338777 486117532 676700343 422196815 784804002 640265395 619218926 968888391 339335808 576681253 949793615 214926685 808479854 936842010 501790291 137626002 806228018 861395726 454221708 615027957 515398667 86418161 220018358 919954831 797582151 16614942 448903722 527537482 489952696 549706089 446207136 621858892 859711124 418658435 583462727 191354465 136415410 202927723 14117174 696397813 864661148 690429424 996407001 827366465 711219042 971217047 47960798 697742048 435094845 37412109 804739564 952054525 431111165 852949144 315039638 237998417 113143892 490900000 543002147 969749861 439183948 932318395 262177404 263627625 450194796 167185420 891545442 154027935 333376634 994710817 884756129 635217011 453114200 279223518 518598687 2293884 357348589 874963893 467156446 254848697 509022178 762049223 887281626 115651555 538952667 439996365 330264205 481592674 331273155 714694966 398870824 840492771 955895260 723236579 474433312 423502170 508785008 347453305 559759351 285563344 920548320 87382225 438213617 715294477 299833838 268886461 681464442 602505 345142644 266711383 717664157 154991820 497504420 861355900 145325729 634454459 157612206 432868164 652496940 925240063 853398146 361410123 204209218 494787573 459006531 838342145 630168031 163329542 966092573 515297344 254637315 614454274 608363678 181621110 187608351 419742174 112955853 222108529 741982994 633654124 629868183 952974480 395889595 777305189 191015039 586710 128320597 383842146 498368886 120365423 275757785 392098165 206332471 66837780 398784783 41388713 639837012 475190145 5904574 813334544 31101136 197763689 413517289 270566171 9022013 453583406 506716356 406253822 966968572 11082069 391107214 513211940 790308508 279297523 708840670 94551210 79523612 61306163 534246615 655927646 530933819 795735092 708217802 604731803 911081898 228303418 448280484 779124305 751752348 550651281 677396822 356569244 854272608 409536703 739094717 954281039 222739289 740324003 7464286 827135686 562535435 353896580 612994980 349580578 450703853 773235889 689641130 367131669 638245892 782029040 874246075 698212326 517756253 628446475 116995082 125375571 195664085 324329219 893254870 563872450 535040219 639589447 985098692 659205943 216437490 202157203 37973467 191828577 16546738 595751079 386082789 319349963 164421297 86476090 317095247 611809044 591510846 167894045 598413102 408646639 43916716 586027871 399416089 708476429 715360332 255776680 674135097 408625001 510133961 733112326 596770453 901491683 331465433 434906415 399137435 873162891 606020293 592534776 818742137 283791383 558598474 586436873 885901036 262677611 250600185 784166494 669872311 278777725 214173345 430493892 464663455 697179225 800793025 274848576 238854950 91858746 442705215 950425182 191958191 470956384 885030753 344155754 237947258 54299880 534803619 169212274 136822287 355573902 329084293 293119559 892810073 132128134 716146030 761284368 888464323 593415386 450260526 879490893 145804250 645288226 289034743 309298850 430137695 306084981 986138787 392320943 312479768 538387840 198198823 826208865 939754604 221564084 740034219 581525167 181374351 561061531 741976476 938581354 790886817 389707602 189296057 145426870 700300852 684176558 376331820 644190358 838537781 487844783 671643774 880558893 875800896 563108473 799850492 306917453 423066493 343736336 554206871 193011449 696882047 174490155 235604908 27627236 248283502 557102281 185026348 516278499 8731560 257339518 2821851 619165210 603720260 165631240 732562530 185557756 338145555 172434026 423403270 127430 572925490 523010960 547544884 138541157 784695695 843974624 753478020 91392984 108986245 482443648 653384028 950062566 788090523 177236561 267281202 780410647 432631408 16978348 566882436 655066496 6803189 298654477 613860838 189013186 382727335 726806726 515106968 905876885 188249039 910703621 149068266 187250268 604525291 958157785 540023478 311641704 11693319 95420382 815221059 874473708 870147037 238221001 314656608 416769940 81736722 313124733 528847158 580654118 111366095 475425684 731192424 978520074 184677161 130493817 678371410 711113146 116057598 585494229 100598158 395809026 231700493 122521424 906432616 646150743 21210429 170536672 496634912 274650791 541303225 86474110 911112281 219776677 849425432 603211387 182610296 837135651 972111966 285786729 782728488 92366479 276592814 728884231 618402770 745717459 773737609 170538121 738557103 679962691 708877560 152432799 306647508 238892200 468446614 633524758 161920978 305570440 187989110 854906821 290935861 837979272 201481320 620420713 151553356 924287527 66295812 267514781 856916618 648625553 587343563 253789733 398576647 288767704 371602205 789055300 522947759 568762491 878086695 524183945 149950972 6730254 806154905 618642499 854255626 198543726 241266277 419717727 858559793 869502099 195440824 7650699 663991437 377939880 662472419 526449608 802965407 817494302 893688058 682018 178747971 613113475 33899095 335051105 906950189 87000869 371357645 295850117 173325360 212817467 444834636 147002179 921647095 540581642 924946401 598115534 232612562 375297759 176900909 846405047 199179517 19042500 981474142 37205959 134633025 445367879 116698761 982886596 674238425 629907223 413722875 862395430 601630950 358989250 690903912 452319991 625813442 42517648 190179228 755403823 217202460 911040356 68344276 950454769 302839339 947518613 325697260 826481591 375266380 126525031 633181469 135775114 622389063 38215954 504915920 848859424 875436882 511289187 206500356 473636029 726089182 303206914 346784500 732324860 982345610 147632615 463528457 168210225 808616400 646061149 463498302 386063593 286678023 655714197 79465679 76087343 309462059 390143366 818417488 274151853 897771075 72518934 569265241 434152749 606321861 499331397 665692010 111724510 279961403 72831194 41173688 597624477 194122119 150025509 585432992 331026550 406362449 331101871 965510692 348271568 207854799 76599470 168842625 53307082 168191007 365684840 325168452 506052946 657628736 380100333 503332252 840590924 219387293 645294559 531316457 174000922 451960835 436842719 700681259 423710726 373519069 569325550 227119181 774417593 669760962 241016406 851709244 363218170 368371144 112429053 332137310 337785893 419863430 673341694 822916968 626469509 504224268 970868552 468250780 178615613 139346508 86331653 42506239 222447028 255004537 469178949 417134920 384468060 306600725 402878568 69711836 189190474 453002305 828327965 613810858 367900909 910828039 745872929 166668152 213765058 529795123 345794498 577701879 695283537 945181809 42267748 456644782 713883935 673173887 540644486 666114895 863739754 531637793 278959035 117620135 723842692 248002017 246777526 767380395 990240049 444357120 724632851 173696888 989320470 948056588 843985560 892028291 364933364 449867948 995036273 993958383 711255213 249277788 414570331 821069036 363263236 426280181 414376510 514361206 619458341 271063571 544885995 397086675 654343397 719853319 779686077 542711429 951468783 287792591 679258267 370041267 816136832 351255792 776645393 182446038 131948104 260876869 939881588 117820495 630131403 858859292 154761758 851575370 955741239 41678188 670650059 901193300 701769164 501041737 820802284 353530842 870227598 48125667 360106512 417608486 238356616 852695215 788930617 325680030 128968005 560448358 834681831 379389842 843615566 614921144 149829939 270866237 322767988 715905911 847122900 15263652 716007150 452822941 556543321 846454917 562134834 392287090 827704854 818237180 100364458 288383724 401894970 564248508 562260481 597449513 908094554 556493280 518097857 244907722 413348572 126653806 819566255 585692576 422773426 658232060 601378021 833339559 817045747 297643053 578682797 981215606 452525674 521160882 243414157 286573867 96836419 982907512 626699777 649879973 52026854 696853197 415766158 933287358 621249887 306814242 178757621 504584158 452404179 532666930 196870135 733987387 744589417 360436690 691309326 722027751 728423066 467333463 201697417 44769709 970883273 603085866 157968597 242004786 348604599 201040278 573008713 609511100 468088988 395050345 624541025 101525566 260165615 439502829 553091077 295903364 332180097 20283984 193525462 122314175 749935203 89547570 232920336 995477270 949823955 132943807 314002705 653271240 499822017 30298985 302103795 755308356 269970782 682993622 831806588 896867356 219984691 509718378 100524591 434915325 757642500 51148557 607833102 21125968 241745552 425840358 65437515 90415991 513948321 208241146 231057397 519069929 570014884 765640073 191851501 459810835 551728568 478986571 321557668 886990609 937221704 505757808 734306996 752833003 735344219 788705920 102176448 982030997 372488744 32622595 523795112 406717205 63744577 243349462 515433030 346914327 450785043 860010060 848164482 787367717 99189349 263396878 241901586 10490350 707768362 974775412 499519116 32295630 88636945 753023257 96181640 822278301 302826618 749707236 939884105 90932262 22209864 315470634 299940700 581179341 537462334 690803618 933442392 222525162 73387694 318942026 756999212 842217795 481902757 478302766 442311475 970226478 867971999 188834627 529888054 564850985 289462836 636989104 57360267 285178849 426824862 510020676 837670275 341084440 225539069 990945449 615943450 515199386 863587339 531737680 134729300 834137880 607432713 876377170 356944723 483658755 798106724 785056155 55643550 36271267 294130280 593962687 427482814 994638811 330459735 944636451 135577926 914038231 792167344 938526747 539905723 493847817 593672222 335910037 459919597 362021494 811440083 971393343 980505782 873732413 493277440 80612234 11852868 248595831 756732806 796139220 335224729 687913093 687961001 62036136 878280981 129852970 33274335 589249611 179450008 125009189 207222425 333851065 180530870 159604464 535397817 218591750 18039635 590659411 190255046 124832359 855958065 838249561 750959844 839786625 483365115 163201780 119796388 397544472 28687750 84333388 19675714 399963578 430622855 400221844 826711796 702521939 941410514 177888309 104900177 591401398 930503036 71413813 514844533 765454723 433526459 87325661 657102661 353966606 59169611 812941066 780958841 922673714 606686074 569700009 86882720 39005518 807045384 152974000 772189185 298669520 591474455 681244059 663359987 293046863 55000742 92546863 821570680 825752739 611536881 174153677 152946607 935937727 866691035 728111538 861642787 15261870 691914952 366418537 299658946 101590892 84589966 842169822 975128147 753748617 522163743 177274989 647125456 594544446 644228200 418075197 7932479 446406070 620784194 502448269 429230213 841351688 632275086 105176721 663367907 877148000 496852356 457590616 139621541 68907094 54763047 113144903 60082013 210331850 201873464 497923226 418928769 85237198 228266414 308918557 148652434 517606688 452754672 417645392 2058858 398058021 816723638 781166756 607605699 99955830 406599781 639931568 33583064 973198127 853530829 868784336 10699572 214844646 166207613 203098814 127358975 128413713 512374911 859452704 563092460 136999882 76416483 648776998 599910063 890030700 614712127 965038506 507173824 631594766 814359988 403500686 196489152 558844556 94728743 951800954 546762340 983769314 1682678 990143000 186009286 45720016 113077800 56116766 72529310 63063440 994963852 950743122 259578085 19827950 73400724 378116500 77397063 748350520 80686212 561919006 155807118 678608926 764874963 199489014 212944569 54277524 552483482 226287929 246037174 465079344 332372779 392094473 5005468 198666572 333964487 361589730 37457679 216722168 187706241 369803625 864398323 953175934 721880076 539012078 681954252 543135043 986964170 575534641 747274467 817632960 405270604 982541354 396458369 272834388 696889129 402657273 65188426 798310489 64735267 333485687 172790963 124680490 649068470 297692589 647581464 535764409 98781378 531925184 848429284 301117313 742399395 681984489 649759902 800474190 337321513 571722518 95361070 497415741 64222353 26410485 924471418 482767975 420053639 228083073 745855055 500672390 966794688 687481262 353658171 645740105 298057894 806440927 60624176 550240110 331665228 286948277 53043075 542619530 572595554 333666529 985352391 829257737 545076374 743208161 904568721 911933217 314939911 396206727 764837936 708606921 623926855 558487311 369665443 596172213 464271814 511291534 258953442 565410219 97495187 470381171 839464214 909882579 486675947 477907975 493183770 408846662 631216956 971568416 277165713 507731838 559358198 174442145 553260696 90668533 47235580 710483743 964393360 399537550 569184476 353323839 637363720 196315145 249889518 12250189 63601784 695482067 115738385 728158266 608551824 937368147 156269728 987549237 531400005 418348951 856703787 178483624 551286672 209497018 178962501 529061379 629080117 806291910 814193635 360071336 323015979 245950756 931900891 491629301 530085120 813765617 56807631 88329070 361162058 207117241 65800793 761503224 130392249 452222897 539706673 355285159 552685093 466715629 780873938 484974478 715140135 782663080 898071555 763679169 596683414 121875217 318657884 477514700 334593581 718385447 74779563 817461978 887476940 515195991 483632998 207968712 120598598 704799468 747631729 8930453 352529962 658229506 922701809 162482689 443413310 400026322 727677493 423559586 616014283 907580423 840866608 653181020 961708778 479521374 572872795 819792585 194750979 762131413 687035377 38847866 840867085 23699911 762360716 867575738 76374671 991026976 179178374 76368062 583569685 366485296 874751893 486148072 248473613 129223798 17903595 523549490 701304401 154657374 68627816 271900565 423436924 590385563 413066520 852369851 204025914 983522974 567836799 812893930 380517521 512502870 584790958 873154976 657656503 757308153 590637773 247466130 772749456 853578792 490014220 295351790 485096678 489072408 657617517 675190425 61294217 61270434 26079068 543059632 281219189 745956917 675328938 227172542 545168455 900801495 894129280 14621058 535310047 55021812 707011642 937458106 669869115 293052832 511064877 370355966 500545711 865571078 422700466 437005486 123541953 243699808 45527297 371171393 885838230 579055348 72190188 219549194 109604955 144633063 803605383 834834340 905549954 732445966 700082042 345847996 433224811 569879952 329012162 589800904 740869545 970686580 100982069 356104358 242699830 881419505 795080371 492596742 889021031 626864290 540306539 786592825 181158935 493176753 878843640 678432699 495226082 37481505 970774128 734724937 773541507 17909209 29238791 17137511 305671812 965640021 274292631 593605006 657829494 752223834 959651895 692472203 186286691 497575304 729906034 907125812 63327088 349308931 358550161 467361643 316225201 995843000 503575245 165991538 357946306 911034112 713984053 595073713 173055185 742712704 934646403 480371993 567007458 871484281 806918603 292919924 836416194 312301611 535524831 294099628 939237216 892415578 636388180 729644019 168458962 476027148 656800430 394100893 719546366 424205964 210292114 694593389 605190516 964417944 28944497 716425065 924272821 112488888 283996778 9733567 474405152 24487471 4273627 983799491 36176138 388585713 324083431 626459374 843800185 521360020 402765077 758012144 619111501 27575397 171991868 204067630 723130777 789053760 600449385 890295920 478127279 272071530 174156319 151527126 484655040 30063306 835294277 906325818 70035856 168887422 465564339 658772723 389036746 398408149 900687394 978061403 32826211 271564999 568755767 423556004 319807484 797131156 125634014 77333051 287165564 917497378 653471456 610416321 366486993 510751583 367058965 211237592 92970306 947544728 201807202 14582144 65246150 85896815 443266190 657928625 695037059 615176377 578899026 338202607 923205052 581662482 14603040 727716282 221704612 473640097 239657200 879004285 510017084 567650719 702940718 854270653 257831364 68120689 228885177 8342656 467902207 480001768 169801914 517307702 132741890 581331437 681252360 922106161 63034441 706039959 361471861 203510849 299121903 500176604 744342327 225973374 60017424 557497088 212419241 662068725 41699147 819907811 674535595 265546231 571413243 820649337 153854916 688185751 549897614 648887903 765666118 665430014 507752212 155979825 245109586 497883144 82247014 576752062 81069273 619864642 204817714 172926655 353324223 75359151 858009770 752978602 497059499 613916021 189417186 657807221 879007175 220240937 512370071 109389823 580231278 139576629 74118634 790425079 294179206 146810204 926096593 168755503 107300097 9017770 484456990 189396666 440969599 431187498 690935866 412115624 651340172 482200610 643525230 43554844 288588845 821922861 919592530 915869086 923539071 984571591 803878365 978424593 885108185 28809758 655263891 876190401 326259340 188898269 424337097 300244640 119248702 32877231 256712917 350943979 454711546 972781084 255273105 568045770 328751224 480945238 636930200 681670543 245197979 631009910 694357452 810712149 519819545 143322683 983444940 187296716 850096864 771893073 847618333 454982059 838056511 701182896 966421353 657012583 562292256 901341308 16017541 457491365 740932727 910899998 965201890 123500200 677308483 824746812 78965189 167513815 736087402 49379839 945793079 55189635 421335606 120894146 439992722 720811032 91619160 825460229 519982788 808051039 726864535 915824561 614871574 720375520 271946147 344379746 753922291 684637613 882711803 634370667 188519697 77466850 1564910 623489993 256390756 618803244 553083188 987826352 41931625 758925555 730709320 421278893 404267053 534117801 913400318 322647135 138017607 257469388 397955892 397510145 460392031 789686087 949613519 279997022 402921233 184095458 399273396 715310049 75714646 656136279 238881593 497058719 929220505 358525110 678769815 855543030 880905848 306640871 33530230 690378918 789514266 240419049 951845269 234538387 14003168 128207884 816066065 566475243 760978706 223219375 875277455 321939385 330085713 807828774 804941557 883047065 816318916 555625187 254838894 203127061 503994230 317723266 52188756 291658997 594724036 882535059 429403143 259195082 118020378 23032260 687688577 277984060 957960128 795248949 578081315 720484501 403115502 179204829 30245287 86276315 597243717 843092619 112283247 318362179 737280988 604194776 140330828 24925083 863670281 805122301 667553273 793404857 266657182 208485523 840768536 212158817 39453418 174961161 438047308 655769598 24458930 276850122 764596017 44388572 855965139 156851977 864075741 692714480 754345892 377388277 522516543 380243493 435884795 739816194 942960879 38565344 187887741 202364847 454277111 691343174 97102153 736944813 369021832 257348138 157479987 50270308 219947766 653441474 301809551 234729591 883419917 713524888 37040397 199961285 756158144 393463906 675143376 209308056 183346616 841537426 644658969 523124565 10762445 476567794 647574684 358938749 435955942 589682154 612316052 580116277 941236674 420587709 813825108 5864554 419011187 619927455 351054191 488785164 968179080 350038182 666032184 848875762 896653444 656322467 573347012 654726308 474470469 957333472 635050219 679385041 312866431 177047836 676636602 594706863 64901354 896916934 254628580 461902009 18176607 327518891 668511887 801721082 865540570 375343471 728839026 259537402 284771624 598316482 543633162 667845058 860922987 682351393 924947128 585593803 672582595 764498866 992968214 203141144 199712352 793767539 82605691 962368062 106665229 279251676 822172465 922958811 367862015 64212832 823776598 281887143 622092017 155000539 947409792 257437124 321023264 773781749 570562977 719375675 750869129 749863242 190450341 847269370 328255458 763710376 762484953 462478085 626493245 757383807 753116020 1922268 301435372 912281352 453360697 408638645 478792968 151470581 778853650 301718719 92802495 256761011 20855519 369605189 460264052 812621850 542553441 238088807 679023695 28364748 552974912 155334144 252796691 570507710 644050223 967831417 627407497 511689287 16865270 368649855 508717073 63107747 173802105 513763816 185170528 25980803 466260882 220172029 300097628 307802834 295318356 982970716 801132962 139824964 557490444 503821219 197075885 325847926 638098335 648784454 757665683 222595563 245715458 413726354 776185146 310800597 199503091 810697811 647798743 726880325 990287425 298639779 620817754 331325253 805752222 138972349 889899611 467262998 398251306 281073264 925216802 172705913 98215796 982503893 152524242 93534028 17393036 924741251 10078933 810969553 752473908 407811482 228193376 884016010 840912006 678316933 289288073 973113889 44845417 571078804 213575288 639331386 964412065 44325493 707111272 831864243 924059446 704195574 106687809 756899853 379089676 969329994 53245598 169619636 907485541 160248973 379018823 673436837 197706678 226096614 154276643 276248520 880179304 380307942 683884678 248375307 493916703 124455108 469657865 669319992 809583861 771469106 563893594 860279784 48436022 805670099 515189545 480479162 84939333 346177050 385405189 452127199 769942517 169996795 722493985 71219506 624498027 371475530 248363017 121909950 422178281 247661688 949037702 769429462 460541696 317441382 687997391 850898535 650450769 251149943 19566713 443792206 219281287 240924315 568713567 824408092 884606362 741496696 447415167 789052320 41729720 891373382 111292017 475239324 671899935 208650693 156915846 891211885 887745080 468979442 552564296 178888906 510924282 313717291 73401639 871593583 175140013 845493832 108473100 852092914 368503477 184733657 993993994 192720341 916591056 386295268 975723285 679018811 409915660 618811497 573366248 739118017 135955385 521121373 187802187 484245902 895823951 526629093 251865033 978889211 558513031 63539489 296517726 503393339 869498501 758559196 986300774 716754768 38155428 119822634 276951279 802287803 898981063 508090032 558884403 376257681 339276295 8512554 737844226 229211576 73153409 187037887 1587821 239650366 401229630 416170868 751508236 30092609 661355610 891480172 222715740 76138569 970169808 832501297 902519751 400589239 200719154 764744165 95377002 899054825 275380638 236002391 317075004 272027259 724767319 331566944 578604471 577964495 830605867 67702658 936207773 412631696 753562891 436708411 894909330 46845472 427221534 130621471 960990730 892362114 280301237 156829288 510367737 425178894 906153968 465419828 439466245 755911126 60714431 687539832 891818973 431191293 746477278 41355435 459559641 911630223 118463318 564204896 875389318 673468332 381195105 221470427 485726682 469657710 961333950 531103700 287962209 492092253 31308777 58852130 853055386 596969001 818887955 521357970 619452859 783229830 496389448 657140684 562323333 622459283 950595699 681515109 570164303 237757911 103865301 237823498 32921040 945726673 87138285 930845997 473823239 242674239 929617553 171247185 909621547 472645862 245927083 493898361 255128589 251764890 668416339 247191896 336653293 453044002 693902688 316078087 219396421 712845840 478749405 7761296 794341646 908039962 516212978 81258208 896376442 527563898 134783752 581974048 499257952 234149183 881884238 75441034 473695070 140192069 950074303 698978242 490551622 580140960 850426350 231137853 6297367 73223600 271787928 124826337 582489067 718082407 343543764 646971482 635967663 742001046 795792816 222808038 239174785 25781153 787358432 610099744 651870089 629417270 490267322 652928810 952721991 914696810 3650655 757060391 128757639 42204006 281288546 795953484 293364242 961650488 914777613 42823519 840193346 800705147 753659392 306472726 855740342 195049516 377623704 637635314 15445086 648182711 899640368 397517983 671788136 390701865 496256706 648152617 551919583 288837810 383710840 782051562 387453589 963148021 271590688 472884391 32187899 6892163 615985680 751964203 960414904 905475173 117438708 387020416 662590286 344948487 404425619 614261564 670129151 724651989 725618202 71481984 687614967 75358592 333676381 98136749 801666831 219776972 599839893 267667805 522706501 192538677 847393366 926909371 944672976 840544202 754308752 868389917 762909383 780647168 967584264 215658994 837190671 355135229 644385406 975480355 925336708 409509839 153363511 311108930 704326046 473597460 74365991 953250410 518351027 32981015 271241372 580448084 162447590 46577908 110729618 708174130 990216852 786252443 947125874 834108653 668237456 650654789 597972342 501818966 334790650 80982271 750196272 513939027 768395531 266827002 345435561 90997557 910445621 497977226 560342218 902865345 540900583 656381605 332431752 71290338 448370934 852297016 81518860 806952172 732177733 232162435 276182737 192952538 672954297 148077613 758702614 766256754 261977828 629745199 310627340 338993711 107956828 641589636 749471983 880794260 10822672 498198879 15559582 871448455 325690699 847244777 663554985 196839139 166735273 246007864 289702566 558875324 645228619 561955318 16961785 27933337 108323069 145812635 456597583 115576405 910358688 225692067 235486273 377966249 349772481 947277202 416764570 602981649 767957449 940582792 882462903 528432105 533290426 445845183 781948215 254659246 82425678 905712036 730643062 561771840 468964093 45313127 773431116 5263733 334951432 172456870 753032967 640931708 771033886 989669516 789618439 139604527 261056047 726743638 204557189 829053706 259728708 298088842 646567956 400272476 354191575 595629265 562759274 279119862 854205647 86391255 130524087 369060831 707161470 464912395 82475922 730754408 519826889 611007126 693736066 90235704 386461184 588928637 679730271 424438101 890445034 260450788 757590153 671703153 678542152 196117575 680381780 182410676 822612690 279745747 275869469 273390698 952278500 915982580 899181644 852505011 910918320 912974899 66891985 107038835 441569389 991816520 288064489 695078775 706850875 891917656 937277253 447089456 137435776 133861874 807495909 564964625 630743411 995417577 189331459 317536177 748203115 872741381 738727163 503596031 89152832 787137853 278615707 564526001 226626402 73189984 659347614 199494950 636610056 236265495 156019781 353173478 643745138 832140486 555456410 603027744 905307152 967724551 560851345 888978389 88887201 254313090 635040549 242956693 103598055 134113164 833704029 820434518 446458957 436559090 231822977 459233212 809078658 2385170 640098825 286994702 928257786 526204942 371610384 640546901 964356622 701983657 892096113 246506095 860733069 196980302 863258371 544427578 317319103 28714582 556340176 269807693 930558765 480938941 775876680 520658883 722830852 613932385 500190284 777235117 787095315 427505696 886759245 571974533 134706228 667095873 562333910 592032609 416677610 102531858 1610646 303746160 390074059 409153334 631946852 92859417 692486079 626440652 748993984 510384902 567403879 495059605 514622840 141960498 902635508 477392193 391612500 309573804 460511663 704626217 13127010 154336817 37576730 106075580 511686006 585938002 361601634 813361351 549410186 83643694 190776910 353581878 910680845 987192389 823248252 206129073 19348331 496333124 420248602 100669396 37055811 714208327 328758092 25465559 216252443 950104481 993613593 900571334 566842075 228351797 11457531 337364140 582404388 359876494 194377751 172281199 685049292 426973205 833607310 631891171 248449046 755147705 820136187 78388500 857909894 104283109 335144880 686912065 152476983 264205803 336789449 856527088 696901238 404913436 473180093 234265219 448673249 449883451 768723154 256743689 820853026 332045736 891388689 790937903 89908983 256981064 345293336 805789788 384466680 982751249 931474343 329679550 113800889 702766975 304963935 174981510 754083817 874134112 160765791 25580953 256485361 4210955 750447259 168104436 307666187 520484041 432010450 213944566 602179296 552006434 312885190 133905580 496738353 180510015 718561996 401515939 719963299 234167129 269800359 578764262 140001131 978758220 20067275 786228142 617230453 29444339 174805468 177607692 403478397 939860032 770173858 685228760 944316262 968306912 48367417 210172348 775854142 570057414 831761482 341013207 130022456 769133368 448027416 197785166 186377700 31481188 625082412 6828727 330889940 141320733 124068084 555435818 908407735 93435645 465088856 234002641 189560637 232094562 284414304 986350352 153205614 255496667 69496645 705873795 35278486 13136534 331777773 913447613 718050503 622218049 326233484 414184378 374869666 180415332 53694777 717804200 531541683 953467834 472967633 789469923 461226143 632796736 516840677 377871047 369206909 190137283 205912391 471117461 400004498 571657955 325156696 76353744 974066017 428714306 354184412 800206946 994537203 147359470 975847944 82702035 100976800 564604167 39746695 351261939 131897858 912113984 330720733 597736454 779501917 849087564 780301944 102812884 61224317 315331218 885682507 390878426 891557310 273914618 829725335 189149776 869899882 151718188 344674481 56665958 493320773 540545444 763078558 534879254 77491553 561363950 72391952 238619359 549680984 349231027 198262486 411956780 658262531 193819818 869569173 503235249 940320597 271688896 177401372 778540125 63953681 591265497 646296450 985396135 111070873 326308570 336325261 165889951 848618975 36787237 406163922 382285307 96905495 351387554 534691317 357576330 114018487 63114467 560490478 917004283 287865653 284297155 607121805 153620925 448636363 144178029 535839456 886543165 131727000 948661433 535536955 747779737 22139933 178125123 674680131 60785859 972262638 538897292 773285996 338639768 650510860 374327795 45210490 997216411 519011022 730322609 613810168 69018915 192895963 947839857 247408672 907601945 49366661 515996701 599262251 121569349 961946893 847908627 297071811 59805192 419932405 528425498 954555966 189028639 405621680 158679403 245993048 817601907 398308948 371992868 372993506 698996425 894937489 707188569 70458869 390632705 234698024 137285402 232848051 888850831 159609329 498801420 724482032 679024859 670761522 29123815 134538331 988871913 244270478 94987298 72078983 539477514 340771937 98782094 443949760 860685071 856195982 840216593 631512728 125273249 610628761 76290444 502691784 21687865 280240835 93995581 270419823 179574884 466514066 598266586 814920913 260695271 872662844 162559879 744428349 796064740 265765589 318405769 3767218 262837428 644005325 400183231 519679302 924299497 557492904 659652651 691563800 178519473 211855145 826606952 157175074 459405842 125171817 665181147 258518494 60529203 184263282 474206446 187293720 29167594 255313443 832544333 224517016 351207810 420283609 696049448 748882809 723347904 790864314 371811486 741170332 619403204 951385157 19164901 553008343 218199198 856085551 87814702 971754141 398268740 360847972 30119380 957396822 671203282 688811680 954529840 635126419 340534084 985685871 840426506 658573569 781165757 865845114 793332991 853291122 331360187 738659234 656987792 352250755 599929082 131045473 723308095 266289459 447083914 46037485 20964209 460792638 587024172 596880914 468200672 65497886 735186356 447104176 936758224 646377887 300153199 741657261 420034965 710424398 569146270 949380627 155298763 723877861 768024405 418247658 2287542 651165816 783051423 370914882 93726056 814977085 629168893 173680351 482891366 166283273 973622897 224544847 327734217 235470865 943630229 640074341 987126030 129717092 4031622 225138789 783078309 153554441 320287168 214526076 571799535 249730931 52287118 894247190 59501656 772386306 739178857 96211401 359917903 153282346 707308635 962616046 624281076 816159716 471515741