1508
134491993 216354220 491335292 343810419 848113190 263344345 876395005 549049141 387161158 780742252 215207182 674706031 64567430 515883143 722371489 215964857 371533379 929781631 72602142 7421187 498656130 42545499 882116490 733548240 770955282 665877431 714286850 875470712 792643346 34061209 892794884 591701914 933200402 288590290 300963846 331207650 778724573 56687070 533488870 219786192 232806443 143064073 568796456 421511509 537545970 542292306 555972337 345332687 624778506 807093457 772029244 269592018 849263502 586491950 361886805 133822269 688643574 390209932 508137324 326213938 807013370 877725409 545031247 712005810 240484025 409786146 955568152 680578298 30802731 190598328 313753623 209533257 463251493 639111958 535958779 984423468 554407561 789634567 113329124 565397618 503111165 975782160 342563183 778863766 297257206 80898544 439110865 638721960 965724137 950342021 648672591 366838548 187721804 697645142 705068623 356340207 62255172 654061525 369288029 871540527 540479643 432271255 267836293 466066363 151248227 81654018 64180831 117243962 386675577 65675003 503161580 767987037 725032422 589161396 489331553 960990659 959217207 897235943 912273941 746201249 567904777 630682401 440953794 158367722 938302302 141804349 916389012 80899879 461829734 918007149 666065247 134636357 942490656 656290706 717261250 148559612 537997988 640517745 799480555 722676151 359814807 881715658 528771997 851510254 375093308 869625877 128640490 52685434 298630783 192288573 644118711 656395323 271270393 842354462 304032184 125478134 500758560 684378070 963851979 89881720 555687076 345522630 64658105 718910070 13420822 834424651 580444235 387920805 198478579 472800490 200536178 900235075 565314753 703408338 814855362 5222167 120271572 848966539 191979397 609218521 114701388 818902062 110319069 665202573 583973553 921184675 618013370 917348074 37771046 504325802 695015848 213686239 673556606 543574456 988907258 178034772 525479883 794776357 497131971 52806609 620199560 252938635 152936952 700569853 11519566 863650314 297284281 725891723 838955596 849073826 494552923 182717813 877197202 645422764 133491848 89618559 31663133 211294240 14677239 457267329 2169043 10411978 264724394 169621383 653598929 7682115 387277586 153433671 952537096 371862300 545112753 645806932 488039944 59560497 989530160 233418143 964514191 513081572 483007807 689855134 424004595 143635988 305281171 547444968 356541524 433314529 580393278 866744960 799756133 718383784 352900048 431102780 381300383 792301269 601074667 20162117 23675044 520659376 251845172 921456088 238842306 650673544 690915612 702490451 85221145 160994300 786175976 268392581 810838740 990951197 399528995 128928425 427443935 989720086 234321635 206434003 884758996 332343448 390983802 976079253 51047413 265630234 436904363 393472285 550481705 402352477 529996582 30716934 208696441 479066176 720466463 612449656 50586321 233786820 133179865 651765785 464551046 950503628 749325634 307079511 163214833 221606328 994428413 115167642 945918238 435386334 936875907 959820036 785328010 458244783 626347041 45396116 213580970 593161447 851268922 102484413 424781229 426509448 911112367 584459334 812355014 21490383 142769898 17220500 889221951 812167694 512079956 591244020 584126603 399036393 713860683 152261158 987341033 630766125 31201207 628763786 615092650 807625224 292185534 85310841 491759719 463444554 737473273 418953704 384263947 960947710 987731415 318891249 626485149 82927449 472250304 792194929 135018652 94799198 303502617 347545266 119908849 574313446 575083057 531138416 975743839 942664474 131221831 709327580 914191624 878475576 65927568 540282532 462135062 284327248 673082889 452012147 715992484 792163294 136772213 871374929 607482443 662097488 570220498 170078903 648457152 338996821 160373324 286476257 230514783 252864842 45972125 917729154 942913574 16360646 289364537 889408984 961749307 229216129 990293618 253757669 423369895 740828567 941680253 443351844 924277126 389788059 918009254 134864387 473702065 709577085 842935509 432547539 2619811 2159401 145038791 784102214 514120932 56192284 109979147 240942447 929580302 852409362 128313072 959002595 827929976 5477090 499361923 985145629 206262433 428509913 756065853 344005595 275588784 371183426 486169609 684294695 204724144 794651175 845007533 466113384 341401303 547203135 375044020 323340272 495871755 355625541 57059998 838513728 954449284 888037286 118771810 974628042 208448011 908985010 88606525 480251381 943384217 415662994 494139187 248406500 764867214 78773383 606352507 833009800 90265431 381723722 416251795 918164352 373039140 565438006 799683987 768640211 895987900 913482205 531933186 957077005 717944884 938088163 154633545 796312842 265451344 77328484 204899264 665124780 900981011 911288087 302712156 417447166 119959074 337314488 242135280 853180283 807827383 545129932 68565242 679482732 582896718 190577571 659786307 607294449 218916254 161165734 836428818 44874216 478096799 377359859 940405000 820247506 807537497 699665760 299448252 797088303 346114188 325223949 985144238 183043993 233656853 115026646 80945260 690102725 248918704 817088458 707078352 64967773 960232715 302261356 691402886 526286325 288150575 821265983 21179532 961480656 780580495 510455242 61544454 331420029 959052493 80694456 301658200 67274893 944953742 723775749 544823656 789164614 287383176 734755197 536489929 351836598 610514151 52366353 72498059 536876911 668812953 944099519 654389091 90081775 133358356 654442681 63634316 468739019 286249015 787521284 192322588 141806559 304040306 637193508 862203262 495837993 676152738 20480106 863200463 80529334 7057032 171233116 970302588 88508582 727553800 192836808 940055506 170824957 504098517 686819307 171345235 187545217 183986085 238478330 948321768 771019936 636744171 13034071 377405765 810137006 612593279 203407341 839662359 278859401 192899191 594663959 99781204 688613108 988819083 942157701 208947939 999154181 784470345 815914657 770112236 691574425 899868492 846631795 817939631 498715867 740659337 214154318 534435106 495051325 114050199 537915722 110159883 960991129 483695031 587713049 5321080 865615124 824864506 685565479 278398712 234900597 695942939 733037140 496913394 839215169 59543398 30477373 64580249 497750093 168423937 429256028 179691564 195573013 442842758 580437904 52835781 645336405 943627859 123724978 767059753 638762727 531235075 941997486 369069929 592336546 127158904 220386834 220991449 667995124 110300864 960415335 63569392 263140523 168740456 103694482 311107111 106129289 540399664 214412546 524861631 805906372 950227705 899719269 302543868 970455802 827568779 316475747 893703709 992160853 855754415 403606538 126666631 721156264 866759800 639912861 120035430 347849401 402426988 57563117 197937377 124412622 773301692 643674398 367853253 839113753 527435048 838333591 583575803 309569203 434018322 949620148 50681409 858470369 45472147 760987930 61920598 929459321 358171708 50739409 898946220 990955936 449123867 220868034 914475015 31000844 152512014 37751621 590027165 976071294 769798467 773421226 552108635 256035816 620679224 418606238 497660746 548689275 381240149 461226790 720046442 160876703 694875192 587050365 847640399 709996426 881634431 78800083 930677698 593736450 300174576 864558013 823554571 675900207 983635808 861050037 17005536 52126354 693853209 242541669 892777318 308213682 589230334 35219501 293790464 167106946 991078297 621022728 223011286 636763410 22972897 721909159 902560757 211105402 102684777 481802064 494489112 535727903 768054140 19649343 545202855 352534768 715252225 980402429 10302306 345665152 160972648 489349709 41135809 863820823 537914449 247278702 256880703 91534871 744478128 305737346 333217402 650773823 728404409 563202598 496318904 684635578 40814370 617910110 492981899 361495696 238394886 78726158 763093318 83016762 998103852 352427444 676629380 379399897 184363418 33301220 528225695 89522938 428180006 103438246 45155421 816716841 204226068 58325100 712153306 505517664 718283576 209091854 55333869 393676481 319211722 767945989 683235947 510380263 26609775 522086495 877383437 75037686 789134583 914476119 917341920 956549413 642277229 818097003 452823925 443960412 767709371 684486778 479044479 996111746 982975572 434962382 733732554 34456162 152374131 987733046 543304279 151004996 938688360 235396020 437132136 438762236 659525811 997140848 275605314 865036062 191746235 786038991 498817612 515515253 674773209 442642539 121846573 544100199 868123555 316750484 97550644 767527301 855906139 916160345 381708132 36608554 399967013 635529761 668974099 467559428 580696282 93081914 892197482 657853395 935406901 701178833 168033370 321856392 112340288 763276276 104695014 293405202 25421953 756630320 668609970 310566843 719142410 507628138 362997005 446636779 986863000 841263920 214318921 978766933 248417185 992906707 127072225 280244310 409508707 331999784 421713760 573114961 275403200 774219829 889764316 304708706 257599232 174311228 260439689 804187830 296535814 619359313 755306655 601797994 119904714 314649836 746869979 781235366 242108896 292711363 212441267 376245408 876366040 553816791 412584499 110803804 263726292 994493886 292079024 463523974 226699128 143604821 878913422 357874434 405014777 409886147 273751162 64819967 140702316 777601847 154987 276930615 40684675 37767244 417414417 829598456 54946215 825901101 48063175 335170276 84250171 254812623 856030257 280333568 978315661 830116839 692602930 36360801 479528473 489014267 404631182 478190017 431794279 861640918 689687081 397774148 418785004 607280707 717405623 461866639 404046051 50922728 193478809 321717026 458098446 822406680 364870280 132605627 814089254 308588885 585669272 739808324 418149918 922987964 239961813 894897294 885777116 254117917 100439875 717635577 565516348 581764489 801546338 745582738 925560227 562782174 37738013 752772941 320807565 942659806 794475863 999039702 172196265 148965469 204840607 936626021 895183742 164046819 901294177 592933086 178404755 116815841 721253541 136166944 618510526 661232080 972372720 65916534 136164590 902878432 400543833 960794177 68035797 731749132 892080546 871044150 571502268 828520898 782490204 981785088 745473387 384568788 741781411 934624919 478100668 887853527 535412467 128852974 997229438 168662584 528859 307906677 375917065 883781817 556032812 214035382 807380175 457156342 88749226 487618417 959278606 307768026 312758136 364209490 21635142 417181505 987343780 244926701 643184970 812686775 767193787 153374975 870087062 327270708 596201065 46617693 832263150 314403391 6994272 365524593 94178164 703083865 485259765 882996886 793202662 533077427 631180478 699750802 423931546 683936792 820065802 65526396 906030997 107435707 789840862 893420625 239069287 764281455 684999709 481679427 202246134 744612565 805365792 208836609 560038820 904501179 801714477 996414074 920987355 725515131 932895096 779304800 37471556 393800165 358325798 435527633 966848158 636073256 864633639 557533623 729612922 699866719 292113183 680494335 842018524 471854415 875597056 899142331 586603491 53693442 548036156 705602741 220908415 67825973 351812523 307266045 556378734 643693766 852655358 181613725 151766090 636203171 266847661 249087162 804561816 214275757 734882533 617764643 310659954 239566245 104151951 500254096 559365128 731005040 241876801 832835727 611089102 570011243 43493265 818115288 849632258 674481312 362460309 932759001 803609750 280314656 443321142 603997622 748227142 907906631 481713033 675475572 394567096 799962968 774114823 430227607 349523298 242161579 583792334 325753754 99624904 97831973 990873141 662751548 276216048 702631490 98099628 15251418 896400614 889336732 529831460 132518083 871734169 275760530 251261789 709030901 37178881 486024451 637528883 291854167 308646751 222922052 805765393 775543538 411283090 30285415 550863068 249752630 504629317 444877394 128704962 383424526 954253457 336038676 538500943 105891501 63075520 673258386 547006116 490633904 814940685 568299010 645166950 883821260 537454007 292876366 353232007 102117000 338662331 411396887 774671529 782461901 608596768 718561681 16791886 821856501 411692871 241996929 106774471 172855127 20287218 18797912 891342511 971605250 801963411 78925169 584365829 30573105 679458982 866691989 73279347 852681229 230329515 67088625 557719125 627195602 978420582 653937590 958699903 508736821 581538121 90558792 320511823 752503734 964639031 792731422 259929784 381482562 675956403 329251699 108237029 973331696 201486047 974647175 912648135 380569989 240013413 295082007 268971333 934268329 152566053 303150215 698227625 841554225 746467993 557816695 424758280 191911949 565287339 254474073 640457696 558720797 726934698 432982773 808413300 688084931 994226255 371674629 735373180 398258771 257487436 627232591 968654252 430320444 307038827 483850732 945946770 563967751 139028579 569910304 576706279 524132012 955331831 735440395 58258871 910268612 750800318 348241807 904875865 748008066 201616683 648997335 601379622 512145042 903374748 406644597 485369860 573695581 32192973 689758782 429778897 526636734 765566789 959438903 831171981 230461010 779600647 847496523 192691449 115191369 577388893 759184041 985519933 456796362 856557078 600514202 999867920 613826188 662451173 583267725 51111057 31008234 690755611 876740746 56240784 609087313 416763051 749735031 197238378 666190068 41274570 919412361 574570347 333816738 602516809 444141750 831644069 557008590 976780673 253019612 88603151 445180751 1506837 543933411 501868921 831026766 254349700 226508091 933116774 504649256 414219283 528595208 189347299 203342626 884110038 443983317 876004413 949905026 484634417 292644843 981946470 887103667 426740252 443374456 683192151 765641926 767740224 842815513 921132476 978820551 603902477 244710846 226866471 326486329 485287030 596500623 700550993 32919373 366872242 561846220 893471382 822817310 955965072 528724983 885753987 207189979 898929828 995052352 937101476 832336344 751017785 753035502 460380633 440935591 731407644 443288492 1755431 907420321 55753602 79554399 521047401 877386788 64239053 861939293 694923225 651099482 153243345 112968528 76003426 213736533 870207506 9907612 702082923 604654082 877204319 198115572 771325129 168538687 871539321 941571455 364515261 523201743 521007851 703887011 629843964 91595366 485697223 683355697 659127057 468370893 677115148 710227152 374455187 326106903 349101266 598015522 989283246 308537826 188653401 337166515 1111202 551088617 539885941 610157883 265651531 941318948 483357719 741990187 762983612 262077644 885402899 592660066 755061191 262529087 372209340 776163667 922049056 610770175 647672525 821395656 2157992 366037671 113002038 878122416 339791612 417815794 43477810 982077663 746660194 438935703 107815852 20144158 177078609 344257725 536624374 989153489 300658037 972989331 217047270 289449705 715494330 725720558 30725165 622337744 15556922 547339382 917816342 899927911 486681577 462284985