1037
150644678 587802059 504985530 340639568 112692885 258363760 110892482 817447798 254134275 493209996 744390435 490135759 550126318 941319196 264818607 455598231 854630928 796576316 307121544 231776832 97052617 63463097 905993694 653095432 55843984 801635067 270507558 194813655 238735226 341348211 797772322 319656865 102387611 62586405 519180196 721157686 908122661 278334910 706450881 934152351 520667542 544064893 117223164 937791171 434720730 590695821 543755629 997688238 816059642 57795549 549184466 648499409 25894463 935463855 195014575 608000874 811363468 689017217 710420093 787583737 199928389 753974381 547991569 304179324 250792201 670755962 745252223 4701549 974144779 978294409 558313183 468019345 682689373 40448272 60023001 89090404 230083058 484246980 71700482 109150847 349514449 508205071 117372969 331559171 891858595 326195053 743541455 76698475 375804410 1033221 309621697 879176349 84987945 289068155 534561176 867610814 158112810 275761946 432316619 590937442 158267841 22208841 109436346 148133091 413678697 29973408 843338433 602853928 349024340 196650632 904639632 881563663 259899447 20597619 943673176 472111303 325122979 872663017 787431846 911010129 364714877 351975436 661097523 315571477 866041337 312370973 52891391 987002024 36175705 138999424 778339781 255672562 102767640 983903052 806149195 124950525 70051144 943229331 852205772 117603676 761420067 895336597 157452392 702445056 293150998 253397497 886902313 411630290 729351768 519863160 842021716 349404401 826855710 323990857 221897658 777555271 925977120 747227380 539501813 111098192 759713003 487470492 863724182 200357905 177847415 266516985 731371420 791652618 901158087 331079907 435933419 73159565 303144824 457377180 434298407 71438889 198748949 887443618 778908213 732698067 751253441 338234739 910957510 248641046 797422177 809453303 297234384 295986562 786513522 197142986 290186384 259657342 108620956 600300868 288015110 869024153 4244525 100261481 939195626 87576823 77472674 179664570 872915128 301887614 113378334 961372087 386583826 687439681 896289895 712643079 299244894 23301603 589510075 248112028 153870141 604973224 650771327 151472478 600837577 897605570 459551600 151409362 650823057 268900597 276931717 291661280 919054285 363391643 62385613 816351934 935095226 495365804 622644450 963627109 518663230 799798287 985157495 836010808 510619013 205962590 151898837 776643265 118348563 756746187 63627350 863724046 423981900 527392401 654082726 223296251 6951854 714034853 8613204 764396415 651759268 71764634 194409636 408291513 821301511 16750071 92526325 894436607 8980146 261106151 354647813 146471480 484047397 317282451 583083228 617847895 209685089 749853748 911854151 898444491 63076193 232543789 923675210 687409434 728396585 230218394 722323434 256666502 76127281 166004375 428541942 517873388 297007029 494830739 838318797 873230025 238895032 462151385 301483703 894210463 328492297 416495226 841676945 534390618 478866590 316851236 933966634 18731578 327329772 664674240 849776481 803542230 13478302 638230251 513287398 318940493 248509931 768439346 468587858 753620947 29119360 493604257 814265074 496645541 549255291 284625397 50225730 400109139 910258880 100240444 69638038 226876485 235266020 698715514 302164681 164290955 889054468 595614495 894643995 473649564 555281335 378972943 699264542 843193030 528045535 704960947 168562266 219842234 365030863 867463060 20184810 915372711 615693082 172383740 481791453 697291172 420270353 330321423 34542260 608420341 947372907 646863658 967270277 263114625 131070499 618557133 696338098 57466313 236427004 198417380 364053103 408292045 476747703 607720042 739962554 381851317 763972435 581744749 742096485 797112367 2211712 423478203 756849276 144579908 113621508 368927100 310511324 391830683 339667784 663133801 599756482 512284639 397467 951676674 698689203 236226345 650636045 899123997 916005920 86273721 813633782 396168757 47620691 428384239 163240023 829873437 761411013 695878121 574719629 733066092 436507558 323353204 636104731 202885287 427739007 936022656 252994903 478570535 853389632 849664981 226987032 731913485 480792539 40433107 454005529 18601764 824538206 920405311 70997213 115786668 138063660 232510196 810978464 946776989 127128123 387925855 554552346 307145416 636141808 996937372 925434791 333203719 718890791 125687845 190687326 77890412 121764658 344036165 566824340 227125867 873568141 465797547 740831932 802661562 517082389 422557066 593342234 664005196 802143784 387849407 598857565 415518897 765399383 42726796 783168172 297732230 42511961 621395393 923391151 822184949 782983916 469410412 695929999 378720978 125951610 279057093 983469793 829977220 301554181 980091503 216962602 841299161 49263364 235111192 816179057 938207355 82014401 976221909 943464192 214252261 597141786 358613484 506903543 177367110 104685772 129023601 196701958 97059510 636747686 202498060 124869260 84996013 90084183 77081838 507545792 941327531 282361157 113974048 829808442 54102673 44392989 260507738 555919983 979065313 770099979 943801420 745226058 354804345 53325095 797298144 187158784 565344354 935854028 654791879 424347640 408757467 260489335 566631854 758172007 121707665 711933739 569157048 904136493 31704914 931583467 420954606 770595978 737419269 806601543 331692086 575908447 779323976 726584664 963708224 789636526 500199431 428982325 165261124 290027678 963295400 533650376 223056192 204448957 754315925 412827672 72147446 933061865 598573534 85643580 344193659 952929162 55192622 690509452 18592532 738285229 359697419 981571144 17883646 372239223 618674438 7926617 705727791 619798804 261380814 396951998 574572227 859299611 391792863 841941243 294833264 798857201 717006166 867614760 26603266 189696116 263959966 253932865 706065463 357018226 826149478 526506937 609349784 23043021 698141452 545773152 689013161 983594944 565605531 582943764 291253531 506451162 846252554 958449387 144938411 867841482 768625363 359247840 868530003 23051920 956642623 384651488 89107005 498339598 811441941 258914860 446163131 357213364 103541758 996264753 463748676 809617363 555278770 848368526 693340422 228967454 115740993 141133289 604516898 86746532 569382818 207767328 318675536 77901402 990142764 881064 692054511 163493905 707766662 256374581 242156211 854358206 358085999 558555794 994636658 906302161 577913498 933915071 111825952 216236307 817052079 762826834 828678068 206870324 690393329 451139161 822953254 127312391 535909386 62488348 133551893 524953777 946529182 871677816 927324654 484772148 208214182 228024750 58968148 412221301 919241834 379455643 661713532 42495180 488370232 274824278 630228324 226030566 539481445 324704686 840428 670347648 955165354 912657330 723784836 127742163 93064543 751225872 889100500 457275381 677365851 282856406 114640818 406205025 120257287 23934839 358530319 877438291 543506553 237558338 841792381 718453090 499964721 926735255 772719224 698528526 309291167 933691368 814380906 384673446 239174535 265282915 947452692 341969037 197535602 410856267 257279899 348823618 904095168 713524690 425863667 770979709 188784429 706519502 535613221 249379459 699027844 888358579 66973816 53463619 47024598 22341164 308367208 800448160 741528912 717352651 171862402 482327247 543432359 221220816 902941586 547806592 938121567 582196574 852003683 126824428 589470714 105595256 330772708 567558098 653111075 524698375 186361386 918118873 516492830 415339383 398810366 734639941 338518596 671689627 237728259 443824916 836397918 702223766 619158745 714649610 935409562 615384177 232666754 281736688 574183221 809592124 793257377 227515030 371868556 765984561 552705206 85540485 767870202 121198851 4115396 637835763 725754260 517776839 721037088 568675236 334647562 536131089 618039715 934038451 87607873 927866182 398840792 306885496 108884817 436999988 495127600 437395068 257696472 690720829 283392311 201139040 105695122 367575285 495647107 268270525 870435604 62475708 148953941 855370822 99014359 758839469 861791251 755487840 390609812 528126937 301771759 154140778 820453059 187206354 29233645 41995204 611511024 166328723 92405964 255953472 657781870 568022144 48352885 92921594 781167519 272541603 706953985 336875656 785100136 640403605 723861929 534640264 712050063 796754476 410851066 143894343 764341694 432129578 156695015 411085275 423436188 991382973 201986889 424957067 838857210 292261671 23219245 241275912 744222178 15652587 6425703 217278808 809350980 727615970 880407265 19492320 896577844 800025576 475226433 533321699 914052453 695309258 851033014 627707280 350595733 309318489 308909855 212189355 638389611 198702274 654859522 20885092 831368838 837323702 401843861 50729913 10478475 921752447 619243177 588316296 271779808 219688740 425100107 305734264 512529519 205231917 896058775 735916759 267942727 893518576 648429265 533703031 185704897 324798336 399452891 668021553 977655434 400310597 22207382 285483380 351770908 673999876 462418266 315941235 809871349 566933072 790513572 881297080 433348240 716928071 924592665 388752682 226236470 591514080 146546277 766509534 349739338 955258646 444741269 451743711 242348646 454619829 611614859 206274019 770774229 544889763 158232922 892856408 429593682 252330506 733431518 557043299 281404138 850557524 324305996 408814617 829515280 739007346 217757409 289182685 476253580 525245471 791138897 254644312 898877666 495927521 848685600 389963836 23724566 541376187 724386084 949754260 952125167 742364715 840191614 818257491 696995729 465230172 644156040 592766227 259185304 338609965 106458882 883252027 155308956 112520432 627452761 933350070 357893168 44616343 526473405 691936950 67316782 349217362 345781501 942596033 70408273 45118485 427870587 722889050 386561132 258574781 694111543 380333993 89460487 478398135 886969648 617435125 651602073 979530769 298953673 490157977 811721615 428460846 635505107 458799249 264246970 303895879 941479779 503330778 977181656 590604757 961079384 715506705 949814967 810631456 339416161 912906032 114586806 989909745 853906220 780713913 513308594 785163143 349990318 435414990 879828604 831863956 632741741 604777655 368024966 900877922 988879462 824392394 296400574 704034337 575433674 834954737 609714399 185689973 500699223 274670960 880605218 600542349 862409696 973703794 774641887 61060124