5000 1073
720251906 237698710 326027440 620976929 599612947 635854570 595435484 436461941 648143241 781239696 3903835 73664484 755540729 433312357 232618344 708053891 113478453 117798157 450332898 382755153 600960290 484053823 213559946 560088524 523988449 189310198 445704080 768984721 865266333 817853718 814461729 709926586 149927923 797223212 341479273 795047085 257144563 411416841 89348883 817963618 470252275 647125577 257121801 56106877 328479726 884221344 380910877 263380569 733204907 773508194 553930141 767579953 217528251 784907802 401525926 887425328 578503137 518175012 914090542 837273111 670994953 386638565 957802884 401563321 350237955 577292480 96929756 497560919 629572234 744368251 884687274 558175591 439742711 84327212 490156048 152540999 632629248 688743473 345582029 324313208 894659847 42672450 926165019 514422558 935247278 124684401 713071923 1513298 496311788 970393451 419041170 172124875 130307211 90423292 76290097 854182127 212213023 26160337 634422262 93101483 962362618 81615296 927792905 707173109 990152516 847175942 172479447 407954454 821507001 58524245 841589552 483562731 347575504 765598935 658352189 162961702 927255941 839860193 749074587 936160208 265078174 22771445 950552526 814823742 354080144 527972635 37809278 337347219 863865808 265020192 951189588 753087842 639151837 977408156 134588860 961805946 112774082 800114642 124584300 70089985 271961034 762024603 420232304 321682039 973009663 700040040 432834674 708876972 804403223 474391495 650498655 855080249 809250424 693073134 160263260 442425638 708135603 212183788 77670996 222353707 605190650 174439206 635902867 703016666 130395285 944881822 354846292 342605911 608609989 530896116 799251947 156478782 297058990 928452095 55089133 877777920 840874805 592596031 813479402 657463146 439297984 516562201 96757117 947343977 640109137 998087183 235250951 508986973 155670815 910575849 349619199 889612682 244295025 162787162 423358107 473083589 885047536 3396017 698186005 922408130 825176104 607702910 381635487 624928237 210030283 766803388 799697743 473478908 102307443 511900836 336591567 120076224 623762692 327002693 38855684 861345877 514025909 526852185 719762822 589480749 680850848 804302694 907310526 985106887 161972141 329964199 468083421 448484360 153667670 485055158 281916650 706495735 103710824 684598341 304703861 759644544 867814088 487678452 749739477 204703114 183236662 955787548 841969018 264146206 331604447 902209751 521731891 749512268 289719689 606783912 201765010 695029412 717413415 377389459 929271188 452648402 840582514 58577403 167742602 978212317 423771836 34573109 228605985 544149783 900973521 306626765 347994203 498338541 813814640 246448246 9732046 359030584 947739800 120472594 114926832 917607548 135595321 87028746 211746605 150603077 141253423 38529693 333018307 531533364 106418385 263152929 47876993 182241216 457277361 757560650 680063208 422880570 696068118 202599599 209572544 270941804 874157950 566111816 751697919 223789335 381835658 73182304 134260235 200720050 172834848 322134423 608574272 751250847 50363656 16539916 576473265 540819069 825692602 148576225 835677791 255660424 403055375 860526323 582461594 46724890 911799978 683263860 898651498 206495285 359673416 718023283 466647443 547456788 572965034 661092859 143211775 885598874 823616165 338514742 325833139 715284008 677556292 998805482 214253000 504288386 100860829 597005914 201167550 716731643 524103678 983677288 448347198 695220096 250767330 808901120 360490677 927555411 213614700 921732863 660943258 251102421 316893792 356042683 740918389 821764172 135555109 274388358 377139845 493513327 686919338 875049138 89677182 738102092 20247109 809939730 867644936 747116681 959566642 742064145 216630991 636617113 812731893 607528603 83673981 610176320 163076718 9059455 168134525 491993213 451225980 110024839 568002509 590593270 177432431 760488941 510838390 727963317 35637328 64574003 635854150 343131794 387254584 950947075 527302739 68853057 256671477 697320003 554320816 161463080 40983202 629408812 956209430 775229978 966655969 90444896 732702339 751727061 251682705 588357808 989747964 47756642 517093468 787601906 744446870 806697753 135766778 646150984 909667035 430316030 430836992 973877854 487325733 828770397 52634677 55206996 705325119 897260414 398945009 323094679 919364021 544926505 357501020 279437344 13325382 555288317 715648938 634542495 816392453 214531198 536432802 131057684 690721994 289725476 747744428 394161568 651093998 504056826 712591248 301520169 889314828 892937287 785166232 165923186 869682292 26153098 457819493 927861424 168412735 677289124 595312566 148665500 422545359 405153294 914577985 367040863 122314772 195467170 313567465 512915737 872945750 700655507 510711188 979872978 733748846 561747642 714009593 820365716 789615283 339582994 848378033 592763285 134819716 582799358 658597112 223151459 796737840 864754456 50502614 854902849 316067885 429611851 129312535 333892506 189682677 101914805 460831807 530400180 730968348 852291472 548345148 651290346 683469983 242475438 734454329 462478679 704725986 355157758 433314721 335124927 76843545 508749861 488821015 931906899 899371669 456239344 93857491 744076995 249455042 66020123 49026654 452152505 970471493 666110945 402126809 389029502 870304721 217340285 707848965 797367470 394103321 449123464 838216517 241586688 915124616 692824749 438174012 296419440 292535821 725600708 85298194 437218129 49313993 999848610 464953601 505333419 789925700 541358717 528912537 174438121 287515295 148390454 967989651 332322012 93535796 430684129 610335183 54849635 409324590 611300822 618955031 917891477 284667015 738176486 354319648 311516469 142317508 946801234 276614536 196309596 978930482 105358025 975074004 763782075 476390684 166774927 945806038 565499331 296072655 155915500 305097532 290387289 792902553 801560500 585066963 739207617 980464745 344701191 833423683 286978818 144704505 653441494 523591907 565930046 924008094 22258029 303182969 776398325 26078758 407056813 623782929 744621707 4141150 860092464 381297277 217077321 291829456 706172643 16644769 379632453 374507012 410242936 439449790 437205950 823283078 23117059 992382944 393669679 288694158 149653345 962534775 435389223 381925105 152106270 230031052 228756684 355226984 888936224 997997917 595388695 866624415 356836869 245506311 845091426 685627998 778278745 984814975 793315622 325873668 761218085 562268245 231319919 262352749 892853677 256273565 924337555 775919550 183996680 479396754 103076758 591751902 509423287 150228514 141545551 97344667 843754916 894932935 3663703 232800165 728424277 15855136 928339869 441977416 202337145 496882692 360486613 268875666 921241380 207689336 151796093 74352952 725701426 353747551 359795092 446855333 517362781 449022334 293031973 780533161 25454308 346582804 906359233 264819939 700698196 177898425 887392526 618998851 634767261 517234462 230023227 597619304 314988728 530850959 110649157 110805067 874193961 774371416 512145386 712121415 415503778 944533357 107684899 162550085 555762054 592656201 27095908 461241933 317701422 132208920 689952449 789955520 450427946 948677431 942790646 616874709 462650074 503557085 684618720 857900797 378153213 153503557 793267117 466873440 872185523 617727924 122478050 44047169 567932014 460794909 511839331 507886493 675247474 959821885 455734220 755287563 895232094 685797660 843937130 228797081 680239502 45240243 484454414 463077814 448132640 180436368 631898702 72334599 964107970 766617233 885289760 774186543 875470680 711511490 162119725 676719063 228954454 661486134 173335507 983275836 89807959 529954207 241817363 221781549 643491143 47073407 152696156 552832659 472020877 42597926 805591225 888236398 327653388 218061278 757611440 761524062 736671740 623070593 146725612 888343033 43557763 363551174 289883316 725703901 107682388 472125190 794982335 750826793 823966685 417069537 455796029 210541534 531915424 483532048 624895947 574956551 293845788 606087826 571247381 25785522 546362055 791496007 342134280 161174415 522796023 332279115 833573025 491721776 61601237 685724225 531555398 820294561 524811150 811713072 332508689 255358044 183426057 603040153 439249179 848236717 470552845 63514896 860114145 521739943 99784590 600945063 722969403 482897834 838934931 803202292 866920120 559041293 411683503 465319538 856815631 553147309 239899284 148479120 669776742 897896483 888132489 698819475 866716769 63466784 526390326 604321042 981285465 893564631 120025530 642854966 701025804 882694129 184332397 113707286 725107577 698051384 689265412 688621210 537967993 663181259 159842089 991297600 814987863 638746450 679017949 764722266 906568379 470314637 833303102 43220414 821828979 985933838 475745638 95772558 774660047 450601651 536029646 822100868 472461425 899138139 304191424 726660062 272731911 182656977 150001670 365263015 387712621 197428826 718394908 810527513 259991203 446283319 903462829 476003908 132784010 436617643 675499133 485477456 791365385 435687327 474923984 326206143 529850878 440309688 993368475 766671807 589555678 851902716 384831662 121010660 634937130 455583596 355973588 64665894 60056643 779316351 455880114 603801156 393801041 81650494 686677051 373315083 844278940 74379288 10477148 721650093 376238168 682014770 883230598 249278944 933579219 271923346 588930954 587497665 179754526 522530726 657809483 446235420 369872902 255383274 535013285 325591737 883524196 875454916 136461962 854998778 949348954 674232220 81973080 301147684 859941367 155977370 687625992 169385218 884733693 794677281 398762263 859713663 743130843 435615877 907843838 380362974 181068835 904208660 857764938 718642400 989245991 50598587 112960412 750929547 836706425 75458094 238414101 856323509 207196839 718214124 726096955 642894386 259560018 992822841 67668239 453896327 907026488 915439222 137598315 407092309 876862571 411492690 36161030 29884531 10100667 947146652 324154348 222988313 53031529 148830856 612344542 701652449 272457730 201875010 267950295 241715137 642811543 52109573 165771749 533154315 917293614 981183057 593698740 635641892 656320212 143439727 522817757 473176986 561609488 556406188 135374017 870457934 48397604 826492921 743460130 947283222 151934791 770765801 185047575 710315986 357513472 169853637 53326355 618316771 854979189 898629291 69160657 493730919 650332003 919272587 820899669 335724451 494949534 484008660 652977898 613326839 544131494 387127999 192814016 69148054 984766015 807324952 627059976 4429631 420784935 413081767 427403906 975089675 173193233 579410342 666319960 657465609 127585250 425415524 799065578 557478296 302589319 206395246 722091415 424478181 628501118 131885915 964834613 702788190 15594353 740650165 265859749 957133872 961329168 436535638 833699546 709095228 354571095 300165087 111919542 243959462 887234538 64540670 39628373 839509798 658988466 263450893 613222891 262474617 476061154 349193575 697727232 658100750 456184577 520501031 45051532 49137829 577886932 294102129 359030803 452429446 331600267 355251342 281953604 508328741 566041106 266007630 714337063 668179108 299730003 606596393 370914785 96586676 993183029 215258550 264489077 168976513 807628901 286122637 49384292 996392321 376544320 273637190 942560786 816818329 494768983 6011954 895795424 984062108 800902074 180567143 939065970 550390266 278704521 730402506 794129921 511948000 605700400 5169371 544112171 546202504 467209371 890292636 748436094 620271648 348556750 954400382 146905740 785302264 62133438 20063381 755629497 722508262 920294456 601414623 132748086 457507817 662375718 547541642 209853356 550412982 971039861 929450208 867562867 980882911 945002185 208162807 777838430 921153062 749456201 550325607 128444687 201148007 815834768 125981 886318100 569122192 111321275 786261513 918380231 812889392 711122894 44390168 738176196 602992689 872867942 269494474 665794803 127494048 548089160 839398760 304973773 594944387 17378703 737481774 433514645 566849376 707453965 542439858 645439910 247377561 642214420 602267461 854767351 911538161 462388341 986471658 179107199 632967897 354819613 219594838 473059495 915178144 4417416 855604590 675264308 418855184 460543359 31112749 603514941 385002237 774069337 46576195 6579591 397953589 831201188 850641761 955955298 53275827 625248977 968795376 799281499 54947369 698769606 368018824 589017626 735597950 906220313 746891685 471230042 624675331 309510101 543466993 14435512 847163913 784358545 241554763 836023998 293021596 837048252 602200557 627568740 193914766 607300960 740961138 483392986 875564460 881269087 468511764 953176951 134260202 554691726 191910674 713617782 471451303 298067069 754356949 908285705 957696049 368589299 498419885 935888976 363360861 987234371 448725714 860822964 740965418 293935001 61713083 491913939 310518336 442537349 934743436 703421993 706740730 743705430 340597960 274697881 829324687 422213542 462568158 842706515 609922316 421292135 703871770 529492060 991366526 775268101 639795658 854309757 699449163 412531048 732884989 892446811 37796069 682400031 72938333 896520696 688423051 573008654 687810195 251005388 237325217 266105130 236060512 904737705 842393108 64578456 508015297 124019860 126000546 67259854 923493311 477928425 276937660 352951583 482907889 108796320 127565370 925892564 836962125 378509597 184154953 639150540 273657789 785439736 87809375 407535381 113620064 18559105 89833018 684259816 262112066 22858594 598739576 590187763 350111423 899902214 466232518 685240860 796836656 407929769 663537540 910004304 85876093 605949663 145341829 586362725 387047124 637545864 336177340 919853881 812230093 826683734 170348190 108360709 609850732 29538285 576873002 689426098 1586191 90828630 163001379 153484605 230412329 393060520 328800896 730407081 655214947 628193102 951129424 543899027 348278568 356605365 870285934 390055772 138252557 203852831 231444118 150943169 491290216 722871524 176624286 388403099 602704598 249388643 89406460 211117571 723066647 263081227 486639053 350080366 991645901 860296959 168869550 241968486 444926040 433117043 81361420 324821388 725995365 521675983 272069084 11992908 548043532 928638762 235909745 96193447 29013033 712760211 718862922 558916679 459500868 973912154 983494312 218545762 32861653 87893616 569795144 419339423 245748520 42072565 652920616 795950758 639900391 596407565 665151457 289641450 566138050 474203116 855586572 252504289 668005541 960570766 394424729 128334373 892286216 620513499 408039722 251185644 863179619 932900469 157063353 972952128 741276211 715180080 242681514 863337050 955702550 246692084 450574320 676306297 3940073 494525348 438600424 408370436 159368675 440506032 19630130 240160904 688094958 887902239 546602425 773252144 491596233 223655729 752175431 464937100 805819061 146959021 393004237 60162312 250086247 118418626 239838998 971036292 923968005 301925956 674052032 202311338 814935854 106247992 107716595 497385001 248583572 521104325 861180596 418751182 746733596 787255821 667616516 819065073 627453483 340590729 758912486 117428912 387234144 539525863 514979896 457618628 423031437 654653826 578285709 737321329 390941009 849240187 394922268 610512427 19726701 608078442 877574583 333568752 569505942 286300681 836922900 145237005 459862160 299166900 695560957 6433661 875473816 946674892 308804261 812095586 105429315 235929672 712997173 408838665 893870047 813480958 414005861 435509208 30066846 820217749 191066234 914742020 406838314 218070111 487236778 391482552 249008068 515053733 551018412 154334240 546097087 650442404 15265844 172008294 213835527 280447747 757955032 415246146 579711282 900622845 606157334 140318769 499102620 805506359 933979602 81028933 484690004 947657006 827093525 627046764 452138997 736524850 988902687 368181500 870028602 784209937 547247639 210845685 964273119 966071153 435110555 91403487 293021878 173705273 354095665 870789678 934704661 666592423 130625183 136958961 528135352 729884224 567711846 166387832 83386301 770897108 663427496 768223350 749528487 293708872 442755399 742246580 232395204 850100646 777827598 277364261 962314067 818855243 796161451 986506576 573966326 651235143 704691541 669290435 370954979 653274573 273646984 174981199 547595018 708633574 910510013 987831418 196220691 466117545 831648084 678146120 408098049 867741551 145598105 300575508 283372961 804755387 543487010 607385413 406188867 315059819 878883758 563926648 202809913 919239868 507398026 437562051 293171537 266061835 478644528 289975758 396145094 908873369 408735761 324384995 680659119 232825754 472979815 989403381 641817640 624649186 405830988 568845246 218928961 85801864 627842980 212827273 594260969 791594430 360033184 760395409 496892528 937522799 196572499 450248316 744478004 845641563 994182801 126079078 497590635 742253696 456758746 214046247 131562696 262462613 605922160 301128352 615825898 67595313 683822876 725582238 981410313 926450327 250090143 829808453 25407190 71908026 708169870 98446352 468953596 428256308 403242272 733662640 594704328 309384819 194859752 950860106 419492074 568667426 753568809 928964378 45564093 854045385 25633947 659571181 240750067 87702523 177054841 308686491 260697373 96387037 565106645 413924387 21396376 111892881 850675635 54405462 261076918 155309965 455829907 214830367 984301661 793908692 833031042 82195958 65249055 564186429 833570138 813754307 679044238 615757703 235021116 951979805 224579213 590183761 850016313 866301462 993392345 174429160 638980994 10519567 95588305 122946534 809080231 576730112 891355084 537583837 170176664 906498136 933192208 966341015 998033218 969578786 391965123 779989294 615037538 110353769 729380189 546899184 848474471 236952161 936281998 190721594 577600168 592080794 260875536 939438062 524844380 820041627 640767019 58658033 491836542 515239374 380659400 395802675 976494846 689446946 551584940 617729015 924920177 777865660 736720606 731707749 735801886 247395650 435237985 493213156 163510343 487223468 697838373 454605462 476778157 411985626 534766065 497069837 248272639 776524398 80195003 21405475 255878693 218189165 468036081 132552960 921945637 29854941 228753346 220926174 610658924 50914752 403758760 71015809 998030658 669247876 926768138 321438763 341216384 22826184 44756874 682276272 243941954 577722078 314111981 188337150 821461765 938330912 437767511 621777740 51036874 395786447 510259126 266235099 35358099 750702550 154492133 35556060 524475348 904562626 766222761 38987540 717158555 542823020 929749151 36708051 510298065 288593435 864964480 515437010 517434453 249902736 917867191 325932628 495825935 269320952 103158684 216472634 387254977 414962886 632079989 798271880 717542192 675883859 899466467 926126810 392705287 656323975 565564951 251137137 76365132 183785413 228662304 939696536 387204439 814689049 532762950 514287814 544115471 884023460 955525651 167131031 124418847 108383956 949891590 140449774 267769908 306957396 855283389 831837420 108286667 971244491 697754378 219897265 944851346 105121038 778082221 781235945 196633935 697594352 119575089 256995507 604624712 748780480 957689761 155393965 615512057 343561424 643862151 161346206 554299591 203298551 523061258 637027909 639786100 648981074 359340840 894202404 584835282 164481951 452254620 388230834 54216205 749375085 332821812 559231277 63261905 611206391 973130509 264342850 900180912 112718985 311347049 202198093 316153344 8514628 403898050 763521748 134671163 897357798 483115642 170750597 129822210 194769146 690931354 633907957 518713730 245593629 756200144 206030181 487822556 816760831 376766103 174002640 700011932 229847422 820945031 309105255 695200688 374665070 999659505 927896109 67336527 814781404 931030296 938509290 851862538 875231963 433170568 479874585 310910595 312912525 645065166 120321536 343044844 822623000 649911782 22311057 487275696 184713680 306085905 169027906 817827169 663937740 893453033 408899865 146871170 716096503 543170094 995199150 837066708 976328003 293800584 37306267 567102169 154574015 16974114 148290927 339586255 249179791 596951633 881127737 909477859 706776779 502231042 501753540 331381776 27997002 761894590 918575476 692013187 38559387 884510076 54949516 843637032 948702752 650502216 860562452 163684705 761237301 792274775 211135204 589886748 500469397 442610120 415544762 198349688 337071278 477598745 741769509 487605776 736584611 154278357 104141424 927799170 730565499 842600240 681408332 695642795 773439629 144197406 584489897 7747408 238077628 276513430 422440950 388161685 523598750 768151160 662584607 700230410 994250742 930415776 323711381 263837800 121710670 426208927 614701997 639994592 366134588 882371021 755946087 848140788 713645543 373427541 417729779 948149962 780352762 539251583 923985749 571810741 390776904 375152214 376407574 619155490 19342079 51737796 128080193 644124972 594496189 770088266 914093071 596607878 466955021 870973994 729054408 149285792 51639666 995427965 471744119 939271381 881829246 999749623 791101428 228045186 412153263 627224059 125052495 330492278 966484185 817703952 240385902 432384049 173304971 187697217 381989513 840477285 328025142 450070979 727655525 74899416 416168046 175804886 654682739 375071266 736359675 500701191 641396042 297463367 913801917 594725413 209709544 860849073 809885104 915127156 301707986 78657330 690182233 103215098 673697403 456910504 677689956 924990787 959502303 184447033 24032530 721695703 846158837 306999749 612607286 288190456 671698194 319329703 102656046 666272851 837428819 397447785 949220758 59473567 399261957 823725628 69023163 273064432 580690079 917557216 643412171 103053312 254687270 166166355 428852770 840455366 413269908 241939865 1166424 444587513 155586568 757124704 948874683 369945153 904175684 35212350 386234425 795515148 400994448 95250990 500705098 216561039 123827565 866990379 45814699 665108188 152613525 676639312 417560267 629250681 274458865 582452661 308437321 128624810 114306028 148637665 236175315 828529571 511200026 993793159 400518143 512010779 866362087 457625533 168948652 506486544 488999605 642700357 762021247 880055137 61134681 964283347 948562517 587474629 794090531 346141330 278392883 863036759 438941978 203247024 287691762 109234497 319299380 295346890 81995789 662578407 345788485 856480282 348856264 787609374 822920215 283707579 32713253 243095237 393497008 426715412 317060415 433547557 899317180 174755358 169036113 967154027 811857339 530092250 375018359 63666839 498058441 919702584 152778157 700968439 954302497 688593270 231921636 569334551 378380805 769255539 431543377 439361181 227157441 440214763 426906427 309030218 590986000 175903093 672913673 266071037 171216866 799277134 394948971 470933216 669373844 540605914 502514302 407755456 612168507 705398574 317136287 814166402 71927983 68133247 357533892 121753958 568119755 399735821 835700230 433519208 371060777 903493465 767092915 670353764 727545993 962211908 981066759 737682260 560686969 911487315 22192145 607683475 519997939 17210816 294780424 167472330 739594918 170879265 255999736 741465348 530854286 35428299 267676731 989127671 82952858 421560047 937000444 751138457 181409687 96658908 383167591 811294874 311323918 689175308 900808171 93846557 423105022 823918254 262525454 75463191 308991353 899995008 929522923 615374653 623871668 900913974 249341775 227008827 604454485 754984335 981754795 611734394 228738218 557675289 655116222 446486292 876460887 588272580 863063225 280496215 589157738 576121071 23145972 936894385 409760134 310130492 491856548 913999358 826367589 126829472 877622109 217178129 727875684 824556241 964112688 304268795 577766489 941938997 259534893 618705209 608193374 378109208 708753557 219374096 249385871 422801187 488149716 177361941 627891006 142924072 824754225 340142220 752769161 549456453 829359339 463972793 78658791 953940206 596206266 359955803 903789443 740817855 552765585 596186064 516112966 176757508 363187774 655170410 307633963 910621154 171543038 419126246 713624470 535435255 668045662 676482663 384083616 611963306 512680580 802304853 738649628 438156818 605827707 479171310 302718436 625856000 866854067 440823328 271447704 797634945 938218316 842525256 680472418 440837535 592690708 93601704 45225398 337837335 979953197 813871412 101491025 242186473 405130058 510550883 253761806 19207432 959831039 719482379 198182104 208716867 924076055 777371845 278983394 137239989 522196475 989186641 948836229 179066607 417043156 689127505 567291915 938370259 18765723 562785036 403025387 690189231 857232215 463698921 893119829 221389105 208178673 568313001 349702315 346832860 755221546 52686813 403236034 618863177 186669742 762827850 119207892 505724963 262988134 728883340 824381235 865478343 358328243 477935899 358673306 468408098 354907924 215507515 526459610 715227170 720802510 258540814 704553682 895044778 236010841 606054547 793662521 686659782 628614627 234343428 995677149 295250773 253094435 238509773 286923022 986613522 717856290 330473982 664383994 169510578 996941145 746565461 619837363 612799370 285415740 186893926 214731194 7674416 747171590 877360747 379319478 972311666 793103210 652354348 127383032 96584422 263639957 46902000 526714179 299391012 219835692 258464697 290726925 53394634 964927540 991368928 796775734 11328511 239075072 799547201 42418953 868208270 916661131 21691693 81424836 595086627 311864292 549144184 461424934 21705654 417164755 606877770 21701368 66169305 40296725 944579950 202881114 528626557 732688559 789380184 736079059 385081759 413412274 476078204 555292157 962092263 411440550 472614862 904224844 742024977 69194943 229541953 388863597 188491980 135290201 152582761 976490159 970713555 126288544 153509232 672893364 498369928 147330889 153345085 81816937 177538780 981174233 679729272 600134824 573050590 437369342 174651630 3085994 861840471 374063952 39306624 839109070 466692474 248273939 695249187 429178636 234919165 170874712 32751052 431938055 251830970 195250626 793266046 817582815 544250144 552189159 653311561 670663368 157200424 969245259 735748345 476898728 895353289 972581967 519138624 422686452 54409424 947236376 282980822 564902070 166930832 802747149 58333845 307520385 129355276 276752434 912184536 585302743 109491791 77283753 884187622 568933257 83935941 34532253 556732125 8733764 141368119 603123497 898308166 602025994 369268112 861001279 402994491 101761407 921259993 988143767 912304663 858721037 92737282 967894714 2173719 949666788 484531177 50108459 213501257 913311398 551489009 420199577 89072215 350224064 536124007 295168355 292944071 672068073 478312121 713461190 833435371 680417384 239237641 679664325 411850581 767131362 628743192 652300525 955707659 702414019 42087259 295853477 443609394 731695185 987737228 613358642 991020599 180390426 354923218 467205852 645134768 878574655 37338094 732760160 924659925 555168498 545444012 762169147 896066169 452485989 295871157 132590339 45575631 532095127 531647594 480801172 609017196 161056680 556139862 151809343 400466753 259436881 981537688 921874127 938871346 670725586 593975826 957797421 520647856 624046403 792107219 592475701 727607363 193092523 922778801 118702560 606854825 179083635 380223400 373967242 540875133 432103065 183564415 103706121 935267854 613658088 352366281 959368381 715148060 205783246 976529796 913573483 824594547 837821978 233696648 218766333 84458346 414664159 994449741 866094387 821659373 862964313 372257061 600708294 561035440 748406468 285329601 66126144 697473636 168586647 842701765 911489613 186051413 513933494 165513549 286390712 845220544 86773423 528872844 164925187 170924074 898737324 662944102 760531882 107734450 444941366 717616511 547801948 217339553 700956015 617480923 312848383 565935106 111144269 256906588 208933041 654856976 177481652 873694952 571647673 348305169 813399141 98180946 150704977 595840872 248033780 813391755 506530084 776169596 861814185 495164587 732881742 945699601 436870951 147767279 75510296 194337808 710859933 683994798 525543239 210338122 811579590 816767603 577392296 43857379 385941890 203741281 441443557 738491756 362880837 847932244 14073117 964554741 780080740 399138478 636676303 148836392 537515421 354906478 74833074 75703717 91051512 896472458 951138625 640719605 93957619 629442078 382363086 199027623 731609481 199622240 340567646 941657934 284642264 819882690 354095719 753668412 258621964 197689436 577853279 553821849 908370693 945700527 191920646 613248828 202493423 620625408 756203864 194381910 378121921 437497281 82224078 115084812 200713598 484998203 647483766 846554237 235498043 655339074 842916951 489106933 211817054 245159444 610473493 994568798 868551294 803729266 448006835 468543096 345320239 50369073 20035461 421156876 296365813 766101537 417969916 156115135 930454535 11485381 283695073 166389082 380750799 384052503 91034607 852730310 713675047 985224366 28340798 724712716 893895929 378816035 143119000 965487550 246590599 178730850 537690232 335001288 447920837 775883255 133598587 971404878 570677902 16497664 191570171 459009448 339509997 825169817 575589405 511613738 173221176 882731053 178834327 295349274 496297379 828755123 382978427 453214778 404765946 384213395 816255643 323455252 800576844 190976089 466728243 826556326 10001803 730038355 710967015 284806290 775981226 13841001 441194816 328692615 837808673 979609109 835652368 879648228 515318110 913581329 938729773 744833878 898410706 267139716 329577418 619297328 423687636 307253707 447081638 548623291 558920386 452801906 302479501 208794092 919824186 510817528 824662366 116043656 55605583 789602414 893293196 519251002 419653634 155325962 805775436 969856568 775749598 72381006 907117577 695045235 413297124 868192880 142076879 27177488 660702729 859790208 130179904 616421360 564963961 822432018 182155892 506796132 284079995 769386280 301132141 305974532 419895168 153340773 26232530 406534733 366784094 350492137 90234461 616674834 999475152 357306836 117104299 189694423 281921032 550818635 488692854 612078403 315812618 409638786 714320671 946101143 831440419 540909632 853123245 736537481 277930278 664162511 388028153 807447556 261619150 681825237 63272313 727018811 362369880 70853121 582171111 783182832 769054488 508965332 327038200 492689101 956225743 882002005 40739968 690513678 561557663 926307446 903233385 959588302 955232329 38796071 959819260 375942215 256935240 736284441 235334722 527214969 909927238 67538674 438520090 651714537 329342752 976125993 848021583 386362584 326493429 96016207 918647328 784858157 5385926 440942351 613161172 695458585 321423094 324565973 218186860 521380958 716823675 34091353 871335051 475176894 98314853 765361729 216283811 891517398 952753466 825001913 531798187 498752907 782494423 743488328 648004525 849888174 563961974 613658975 470141970 364011175 735192075 133523933 437424683 501155699 78133650 546489841 11609965 433661487 298466602 668310550 741414635 917113827 303937233 873285955 688979263 289166078 816195157 349757462 141829508 898155086 186836737 282933812 133736453 790236192 718392479 816950214 253424646 696974690 207439662 415625525 600565961 656743452 171307593 794821463 51815880 679181048 681799303 796683039 377888956 64363987 972850907 716510038 762459214 191358968 840512199 460327188 342490338 220627945 291926481 624893671 730541564 490174415 117053478 359404242 849491785 278936488 343818634 687470664 876880241 437514055 234987597 721404886 954194224 914566600 509954834 46454810 514321690 146881710 1352288 811698188 121931047 34852867 207273712 40331213 698794809 625015190 192832111 13165857 977926807 162055644 686647123 16880447 157049006 959301332 574010892 803853744 522976290 740847922 441364996 314215328 347588307 928599978 706236549 355421267 697205506 150146327 868794793 17882427 822609772 11983346 965239075 580395222 690413728 954928354 238247053 104777697 192755736 594238004 300263445 779241890 991094404 814302529 320974602 234764458 761463236 458105096 721746975 578043333 781843190 94416365 161988307 637615291 927779139 870664029 388999975 326113975 562658062 620766187 329189215 620235357 902102406 678570627 268793807 574959703 113234208 969381362 1117099 142273706 87699098 32463676 884837496 952424781 811243986 833926050 904736617 828238860 161907920 177012745 99838874 888700779 215049615 137063881 535290988 582017422 311202223 103131932 205699924 995443949 788366906 742339329 381083506 236988564 795878765 525906322 979501993 302407400 547841621 596719719 835671431 979066870 823942744 769232676 452139954 982221665 273742839 430561765 661230675 529923406 452543684 730414551 766475848 676170935 51204916 313691444 496935616 504139572 97960823 310902685 845386125 172951165 723534019 42419501 223202710 97006098 885397222 28028555 933320859 512926016 212618253 163332357 538467680 747014455 522749046 681685697 987003010 939312481 146445437 579871503 92903317 384102151 509538996 888159848 825170069 151888888 950585562 314530876 447051435 537701902 121233804 786110958 950610035 843635690 700693948 829060239 166422652 903985434 670627287 96725592 291125723 256428664 961629029 389884670 586953960 728697124 45516964 403821520 526964935 160605089 223955195 876500580 324283655 672957014 511381345 892479946 230479391 789743228 517428203 39969703 458092612 507546206 66668464 556861017 332418808 920868094 617364010 346429227 681437939 984006156 52139969 863046584 442135581 309595288 101875094 231374038 657984067 921640584 367616013 279244772 670933286 210207864 34915124 257338129 789971985 726543736 865270447 790485720 70008319 872352646 514092908 553271340 561957496 956994337 957693289 890152793 800230359 76960923 44158132 521052855 812218931 862674707 376379879 301378589 966115563 772800168 490104505 267357 787818036 408547635 824045358 796377244 122994078 455230084 123110892 898234199 519702331 504801729 522005007 171129449 341764821 45786758 141863739 508744959 77229204 546935055 981364534 815054322 396570038 896518844 542717028 337329852 842512907 683284098 20316754 741525788 608491326 510569747 788302045 47402164 938410360 704047328 265309147 115380410 142745743 136136391 649051636 627509175 696835138 39279455 397133779 167915447 484183977 950931882 434684960 927381972 780128110 623153300 711039394 513270730 183535274 580679056 136675553 849492363 698453834 139754425 886454453 681063197 168819059 544034474 109009684 642459344 469743454 507884413 747492106 806314715 990587426 486473570 652448296 431805026 337641833 384718457 239537912 88097198 124360803 287476835 74566768 938987555 8826557 198099118 581070271 983642833 61199990 736404632 962008699 554290407 655123390 556990869 330398947 135721456 670499739 573226809 151136088 662839014 672587151 154275773 670377750 176766708 668458179 532786687 173292883 668863137 968900790 212588461 268402332 483637854 58896626 8447959 498639883 754475763 45101476 86244660 930091381 814100399 930750097 907959795 80837458 248864657 707146746 763970623 448978846 526577065 829844751 400185298 861541182 266567335 68446305 594972496 313943860 390319790 730006327 612808149 96040028 20664027 48353320 169241259 850869066 360316715 304878745 445923232 90679808 116267961 231216492 969680934 361678960 937287368 861446754 837921277 218960436 801102362 207257329 81343954 312824397 642987890 52415276 613279782 412281538 631811073 631497562 783123657 778141659 322788364 778216039 315466713 287788349 532839166 412049970 365355896 717866967 401676215 683341554 608817037 964043807 619098912 506499707 657091114 325025185 358868823 635302476 342094448 400631234 808245552 750517263 878157504 999880612 309315757 262416761 512702789 236460264 211825631 697158643 910869928 650868687 483821075 142695150 485084007 429973918 72053403 254683704 487268202 949826546 367530617 590381595 369163149 851178881 140371057 830543892 630538433 597536910 856021835 846808522 363745969 790213146 458578380 200518803 265833081 160706842 584151000 718298638 840072396 226077957 517220592 474605184 27867944 82510314 823542899 81994678 670862476 796813576 173279633 881045514 519697915 451566275 448290363 102217364 272733207 948230278 448413268 75345296 713437342 314081965 406399520 667191224 740603834 370611915 588656649 602081437 461570374 969146550 287031075 88334332 247348487 439135081 746960468 668544864 287637810 732528622 301101645 939220106 971038337 879653707 493616489 653283371 335368017 987828449 31430739 745203808 310627491 196248756 451992739 835914050 547185185 22684440 707071852 812301254 639549844 860159308 480615487 138343964 648287321 706108633 798384657 847025036 489115809 401459213 659520932 120240210 536027816 559273579 477583123 942264359 744569936 484548454 947927214 826900537 991859848 161809126 455455568 654713338 866980454 552569522 605248846 900016484 956904496 578367423 562565530 970162955 835939355 366452076 525700849 338497722 636154754 845846072 698552089 300071370 530898764 112632054 287678398 891579738 439834044 364751463 673067845 511653845 345358460 344869060 994919600 701742127 103363078 102089766 91800057 260013830 556133473 914137679 869572259 287602843 390796995 694508169 665388021 89443958 863588231 754646833 874322115 84984329 21431864 872671605 650458278 173370409 121069892 514770940 546616864 127078895 706522171 878538134 262888953 745643997 103177223 303322135 806103170 415179364 326442705 216952296 786214179 505025192 256498850 411809870 198436660 570202713 418891740 405070667 186143718 268232095 181396506 244007922 38979040 808312756 274988278 703062127 86745224 93387483 808538072 972655850 740525940 25975052 296867753 680333868 975128663 693902263 554818330 298125126 614093873 387382730 272429369 361823607 649481290 924188516 511160726 557580916 892137231 328407774 449002430 573604903 878179413 644396288 298093286 173259121 428061331 39864147 627759414 205754733 482309442 678968821 609321427 956557787 701967336 82142989 635574173 897708566 442814916 113616639 715324435 395296354 401225472 880195764 6598726 297081183 178825712 740567238 780598991 445240393 407476778 843127641 821664063 770428807 756526630 799247998 840674971 93841494 692723360 221009123 469016012 81537585 582450257 514516275 472368238 54994176 902056508 861116034 959222776 325324276 2383825 157377620 884667199 457618702 397801068 408259287 95974209 960208830 913771905 56758327 520520908 669887747 469189242 358150774 714063188 443077870 654387060 517536908 307359794 548710368 290336102 105240261 166551843 307031952 266949121 749261602 444783914 362797247 375206417 656030192 469696977 480394886 922637430 932531564 204955469 836527760 885083007 855556133 338050997 950837015 816682818 104004701 498844464 269471631 975529693 582463418 490071672 712062496 354332975 735450230 549737430 968479584 58997451 579701469 19983634 398297380 437129296 305612919 644778852 461558525 806204391 222245462 202003437 32802760 51787167 450032743 558435583 450859557 688300996 756397242 719808474 592164847 367463389 867841726 8458465 695300282 718713447 998075060 374567476 21810271 257868289 519024350 650109785 573889683 904371377 950283108 237194309 761482713 171991079 541320819 312216428 847005258 962113136 980508184 811973257 701707923 464842871 128049334 418377833 933097410 14013455 412368470 786266830 551102718 475707764 380205620 981594471 963498274 25572100 953742076 722575488 899925070 985585924 879444940 622000342 769073832 87876454 256585629 191625738 968013615 653555202 29095938 986871184 910528506 757452779 504855319 902407944 441896046 523351489 92984081 293400863 612993351 439822427 316438168 191100760 367987413 194240772 768494466 762967136 945300511 655399809 852645970 105751929 933975875 396280229 18841284 378658283 945122612 895209109 659398133 458781995 937597142 974296054 792856063 890629903 707070049 948230188 106080049 835747842 490640652 967445782 71794429 764374028 551357847 506756950 560068203 683037273 116064022 616994501 19532775 823935308 229055502 638859882 2107916 864073302 691756819 131902579 775231710 70931826 896842735 231937447 479696759 191222999 716113768 532946145 268802323 818567959 174168650 946828366 692942040 890056912 118804302 629488599 504980130 642756099 6636400 138707879 859288611 170913446 710175820 828992098 407187494 905985452 299273406 66432148 149542995 19198538 411346407 338541243 833087653 806717262 541067231 399385207 709523996 504857256 354926455 806747019 939803826 580084687 948269142 897061840 966707558 51154658 924257935 120244004 72462619 170579654 602859616 114396446 988573599 880946659 898274979 874340536 994741191 642251633 859540088 638048116 597170411 527094885 110354206 469068691 125365767 658823689 649046197 956618830 289426682 893002122 283159208 137640602 287029489 998120636 491056239 285189650 229641745 353055506 548532071 13060968 870581161 120851268 622546110 442094930 146805569 830484601 10628138 789741996 607365645 514851704 55188739 51410509 703651332 731037654 390876010 78980263 181639970 260330241 649408144 199316200 857867988 967360750 569686980 68837611 622222726 695633538 554097855 519432284 54262347 775565580 632169773 506497539 177990364 542465004 476378461 634407819 683506151 313240625 908334731 689838647 111760853 153690636 622480873 343840216 785833332 462700667 380087046 220892790 262267591 140303899 223968876 888691559 879148918 711718938 115532694 164904038 365844634 427733502 519022781 924759705 675011649 113810501 103390214 518384067 142123159 226127956 545288322 745812333 130145139 56746600 34728718 866766373 145037884 763937726 838046306 615420537 283780271 226346887 260570654 904029876 826606329 5289499 156150755 974429927 712802841 411897164 132600331 975836983 574702429 897932986 837675512 834716002 175358268 922842083 322440083 911196720 335701133 261680703 340957065 497324876 302414565 931318924 791728665 204811466 660543919 430224565 774186929 484446004 592399873 513539229 384119919 517938541 54961725 554319598 144158246 378981624 229296742 911757857 170813218 900409757 873179900 71928249 635678419 605796829 481458441 417949423 71344379 857881766 383707875 445286128 106391836 82031844 900296856 228507193 528576266 560533116 859813579 639664134 821976583 509825181 477595569 702476979 697977244 830847148 477263117 728330860 777111631 792212280 262032988 911525241 707062385 727740353 904079507 398857745 488525479 995274684 421540837 94262644 73253049 692706130 999823324 884766836 859428840 142057658 371013541 712154484 878526267 584664851 248688079 665983857 990796222 533679529 922959168 103788227 489763815 420047389 616043161 848090469 775599820 303457908 429616957 615102433 437635259 452400774 773618575 521976598 208556850 865050226 4765463 884813505 232435368 423157456 363082464 543396243 935704072 664808921 405031222 324006479 729785153 701741448 943788889 986126951 536890760 35890252 951554642 402481837 176126942 5416965 413787969 79645253 753475444 271091496 961532000 482392026 48845391 492072308 266659889 781422708 466975394 312541674 444468415 240163336 469960129 366216033 962250529 34431257 320043969 490193699 52661922 540861790 117574890 854552519 878845453 784833901 648365572 287167198 549655415 171475174 561628852 739194653 984483370 797280416 153455424 705247635 910040879 96546902 254497663 126396054 847207718 584933244 825774804 362766357 24171711 484626624 181682154 939631421 402665241 2719458 596973693 755837878 763028834 749126228 52159087 905009637 7736575 351946407 323992523 784080342 715826733 720866624 150667504 66434116 219649998 448066131 146980814 749909122 46943508 115893736 949955943 628051970 7024580 783043149 893697446 992958052 282576262 944518595 423222270 200841506 442478044 904907717 382799758 446654681 869965727 401159866 334349921 841660345 893111292 733267597 752534924 657996292 308472268 441942279 825698499 200796430 842900178 578685841 588861687 357916075 302342326 138191159 867899303 33916025 143961342 984359509 431266440 16938599 208660097 413932641 61867878 530214140 158343347 76372406 759144405 284822981 970913892 375623530 944706309 997258841 624515514 983045295 481112657 738515084 143200157 70873681 98499214 712246335 102691230 90380965 517009373 672326141 976866148 782924419 614563236 667379926 716221876 774881968 51003070 318122257 520881059 733220214 35643266 664334581 443831406 687115909 939109310 845452589 362390991 993053834 7059303 442324479 273060784 266204921 940712121 478626733 554615345 183225054 564486611 844404670 237701078 150645191 322733042 257414922 112221886 61808261 756700736 833200951 171513649 734430373 683895437 190183774 636853011 501668998 629507182 68832001 936727512 954065356 636526797 749511787 213097898 868776785 939738181 744800711 689302695 648233450 259784156 773050074 357346785 181084490 338824506 343529241 961094052 221616332 790988367 559490219 943103244 390130480 458550010 876325261 46034820 466597704 284174117 492350620 487952826 807837383 2130382 732837044 341367876 508723213 692360789 999482949 20179559 91030503 548564949 3062741 602732157 859459204 350286347 938074833 224982073 351333764 127840160 769098314 430433103 240665700 46005917 619509902 592658467 33416708 776669943 188887282 166601604 365973039 732795052 112756226 307155533 38049927 775548412 867176151 686134636 497073489 177613114 485958258 73851215 443873304 337080585 732970748 549424674 14067049 498391480 942686078 912417095 733108139 934881113 193696174 712805689 379313410 967852234 694173914 626952247 647729847 772406689 307094902 112153635 606042316 322622410 813204692 873235447 695878266 439299861 308296548 57488983 570447106 653683351 257033537 748849821 316264311 176047562 461115511 426495602 424945831 626362197 157755309 547349695 275789763 144684284 193419912 817554094 608289219 823287916 638321103 250370884 284262260 540973379 43708187 517925481 196911809 181898745 876137346 820662089 856463746 610486422 834698713 281926493 224971281 136369149 118842778 948354677 745997435 117266534 460078076 999593790 516169194 625505689 636599249 143647786 739784897 936746163 622857328 252629600 448229013 582349230 687594057 561766341 867427535 317985323 905743428 381943179 819908681 327973922 461021810 140866232 764550070 502939890 488118788 343891732 815056645 647370894 15300162 277586951 844718791 829376805 623629262 600798972 361343692 298773207 19632793 433719787 414475302 927628428 532193234 415386022 752995158 284151337 451376135 214869092 419383995 783486123 181548534 472900594 563958264 135130375 386038527 788113516 695744776 124604848 494527198 551518891 432051650 284962193 760976275 892787178 646242267 256951025 824995310 659762330 298540801 743840872 125843200 222299867 720707181 658574149 904677125 618252996 34207165 410624551 45504657 534587529 145200295 484781596 360829333 903474103 158697256 865141817 177407199 771032168 812424439 18398578 87942208 584613629 652432867 283636043 629860723 909363474 935594523 265999867 964973373 750462106 198032771 966528179 918442723 726390903 602372991 526482718 901699115 631079885 217156539 291441480 698642429 619366149 393316262 484100834 168232691 797361758 812680169 863008560 773800283 573989240 725229428 848456136 146597301 452682489 193147197 733077758 424154443 395585591 256587706 331093234 210774653 285249669 597903773 764026276 590227729 838011800 852517766 70985237 587596722 109459588 361681320 131684841 140242536 308606820 607862133 140917423 23288560 72286657 519708975 444093653 976421237 453463106 578209784 793803217 743886888 256105757 464638543 49844728 805397476 845203796 571813050 342924044 172711148 171953924 179254301 837928232 159551392 820994534 530302344 477656285 892614245 224347995 473249430 591424579 993103529 703969551 677214183 574223820 765714505 656339850 690306049 360473327 174788256 863667575 795648291 605072346 334773487 222528471 384516641 704568979 123232950 901360573 976365941 252139473 855283703 828206771 484473345 551696596 975419666 621697887 106262747 338687012 662535476 216095786 496660563 845554213 57935794 528749208 455639793 170690429 662375791 218708248 806829915 962810532 541415740 500278710 937893324 206067274 720156119 976276122 265541158 268436057 144219849 132161606 65427990 338564580 209092327 959488825 650702381 207464519 102939090 466341337 462321268 926292715 976428329 955748683 538239234 53388428 911388675 453546520 480387532 479751083 275499294 319103938 516164348 827624902 13600895 260427504 653285612 730677765 483102521 701722832 344449490 30644942 570984841 99482449 101908681 443323171 412565421 902424209 364886279 878014605 175017504 266459752 622689401 232719649 457002455 93193900 45771690 394312347 106195706 584811059 453489921 143094240 621069533 676890630 85607198 372965438 381691028 929035714 114855888 972606230 505770142 712014868 373465974 335635599 205919644 241059953 271938699 661718294 823199289 433805336 252500791 971526293 414196877 208117609 83185871 37531691 211398176 737863212 485501606 695203991 396827126 936976771 967329645 622071731 756878269 739322573 547718782 445176720 65764779 666439317 784379008 981742963 211882941 851468013 930759778 193574114 7342633 858164575 814095248 865684490 498672769 540998115 76364400 419797226 209859625 548633887 395521553 968271953 298785654 790261065 96081869 954577948 637795095 830809882 116645310 909227985 121405985 156309567 899658398 904319527 985984245 752829076 644633040 690704538 378406903 558631119 384206551 345448776 530610362 20292828 876551188 929957429 219017922 149960176 747697919 942201632 372319725 956104292 233330301 151173652 994687890 95843454 739358992 974342694 325101642 569539552 856508854 411327568 727951370 648529383 288807428 567966038 500981159 136625585 765013735 899904089 466979028 836005792 425178724 38890738 126968972 129799210 174497900 971427701 689045369 496442163 55887321 754480949 605201176 452012521