1000 192279220 156648746 154396385 640494892 528756313 434883275 318065816 264440383 659789618 608119380 648104885 725454493 696703871 543030428 663661241 890791532 108201616 428505485 322953840 119811886 691103781 306647414 549862302 176916720 909058872 455464665 307270852 584469329 722629343 875317524 629938577 244419357 781214571 196670271 304620505 633084215 842804669 567530398 381873604 560028831 7218487 861789187 144376610 625456810 780877709 589558486 134166194 414950797 721407802 553010676 955308712 381588618 132249152 739990895 349655325 541586881 148171213 459480021 458194371 711527041 805750859 225659487 923622443 616919641 541627396 189845339 545052260 705924883 701326769 360797562 153907111 153703899 312119365 610379669 633051912 179752937 356035805 857066211 510023590 487449327 911192542 522937781 366865480 175671835 3720977 958798378 537811759 487222100 451715495 514312095 913636469 134561869 695564572 532291996 942581882 651125280 371623643 124409048 63074409 599149591 243222914 423151882 252728018 259733480 643176870 401033745 139381337 251320508 149124068 414594572 331487170 269144629 189437147 248342017 963352506 406539487 845833861 755591984 896411912 346209707 599986363 192576280 339470265 91311827 674221023 82572050 432342320 906953259 996236456 898717035 293935164 823871257 241618061 426188561 552250086 602446372 326439606 36819591 716162336 182538448 877980489 234609344 970639970 96912085 154071710 720041811 241584077 888321423 204059421 444486813 306061338 405953440 718697236 185635311 544659197 175477373 385632116 74114210 281221796 749035961 69575117 403681060 477587442 276294863 344958619 247221529 256653851 88799827 390143235 215677770 69615948 421663553 829251359 473970283 477181978 395005915 204518014 819349760 65949542 849289624 779931867 351133755 458419083 60835260 97550049 14347776 568484556 889658732 259645750 554047063 633917839 869082276 25145201 819042066 236424238 62605193 647411618 963213706 550125446 754369251 97791696 503316297 263982839 622206695 583095008 633551381 82619261 28565500 11547032 546769679 794174955 544258177 607157917 974478438 105432268 44562565 650759971 725160370 205744623 56560140 163959670 788812019 759517420 870450851 786197016 332668941 280884396 896616999 354325646 78199529 380937488 27828123 792547135 344979557 606529987 854248606 694655265 98844756 675361364 540932137 720653471 638568586 259188592 477025351 199659791 923181962 932329452 657848015 785316592 876288044 568202699 711859965 835360370 264697884 888333017 729753828 973849297 368415358 195626384 789440908 599511876 6405002 933416558 56060136 326810208 692565033 898701472 315946986 911332404 784951415 556831370 37285994 754591964 89276725 738593187 993973135 784935039 181217910 778665739 994337227 332058127 762456138 24400815 386891485 904050172 182407666 636003294 108423721 375403884 843008606 967930133 163815973 457948520 638332659 600592575 963917028 156722720 359729359 560390518 235226468 568069676 797782114 239098409 685400425 510134242 577467058 50978805 752028766 164889533 217280532 710088559 522973051 850448894 695807095 512732494 744621933 765043644 5572720 749446521 370336434 988285031 981229809 180999313 787390630 687572860 811799398 791821787 162447801 552007489 767002402 673284106 246463401 802742189 157822377 155385500 806266307 219727203 683743955 593913332 353321718 367144078 404043219 95990639 981617024 76965016 480476399 888827418 996998471 451741021 505811216 175718445 336525214 727121309 700275844 466233564 300170578 450550347 983917278 806337609 574319765 862578965 528527440 80741175 433952228 948356384 483602917 110481351 360912431 716293558 408395904 975980920 201310303 856922974 866803513 952671463 379464049 19340824 131379260 118844757 727214231 593398052 332310973 660656054 563298068 965893603 826781249 169725639 623612468 142394566 509185529 613787528 889856071 889200712 454786811 115186977 192402415 56222204 263923656 390546877 953655006 216442068 217298607 919899058 843904262 903158973 20051664 485987173 741840500 30052410 482019313 853044666 225880642 348694202 778235198 258285782 384092381 866266221 882003969 364669393 443811759 990976337 256754480 191813219 906988660 500055849 942895403 655120522 746453207 881011222 643999571 344763659 856823541 776963780 292684135 854968296 499252687 766554125 290065703 3996941 576853977 871885397 742091261 834056713 156134330 828218675 177743881 393648807 283659587 253754843 187850027 863335112 7836256 54524481 637801774 33448391 777909554 119086713 774437681 566315031 549859515 937142966 72805572 535999829 106597600 705738352 537686293 991633662 698553903 186304138 770200706 993970424 860312486 438703962 332779128 115921192 851511173 447963124 313740650 460526403 684368943 100922947 398047100 573149774 416271313 459698572 197822959 682461439 972237693 310667100 325551420 120649948 481833528 134347178 214392111 8142693 337442283 284108799 593105380 370738803 705438259 352988444 270146933 58754954 555701637 462029673 452459592 308797554 443252150 873227113 338522360 377179609 702718479 911859661 876435283 717014585 279290298 111602234 260788208 601004930 906480973 805247349 322621783 678137338 564670127 797337845 621334574 99678642 355399365 400446956 710870139 37116960 210364435 800081944 313741471 253001775 792937040 164309298 455246050 887096772 141317753 814946362 957356140 481685113 750342074 883786334 869032218 50127022 660073647 76052831 292917825 10574670 48693591 526945681 714900352 44232029 202084007 166197938 95995741 341945489 399061487 78143285 669578165 924924837 136431238 189986488 751880184 943934692 874965297 357525861 382249883 688272446 510008719 911794181 397712909 855849113 322380959 928083339 961481039 362386984 992059188 499432460 598315996 799730843 805105450 539543511 642981871 374565666 412114383 808810446 775163486 738962012 821298553 567831822 149471019 329079065 521221433 175469752 425710284 435891352 474348189 940665860 306488085 117257541 631443539 30515320 624824685 950287212 220526650 150080690 559167220 458600897 379655988 89467028 105922509 281689702 547580917 553349954 363463479 350131284 634609869 646336729 709278192 814749953 162810809 685184955 463222523 902127716 268301282 131047254 842900649 589121210 14832332 629898749 67277966 175309577 658555204 58123355 354151062 558792931 903896941 876514640 501212619 816465456 228127237 931074841 841137513 287120195 795895897 98268740 785104745 555610858 43082330 769864306 704357620 484656339 41403223 858756493 602689028 493083361 239342128 754317102 594272498 562926441 622267958 548145967 83150380 249394874 401767148 754862686 471122517 222925575 257098826 167725286 510581431 563067321 358072894 76774585 871200175 205432410 94407660 872259936 307561716 744265362 799945400 739415999 315925136 473326366 662932794 3826792 255007174 859919832 695629691 424439047 723459843 757796288 716355288 940797767 420975804 176738588 683565708 964135096 503007917 246969222 603970731 91326270 128335809 636545951 906169139 237116437 507430597 512501528 501500896 365970653 815551893 118295098 559555237 140358821 488892788 935591390 967161677 263465866 547365544 521766573 40228036 634044716 211921936 199098652 958157530 273501231 773263914 349059615 151384940 180494173 693133521 383924189 746293521 1130742 412483340 884733789 511944621 56794724 529905378 626671571 474523999 523498634 260253481 128828207 246629295 509065323 78061515 899450083 127160113 399243106 34823060 757581439 265610778 783720083 81741852 983957578 547027558 128461669 400855852 841963269 763522948 524609981 133063463 752000660 721315492 436160969 372798560 418357542 750932767 472002399 100787293 368396442 427657485 515971496 206273974 631373248 823903731 240236285 717183311 712740500 325855784 123161506 435949679 755687436 469802856 608964295 265367081 714937308 383022514 921343022 125761063 658765598 150219478 708222101 957042182 374499414 656830068 85581494 277882372 730059918 927797442 502521247 330780039 878737294 480260771 724336724 567479254 294997728 906201314 158428823 199662339 954855701 426005214 632497704 382550400 888216226 516605481 303479737 188114073 863896784 52703792 231739503 351945716 274277599 365861468 785704148 665905944 517633951 932595006 992962367 723393018 359186438 770561548 273035650 202871127 477390879 767972791 34365977 550386264 805731742 493679141 786266654 272831913 443745087 217035605 2449443 286650748 59468504 936140025 139310064 919981633 553417748 937472592 362256448 514707657 583510187 331953246 157262574 542057154 241844986 121364544 8955615 685640886 553472622 154689880 654393434 497122871 728248665 2348133 827652050 872841175 835498479 194119012 995991089 282779140 162377124 513212966 139801025 242294288 241344683 256724567 791479582 764123104 808450545 734213392 92167353 295491098 696086078 464540046 115285157 671417336 765370976 668988066 984432325 415821703 332380990 261912944 367831824 523454974 582729419 583057157 103794002 984764357 311862225 270998498 669033509 739516186 761574441 666159800 945173597 982323061 534921492 826283849 530039637 396845001 367781535 888044245 112401955 629876537 420436935 139184680 637157194 606049421 703785711 976149807 912533890 922537902 569280730 954422487 819817875 465308629 476233342 584463897 848290570 553683157 456101256 856202925 989781586 693396102 439027134 856124868 123194261 584805911 320208434 756008603 373924152 929798062 677015562 421018259 50368590 623572338 203940996 103057027 239198737 508049638 104342504 310853923 113252986 944635098 135164746 513269418 918552949 410981780 385895600 722031859 583110435 543667217 841421379 238361442 223700714 890286355 401834256 692531391 67493542 11842636 713645329 581971736 976546505 95049090 980640035 743284384 207837745 993167071 209005719 857385467 194979602 573390966 595010493 74073361 295475939 418002823 506585160 332911132 972518853 866206243 167976045 303138913 884720018 721224868 591394765 553671443 218631294 370788288 990547098 228560741 58650734 118176142 47201282 146594371 70553137 439715590 718726700 414262154 592933914 739758408 619795593 435019887 512935103 898747808 728501409 299352457 630371684 290141715 421869537 920169714 437738228 162405767 77599928 646451263 88752540 395793380 492544840 214849554 228943378 343654681 827983491 275912146 957359628 309540280 593371425 294340140 294402597 968501955 521608227 760744527 797074140 915885649 977601398 409242716 538733908 297066999 487859750 683929096 636425184 194012695 667620249 845663344 116804548 53190452 159241784 117849961 314481380 299687377 243293724 388065038 260221331 464442668 502695402 784194755 638463959 960584701 430109397 29960196 847099297 466371140 7255278 83629504 397721664 500988902 255576464 979826457 93001057 704852404 242382124 936827179 514670153 830716438 834970520 163631245 950668349 842668116 657897257 16452949 46520422 819290384 998602071 198926195 311209298 355659362 12032775 17912803 803747911 473675354 760840503 338698318 569342678 58754980 22308373 846921918 872013298 366373593 613003307 952388421 848991234 156105967 366478532 493100254 346496303 114555290 639691010 74625394 754440002 263711709 248991088 288370039 151566900 973978218 696903947 433095979 386213578 131623774 592869589 423122791 159898472 64813047 113659185 163792828 25015857 336523722 984007223 823671606 679280113 129669267 136987917 675164475 754349827 733537686 372704445 224587174 756698955 892509733 865133510 722047263 994685969 678352534 392290290 157403067 278667564 233824669 857313198 506983765 610609597 245978547 57378031 196697484 684451868 730717648 568390239 579476017 938494857 366104980 868518932 954445890 895316965 728405043 818475985 281173735 843816722 722031908 269305089 76671054 424233076 631414868 627537733 977021060 730527662 910873619 174722859 816879693 194854216 25537709 17415336 710804834 442014602 16897257 701100030 188960039 842611355 702451878 593791950 668586235 212367895 727056238 183343740 295644895 269894354 451181442 845929042 514900194 836900558 165956398 617892720 966563741 842580909 649917179 769501529 186631874 730129552 175579231 838585159 166154426 753938858 216703115 660986678 502741377 958132876 885747762 820781494 619530247 843712362 615782715 617326581 535578089 945424168 676515154 339805572 771136768 413371084 135180954 868153135 281168886 661733163 475686484 629145088 553638544 777928744 51226323 436078199 725741166 298959993 797289400 379600 93521364 292971909 450876698 481186980 422615122 62877798 307389038 678564187 179123682 615825315 214089692 115353634 632101163 755114849 803748059 987107433 264039154 596583530 448368492 271047783 124994222 46952281 882846377 268697650 334155404 839782563 119002173 438604084 797723825 848980692 140611927 211696930 206301252 669747987 61880419 112886438 557525751 798913345 938780069 887021661 759217004 346471545 223351514 745734155 404493577 79125178 196132277 998498175 423235045 296208284 171047238 289357191 378877136 692524873 777984013 882580395 38750166 812091265 845955344 246240803 774063449 520714356 282137368 659726788 922719145 151340284 525536600 847909051 327142707 681682131 584498241 720198896 723137805 808787322 473408786 935413898 580170547 410670778 716252067 206153712 868306792 394463539 542409637 845005514 757429698 346524801 664699983 324983323 860373217 892505337 757306633 289593880 147609453 624614534 227052669 297901387 617351809 542344996 214856123 343448931 569056563 161627713 692806751 497984914 605711720 98512744 914446916 769716981 355980693 651910263 492354658 342672554 487623276 413475644 293931297 211486159 940458705 206114387 628302654 782869044 938442083 174872770 60933775 615517880 624975272 720386982 933975310 825396220 335893376 261831920 525998014 701297184 275516956 419304197 616733872 52170814 627859164 848987243 685740522 990894776 747941135 389090035 133160457 351368484 185684018 412853329 879330265 48309296 980772434 810043261 686513512 847132258 820611463 721538709 934885803 987531325 261931833 389991370 635753907 436433939 325399854 280466471 773462767 804168104 382123957 792345868 146951962 705986348 724247821 612159518 369568749 248223203 14521719 894164465 458411097 358568647 807295782 911630786 537119633 137333637 126433355 752464429 992465133 838638087 865014307 802873804 371967167 611177239 147186191 107509812 143795144 368551537 912629603 952814340 174286295 790084208 213921270 951406765 20167108 172864267 758435080 540343901 880689083 424421644 775485426 623928128 215979634 624251249 884890811 354677746 59996599 83781221 698181412 910628517 321330858 958206756 423814263 180067043 967626138 955700463 8697446 988264498 73029146 453400683 895551935 634815714 800168515 241283440 583577526 381307482 987505463 221545347 65065116 701315856 792266878 526723413 158344372 116458906 70636284 41493372 655601891 433121421 575476650 864225355 369696083 873016060 139749234 216039508 650970632 328733331 206806194 577201641 172161618 12966835 12972153 82717522 947965864 926185494 139459877 590614411 983188553 47876368 86281229 494645627 806805168 971430608 644568767 982284936 495312828 515528177 284738276 675841425 109722287 764375987 897614144 496190978 16773534 279060941 825538559 900505544 635161099 863658280 827630001 590101170 278267073 310407379 12504623 973607832 347441887 890431003 447895843 715913106 564359282 849478393 9734490 22232684 128356032 326611991 418782709 302494873 614711112 9190168 213464123 311752217 206716260 682724777 490757921 966380012 294934454 893575380 76400962 478739726 291742984 343946943 198189793 904267069 476578410 360703165 969432512 834623711 708024940 340393867 48835148 40741114 958965085 915226784 238176982 562569207 606472617 613591992 676833983 650387527 921745731 533471613 362176921 813538812 641763178 548596897 437633171 561454977 457897064 275003453 401703828 856109036 736974357 173308920 88561270 640065035 755828912 979655181 286634328 579989015 133855450 178630833 602713305 310103603 515722731 213564592 49451501 807549652 554891236 602449452 383781161 743228844 733609650 609481339 52745782 635197740 395675398 236261432 437687401 400245116 550011573 339365525 624686376 778047029 264308828 546209414 22006893 946807350 332436642 332323826 446948496 963700320 760921403 63247980 27936023 428594393 32337900 849269316 701462380 194996280 958232179 857032393 637512137 858113877 660991114 109427014 42846403 88447237 415667958 118896138 568944327 386185816 739913589 109856310 42891463 895664984 380499820 195271694 624672390 218836065 93200009 766861752 754858785 401163349 258927082 43474109 406474910 596987305 597224177 125955447 75010496 185750524 960073157 771301759 328026492 313499367 820239687 336612840 647543364 266373729 182219185 805203222 79422217 986984582 234122405 609219617 720235532 229654216 234740949 100265362 611299397 962993122 605810359 857180457 679584947 588036195 270366678 638815740 481242804 11425096 346037575 910075946 531409926 33601594 236900824 439853041 519917056 414261109 673692989 646660653 212403589 382947468 143402417 60075011 183558669 971285502 400633676 651059787 541241760 960775328 680392361 814544865 797841398 832725789 698118699 140916152 976213974 427009612 415813750 38258005 38666095 936939322 275005614 652485179 804139024 429334208 744161872 254885339 372312932 504612776 158226292 143354293 656687483 465093473 339661813 48484981 801994915 185682476 21912377 108904306 77678616 995907892 357712170 860828217 327792961 191946834 712444496 34266354 118660875 368195810 351234597 446600784 894873790 433077910 600343934 844668198 844649080 272416531 824833061 777976253 218211790 401705327 985430749 319682048 489365748 853987246 625807734 222663098 344295376 226053942 635214987 331850016 761629800 607110829 99128190 823734783 662470658 521226208 777503450 611316961 313931437 180399077 439663556 794060124 781767899 33244119 167650408 766771992 874470318 388793988 622328764 375059427 161474666 7614490 578654927 479181691 707076025 845961552 250234865 380076552 995253533 612437394 692623546 847063690 908199966 415271389 741117139 601380123 798922392 19140029 1869279 410488553 622117272 186777511 334517816 327411920 271891120 241493339 638835968 828852272 826438188 308576533 321730512 558283668 95334676 648031044 981758535 269917684 31761010 821052914 978662588 307083739 233414231 846606305 355347740 85756438 137214569 110454403 847686446 410209230 101281484 695672755 704062873 198410001 673430734 859682893 754137461 93725081 105560103 166898435 737927447 994493183 651768624 561762117 190344761 345231088 831057368 812264344 494220169 937974245 995450649 710525545 555083006 193455281 205915644 70387972 732085355 9463002 616501479 710765807 704316133 842011624 218307925 54475697 619027603 942774447 228967030 210107271 93957338 853836180 50815249 243046010 531785124 611189756 84670723 779340056 132902880 40143866 565598975 949969114 768636922 56117027 426857489 435054497 983193390 280122816 891226689 958529371 314823253 152464545 827768594 11735852 75875807 595195418 359053834 641211079 678914603 986129225 56961016 716883594 265356613 477145716 768453397 997496381 958534419 870823184 231095802 194475701 16696012 686703230 222123223 152050572 652697321 963776351 400353968 710412443 872946714 391131971 48485842 948556485 741174092 360582588 544455134 315064541 626036890 424455069 69648874 100155046 447922489 107474494 416917576 364737759 875201343 177259386 471749792 670078009 719691499 681627807 982182998 496184545 655296289 707867104 855784246 540694566 264205521 177562124 825851456 764776232 499582749 976573945 600299891 426283881 634913344 759168821 499436518 895503739 394337771 213882878 67663340 564588950 285233912 644053804 366007475 733342521 63434044 537302960 217056407 622851484 850318426 575299121 75500992 971700904 650776893 858813924 221213840 374957843 581994316 468058437 794768116 606414794 997260700 542930829 831461899 117114657 760246011 878386703 129740158 907239966 348418370 707319353 319168624 535592922 284435571 912422083 288587148 548681057 740982548 158895897 521159982 904091806 349511506 217164624 58954891 250813827 729368782 561040669 260359984 704603068 427684149 851699318 63160391 128378301 917715617 36796688 197572810 406434453 840357969 146542610 942362586 25211035 945521666 386981120 327820365 633298192 72794521 821283234 989392136 165908402 877036107 131925502 845582790 571862989 827481980 668422112 183245555 685567651 63977248 208594457 156064378 537888603 122284735 489907607 358875110 141245073 727236552 93131511 570718519 930868725 398280138 831545341 201070868 995623305 873528234 934918520 78631190 68959785 694162753 833858716 158727299 589656659 922354522 306327671 71814337 634942164 65152990 858181650 189319538 695904169 500066211 748118488 447077763 803972592 510002482 74211282 370197000 214395789 963803717 630444598 593704785 977875422 825124436 755112858 135900604 835610234 726870640 33114225 605814853 640365419 421734312 82959890 781082834 974946386 895986500 830820565 986064832 796675683 437206837 453220282 786726813 512968005 903086305 792303083 103472356 458001309 138870011 962673061 575173331 795137525 657468418 910223186 53732469 762239230 290896887 277166964 41050058 548198883 375212910 747860994 626019194 133541285 556023236 75820900 957014064 942183043 813671801 976943110 228880398 437771624 633114241 897861289 498500194 429044985 338545805 688028033 227138939 89309658 210064188 491015317 260051905 442199771 181598061 571815588 476987597 584272772 249405084 206713411 75474776 679871880 689789284 746267157 960651813 220910642 325418408 886189602 762510390 597219043 791710692 192075097 981232664 339712951 527619617 694362333 805101343 253534476 535483323 236959004 119792095 511481506 394488440 845297822 670580916 555689827 854421359 94888515 333857420 707891683 581946879 903264712 473166781 221840413 485367242 366057222 140956356 633999294 251400074 822452043 32918378 724607386 512202889 910657113 561678130 617872884 576562179 358719226 454007105 918236279 250619331 490052021 792534798 808670417 831564609 487019359 112501186 568063906 126150602 816141834 705528700 939050259 561830636 861899644 104486634 484992855 853492995 254438827 967150183 987834306 327776719 429742793 660442691 947721430 688189071 276189868 803287902 338167305 520149801 103665997 703434501 556359701 682825286 177468585 615083610 413100269 303540605 64100816 487245538 929665323 183851236 760272450 424838734 52824035 57493413 24010253 69558311 754305444 756866605 500108958 190870668 984693710 614152076 633615947 586407998 124220639 106726411 237091737 730821058 925182306 768154851 629093361 988262884 158730013 718440882 531312042 964216733 745196098 257852065 706563691 726794602 438702597 236478286 906062218 775072244 561964544 562793124 277687582 440552942 635143872 379611401 68047144 16795680 902879496 592950875 825534319 469878543 346292953 743515493 5635052 929086994 491140244 300146521 335017800 483805524 452025396 75656482 772479341 394358450 833278598 6825079 855102836 785681964 918775631 757767395 448966870 378561613 559019276 814022819 851523925 130394652 793546333 519432631 384705209 503914054 343636747 123403461 213604276 737616984 133998623 782903204 996632284 268172933 618870397 482102793 495242629 899122721 913815325 904667726 208876332 475228309 907496439 11465588 779782565 298100279 216976177 459371056 101235600 933748195 728393029 717061927 327134202 449896370 627005692 261853422 89777698 657128095 281430882 285047664 382748780 709339965 404523117 488979837 684480796 292185796 662293882 468397114 823700268 994914513 700370794 688459959 887066735 632037135 421657763 325640783 255240048 921740708 448538777 73004178 957681330 139875624 684005607 17165630 491322359 170933626 420514419 349296214 30388279 194261805 665984946 53378740 648804955 914313876 538222973 785703007 806806071 337531178 181885237 775219348 793640933 670371714 151394749 500081837 645508534 403339132 601775452 290104428 105539842 794737526 129266158 32066799 892179613 220207207 674745179 579887738 988972648 207202068 711239517 255900685 60206325 252975685 39850958 441910668 656404887 277915673 229240962 465895570 352408934 71997079 630588791 921580466 80461670 169278617 747079927 979524069 817800710 774392420 408832934 342660749 770402499 817687566 593822073 384277884 737542264 912174136 434805 931506846 2900938 604959050 690414612 432370194 750340433 4081086 734024096 353661889 3287576 721187185 111357504 811277175 503582329 866761084 444828839 207925065 516476125 56194769 868847141 965672499 717766817 447581580 483769161 45751153 560413438 103871617 203118800 568718957 524152167 163639554 388004190 112894584 171340079 514676813 998515793 331156413 810122628 319128399 651605350 182463194 454917656 310960564 504408525 452734382 763127378 433551246 791656691 871750093 947852308 871432653 861914512 670601681 443173862 559661504 120668278 457028871 539804340 355392608 813044769 853653165 785858028 531011363 491831820 434928780 10585623 364570228 108499454 768335269 390940146 670077352 939635018 851026022 63928747 911355536 717974471 686565900 24994363 169559156 838758497 113539691 701524131 452843196 306517104 927150680 183488959 663293072 145193624 561044691 276171289 867111487 454824761 334126802 388215110 507080766 49509352 606964670 928737002 186130415 207776538 609283825 692728289 994925431 710264010 745759064 51259772 33386988 487883819 813050598 314243734 247718842 743296835 199536215 692257112 580229435 692396923 428601802 710044432 599552048 697203806 715624653 593524416 959987325 840478672 631923313 163634932 516495554 46619087 358877226 317420479 926754490 707981374 790379424 1086259 982635782 536267247 639654084 786081730 432359366 563337557 134329633 160703236 260030160 622390539 323252355 469904963 585689452 189692411 615971942 484058391 108824836 577919787 122809257 781306374 731910486 272261340 137589656 426792291 159663440 857392345 985235484 713295507 822530825 151506998 424432804 745003249 311790421 645576222 753912765 289449808 631630497 828518978 320276444 826729655 276608867 627630589 829587299 116962942 544222631 234104064 601249036 628995865 41006424 13912867 276886952 931936826 954169442 481816911 877207461 494623629 646285023 842140960 150741507 752795243 149248066 568679781 140576444 91097958 663526146 384176848 795624887 59748338 66637748 568301535 909046749 589690135 486359632 570530252 972158419 92416987 816183271 774658723 879349075 735695417 666441968 476979423 1229297 134571516 353043898 308624822 868688782 998645191 336056857 803809759 667351696 689708341 394958414 24765518 629576110 748786894 22487605 796761668 670214314 543149102 436246461 234089077 82265977 865503881 254175948 846265769 141972221 936199619 579717632 879555035 672022430 533533411 81846650 889579134 452369485 737015636 918025246 88643385 447367071 636581096 764796017 294163136 638613260 7389083 254454101 541846097 160776227 196398600 970063448 323779197 692206419 158442951 460647910 519574976 315107711 148318208 431489350 42606450 389581324 234391074 723976752 685839943 607714798 729606236 621893463 910050816 246675523 427894904 429493995 199890308 10786993 461766409 165697195 299071753 133245819 867711404 166310635 457460404 877805252 943574139 662299343 140369537 27285280 406088908 720915880 795522885 463913408 534100946 198056601 66377241 905581878 91675250 355714531 800958036 690257288 203557201 733701733 169501974 56648096 278064812 291632849 980100981 868679710 691056012 4814835 199464271 758802989 299033069 734304280 982069372 736019780 6213079 339777072 15866329 42738215 769872195 829928683 560659986 477309353 90408559 799651342 429294317 224384624 157499620 12525002 326222707 385134797 842093267 209590934 179621163 100274279 580113221 640309629 267118209 962231825 236349111 715427786 54109951 60515563 143415799 96221120 194447875 546176739 123134279 692795405 230320633 984220295 518414454 689284164 495210241 802401674 942848456 625475786 105508217 327646668 223931166 640916818 524993678 693576590 168782527 387216511 537474191 232526912 610909154 213305188 802068314 424969851 93871771 114378152 894383872 764035086 431156476 369981743 346677602 78510473 635744030 381327485 723613162 743540963 968945972 3267247 468011281 319123553 803499890 74488686 389357851 500257181 836282173 169102211 697266316 549021950 982986920 321207594 379681600 292328472 231971779 550588718 225101229 115594326 899691905 289446263 206785430 492569382 94548799 730512648 225653804 271219311 272697923 553541642 549906263 312862367 460983507 39407813 323759144 124412610 381067910 390454369 936399692 714328682 190400506 805621112 394605101 908768976 336443696 895152558 21330956 624648321 564421439 209330230 73021895 693837 960597979 587618508 123408274 453326564 349454776 748366232 626153778 646818877 939976923 337082124 394132875 543174198 666397523 126538075 224101436 838241681 562635730 837527527 830797940 160566910 161135347 912716424 993325437 29138877 900049154 558584684 668927536 378781428 342806139 166387493 446916080 952445830 661676443 719400512 625920448 66970766 994353542 789771919 161486641 68628370 881718445 92934352 464249583 782933102 675275374 547713479 35677512 708092065 788709528 849896456 114371301 43978408 99743163 105925220 114010465 927994780 829501366 790853404 293644402 540730575 874591994 806908696 778452119 492784256 407975552 705282764 896329396 612168676 384580447 324362166 859535470 498090252 902330347 685305220 67891624 304600785 649213125 662426163 848083645 763721573 871775684 700001485 914330249 240385320 532320412 635084770 968402308 419204851 157600074 572949841 235734824 648043394 890300778 761662379 347493758 744209558