1121
888 272 401 623 746 207 1083 252 84 618 636 1015 174 1156 983 633 630 1254 138 290 877 667 268 458 20 997 687 709 96 1064 999 1293 685 451 634 802 227 834 528 1191 1233 112 1098 887 959 865 155 715 1079 1274 1281 192 390 684 1350 453 705 791 575 1114 311 934 918 828 302 855 949 462 520 1039 1224 150 1301 836 744 1222 1263 90 534 930 337 489 534 906 452 1149 554 312 285 132 1094 117 90 700 782 180 627 1225 120 422 1192 1156 1195 396 568 1176 536 870 723 326 175 887 1132 918 85 718 711 1118 273 103 1264 1352 324 533 1225 1307 921 957 693 597 706 999 873 269 130 125 1319 1319 7 135 489 1118 1225 839 142 525 654 837 1200 352 1215 734 435 758 185 1323 1040 1022 1178 1178 772 367 15 708 1223 1186 1282 657 392 887 1274 1081 1202 175 464 228 33 700 663 566 1130 678 1183 1263 738 640 1311 728 739 1094 1356 1300 1015 540 636 1183 889 1256 740 441 100 1015 1193 30 1166 804 1231 1100 770 1268 1072 655 106 738 988 1133 765 96 237 925 838 1199 906 621 342 169 341 437 903 71 468 205 533 1032 345 1320 498 611 962 576 480 413 1006 1324 614 900 358 774 981 223 848 766 720 222 677 1182 180 204 1348 815 1256 348 1291 1341 153 1255 203 1101 379 752 1086 636 620 421 649 138 1211 29 1285 951 417 817 655 27 322 21 226 498 626 1334 95 89 160 453 1127 546 116 1242 417 602 328 1047 314 809 667 695 1120 173 760 839 146 85 968 355 524 663 1173 42 368 553 1170 62 1168 185 823 1053 1296 1274 721 510 938 983 1093 1245 688 1133 210 194 595 496 1125 906 1028 1180 351 1181 1229 507 169 74 427 386 714 493 993 1211 529 1324 215 1048 598 47 86 895 1215 835 353 305 696 1021 142 760 1088 282 397 756 696 79 683 302 404 742 269 1121 751 1087 1252 669 496 590 1142 207 184 1320 52 60 1035 869 655 574 1031 221 732 1188 123 486 1051 68 1340 668 1230 1087 1067 345 1335 1195 1306 937 1283 135 1332 131 711 1088 1224 148 357 1253 856 317 1109 644 509 1222 1139 1114 1185 1265 236 848 793 548 1274 123 282 1004 772 1179 45 773 227 530 477 625 806 787 539 1123 1141 816 392 1292 280 435 376 615 390 342 327 981 536 986 694 73 344 1022 855 300 640 478 424 406 327 3 171 817 276 928 599 732 422 1154 362 545 213 445 788 660 279 262 451 232 142 437 130 254 910 585 83 649 416 1041 1296 530 594 412 1120 675 958 853 561 739 554 640 14 1068 16 243 1263 156 412 1218 360 468 224 404 67 882 1097 549 175 1152 159 557 539 470 416 740 500 1103 815 976 166 202 969 524 1345 555 318 44 281 829 1147 774 997 706 707 504 913 190 781 795 348 730 856 1232 424 1049 889 781 276 446 1049 403 322 1055 1083 302 695 776 262 712 750 99 604 231 604 658 305 748 1141 436 369 1148 326 1168 875 524 1159 1357 1338 307 1218 1299 36 842 550 222 276 1158 524 79 734 1123 442 1284 740 138 112 216 1067 739 942 941 1223 1132 1265 1216 937 286 522 408 949 631 281 848 1284 801 921 1144 795 1252 210 1261 1241 463 818 148 725 711 1130 371 1188 1088 1047 228 365 615 308 840 1263 954 860 1188 363 840 550 732 86 439 677 1140 502 444 601 440 185 962 199 202 68 281 31 1202 562 386 188 1225 275 821 240 26 237 500 1015 885 268 812 25 1116 301 1067 587 631 142 1257 3 831 775 78 354 1158 327 1144 500 977 401 322 1269 325 617 168 776 82 42 979 223 994 647 15 304 1307 1065 229 679 975 813 1328 140 242 348 1348 1188 11 625 840 1029 57 161 293 687 105 348 991 843 333 180 1278 453 247 1082 722 957 582 888 399 38 1093 1276 878 133 92 1121 809 279 1098 1217 48 791 1050 1172 1301 1132 1253 751 692 607 560 1207 638 182 204 205 404 264 1247 368 589 29 915 748 1168 781 536 751 1136 1276 973 316 223 621 619 884 1286 23 704 1353 1295 1205 1240 263 1140 1092 604 666 81 111 803 1079 808 278 1054 151 356 1348 24 1050 17 420 930 112 761 392 1269 615 757 833 705 548 978 515 864 81 376 941 521 484 580 762 845 622 572 780 952 128 312 908 535 1277 318 364 744 560 490 1317 1220 502 128 222 834 1189 123 57 243 213 723 696 499 1232 971 390 329 1159 201 419 52 1165 829 163 1349 316 788 904 26 1352 1270 396 198 1300 957 1199 1298 1237 1356 458 851 692 1016 225 1198 243 1113 499 984 61 109 1058 647 912 993 752 1175 1332 1333 94 63 259 319 262 764 871 1349 241 945 117 1235 270 271 14 1225 118 498 1217 1140 1058 1011 276 1059 98 724 938 3 221 54 677 1050 729 645 1165 639 711 463 1219 427 313 361 737 275 635 1143 890 453 464 96 1304 215 1058 207 1021 662 64 973 42 196 672 820 763 1018 1012 844 1126 467 461 571 163 904 864 720 256 1034 148 194 789 569 779 1001 289 166 402 198 140 48 1098 953 610 993 790 1200 1177 673 1064 854 1248 677 1325 283 530 425 817 19 1080 271 181 972 224 436 1101 931 405 200 872 419 1280 79 424 1039 1158 733 381 40 1168 1211 169 307 444 834 651 381 47 1165 222 896 82 554 682 407 16 1067 252 588 339 221 275 210 1083 779 1341 1294 804 257 449 753 1143 458 1187 450 870 1230 1117 1221 563 734 1301 1023 19 173 656 1326 548 1079 1240
1219
577552641 718611702 939407717 786689218 721478153 340048449 267609353 48037545 607932301 137142314 851963075 55137658 2662508 552644394 905485196 380643135 611311241 70400217 413778232 114118233 315689240 735987955 801175912 607404168 624843835 163324509 838034916 988843136 579403491 893172468 262358083 282511978 995181100 815896385 753113206 773217703 726818621 93501279 375402528 867019239 980236353 655344466 41343868 640397809 224266399 197010901 570012619 11446908 88380192 347540587 657749205 74701703 141430757 610472632 828060591 807244745 501157552 331738417 913402914 377496802 919606171 190749908 736017281 864898488 872896327 958370163 752836050 121436335 450322514 509346702 150983266 822835749 707685860 627820148 890847845 935801989 330723942 921969867 253200783 727478547 161603919 639019156 985719133 897361184 931178877 283054083 135992744 777175688 77121439 723773147 638248636 259678234 113484019 445091418 44997637 527752498 86132704 98190478 722943237 801940465 87560345 598811474 561778487 589736383 672093801 552799444 459541064 688163652 608974420 676961238 957213700 652273877 408538748 686821560 22884445 745212100 966426894 413479787 753995921 152702967 500140339 718450527 900275818 530801848 132277046 752436742 18730919 561480286 346000704 698700288 213708014 183844688 788767618 885631158 638696750 179123220 92633050 369098612 379863200 739911590 811473327 300277011 71115614 124565759 915211167 799706717 963708534 776120163 245682817 785796341 152264506 692546611 566369262 585802499 304285294 138949456 820634853 556888203 304172874 289140659 134020462 777591823 733995247 408514835 38147881 630946722 529470466 388895494 899383477 338830464 832760104 797105477 893333132 334952567 4647140 4965213 95364225 455107623 586625102 729695411 623658202 559679009 823516828 223670414 330048008 763370891 263675332 614834156 180421552 847968173 178415720 346753543 577434139 726164238 58599413 513680652 44053672 437096860 152896907 482758422 5630975 79454857 514249473 306475664 765617839 341770453 688555769 706661495 652334337 366654626 976539982 686551011 809903788 152648909 661971455 889701088 505975028 737612969 745793237 555819030 352796660 809171338 376657449 681519967 760590994 767858103 58923834 59308533 394602000 596046633 544358769 993885999 17847638 949230845 915925594 762774670 782106655 134216371 902335062 859956325 261556058 264898526 113110939 905313912 622832076 265669905 920647840 729876452 720411114 871452367 421082909 390713731 41318832 596416332 573767590 815704025 535467460 847162653 460261416 910638471 807521370 35281091 911375051 418078123 280965799 253562078 510459706 40254665 349979790 491967531 662281599 267404935 664744713 790237569 671415108 797491393 40327037 949393966 417917803 932086122 238756309 960362911 777021089 119273985 591422464 129950267 788362114 966159133 833300741 454942053 253291085 781104191 123455894 25053814 930021321 11638598 594172480 748367064 795996413 259722112 366689872 236645876 61439169 305481621 122345520 308615872 8612558 925434425 704885905 760932187 417520698 100038625 729114383 154188227 979696238 130245637 67562302 237574843 398074615 864106805 908185639 941298561 531171275 430707870 570054379 250399229 98891234 957263476 219138885 636294803 604238782 92133532 778304806 20937222 12230547 179618920 220834246 463341926 699484333 126914475 868696007 116878407 372718663 988892591 674246395 57799714 524017882 474218773 23390082 111780546 324412829 667885691 925090448 486246645 590078305 544150418 666353383 505674238 426834950 470071964 660518558 646943376 468809688 229405388 170224457 943786871 463499295 5452519 915267955 171467891 332710682 191158492 528383869 39985027 358808052 940538206 391952937 6262091 147422471 698339783 80327686 24803154 854398919 685651283 680374113 366912700 574218955 280548647 912000613 188887298 542641721 769889833 524808934 172575692 597896345 508922044 240773266 311416355 656085020 540557641 36574574 634170163 868448870 234892318 845739710 555815737 818882303 110302452 431418535 614237360 384948569 159727567 560656625 261470011 745933770 683338861 70473768 947891641 430987851 329370542 936716056 972364990 656929532 127942847 500089651 787060101 748482515 146258112 104509083 455501025 720472167 161049608 150220215 848043513 747434369 703100651 454084863 80201074 831820142 963199948 606429859 402821029 654457644 550386683 915631295 602140538 587712008 51783833 393178679 120062107 309284666 9961515 71651286 961292994 10264431 599587080 864285171 751750930 441873868 981279571 292977473 681138757 655655078 396490817 37774454 561618642 614118328 378715222 459044175 683382065 367604277 725107492 241627611 824356996 174345264 454727918 730480045 864975111 459656071 249350392 529199943 409278267 304394407 319845107 25338602 647025223 294512062 931074397 11230830 696182081 214359062 326973604 232627870 252734598 290148935 759040317 166397384 432950323 924917499 977460430 790851099 656143698 485907556 752299001 36892353 445515808 290328594 633887685 30205758 25039294 977210856 748531763 162722312 383263798 961645970 82817240 128184151 399927595 992866732 697735360 762743369 849154576 368677805 291637821 382050892 710415750 252227255 509671411 902172102 323789917 395463094 619614389 441445073 551525352 340385540 502100310 772237108 802787635 484841929 325120978 437136172 34151448 378485538 579732184 710366465 739010213 25006830 363554391 656776899 458412767 887393836 466470200 878196394 151896883 96250146 430194687 739223684 548016074 725223224 255765260 823701471 805332795 888993444 204187598 278064948 522347724 901802931 582444091 289538503 478640622 174865156 878353281 479635162 465950643 600464263 770154734 549856187 923390352 396457443 911428901 192542472 444402324 341184196 143676189 569104824 920862468 544781827 815922245 274212630 866007188 370247152 819926091 654662524 775841393 398124848 147910226 954848757 896059422 950024210 7872328 166994950 606500131 495794629 819591806 695598173 493838958 13302813 568175211 329704401 541832477 760536028 419158939 168452154 577571492 959354521 502846867 678635101 234578525 81871318 895129790 16332614 235304856 302439107 347242353 45959086 997314328 57614398 970581053 135554858 769929973 894773928 466110929 522570330 438096399 771240839 74975236 224943724 188783919 992198173 520005638 671530955 949805165 432534927 62912220 566908616 594810502 843677085 433517458 44720339 294459486 633771234 436698821 970150539 896714147 98196801 802447978 728540929 230320124 340101147 903286291 103519435 89702938 686910115 838106697 510796982 755991630 70469672 880070521 78783232 628759865 401219126 178743923 279365745 162361704 889963683 142868749 520992323 285694455 370893960 981696897 654885371 459730947 807806173 271477148 771139090 403687088 564194771 664318977 903715007 5637162 762692755 467482651 521574284 571567569 27519954 458338790 280024407 901524483 138254532 591912688 643522684 779123288 198410953 453550245 6753816 721322867 839987119 801059777 428769874 42895578 305601447 463281216 318036688 864348067 534904263 416999618 337181680 71705326 66511779 14421485 762529717 796189081 656251979 496561433 643342031 483126000 735187356 497318831 493031062 82238007 25174521 817374001 749675181 129838957 404970165 979605390 175785864 444329793 760542305 762604087 735057894 97439257 562279451 328185655 782824363 245391360 444128282 904555462 962797692 171804059 940431844 313020735 953846781 471042170 242664060 557457930 250963810 742567178 240178588 350422307 526789543 675199975 39947618 894339185 903673899 132123715 791352396 467652423 923908634 121551725 181905590 781348079 413166098 455770167 264028408 23295551 813573608 585569150 140473902 773016308 756762878 51281550 870661793 321351134 415165722 742397915 451377474 464730686 819424655 235460987 95766847 581982788 723445176 242085253 926262000 12571152 874412731 949739211 851437639 321357128 615940839 207646720 346418819 942945372 29686955 177932223 438039668 232832455 187614787 414212197 54611435 904190463 85626436 510298887 124784407 845292782 809334509 468204314 696570265 437917632 546618556 543787967 767272446 645699229 857818005 320498849 358709637 406030975 886310065 166365327 144679483 591006468 456645979 3292362 439346401 716021793 118599959 693894431 767988731 381486757 919020143 664714643 310747247 17396627 997004492 633404866 721671722 228403499 409437055 533124220 976243477 965357020 49110332 541146348 630914181 850290961 899344162 823080230 363283352 483841785 84543787 292803026 442877091 68527161 451341176 99398867 146684869 34592940 739668075 517439491 328720676 858815199 234081122 714848335 289865265 170531136 411610455 923724270 779324841 197319868 647044387 402776606 639015154 292951971 830642583 568934197 284255915 859134471 16398428 17136320 746023669 338283800 332952584 631120081 80542836 999940666 462928135 564737889 538395810 168717800 982275064 563426263 295340250 722394138 744239307 299942323 187507151 486692262 257648871 88347672 867189659 1524970 495889797 660523163 720351105 776163626 426414404 336009688 32623924 174143928 115082245 669977598 359564503 307218885 640492927 787549023 889748418 162501574 244956249 242591230 510234251 382841354 969990118 593052874 111466836 530613250 919136384 348869415 325473981 692377955 991981154 834627193 928163158 47676675 767176693 524430228 682487393 853575988 721473630 348979128 819653975 234712340 286496143 910116932 596368043 157355262 830074295 969763539 955108145 372311970 944373999 468653197 20129337 361122813 247722226 13421486 203164297 36781274 733865978 300541303 370813921 195188793 258106273 620958261 302063536 494655653 309789554 986106033 31984621 129039422 746139346 425509847 566448499 330618480 531989482 627882436 329545703 482038416 877785050 198182562 892640381 339116424 425086976 525180796 688450653 847922858 927294159 202629272 62520687 295920481 304574180 224790206 802267565 923544772 424411647 187958675 421169775 355266523 827786060 720940101 414875320 859291586 866062009 585069802 952161091 250607557 718738688 126982630 72989567 127465358 285532746 347628041 952426940 68146154 154528201 648969525 534268036 832277316 410963403 621657238 52282190 557353019 91486987 174679522 122121512 276222235 29776663 581663259 356584078 690178418 806150291 521862210 457366068 834613402 882655276 611018902 637752949 145292078 587894266 132773235 589300261 830043081 917315799 425969647 932011259 132610986 19238849 39053708 387419889 806632262 441608984 479172733 923006782 840655510 207688259 131210731 452514406 629688834 268122389 724291546 158850189 415175574 387408804 263323524 908100875 223267833 765239535 876112991 417075668 329971164 839534626 253821541 113065146 116287346 236964865 627539863 849491525 600700966 466435919 3204874 976386610 206775818 832045924 597424991 670918162 775629839 514120864 304317968 733887264 739627494 473139638 640854565 737646131 74101877 357310814 228676734 973066373 859777658 370001696 731480980 776546005 287811697 240204170 897836740 101273286 913879189 19819569 345585651 67306626 244400052 708587667 922542611 967768549 437284056 964287727 252022493 761900257 780220040 623489707 818677615 228572632 548232890 674376196 833858164 776834590 331983290 133796053 562574738 441265370 32376696 15669677 64445913 195434198 61159682 885690424 924393694 582537759 538325999 456264962 838416747 93951211 155803305 956597532 475805817 719251701 177829518 922752242 852833426 980748930 985131526 240467397 209319430 357724027 362824984 186065431 488798120 930064146 605974923 607003540 227421190 758293960 97150847 816940949 951424510 957683669 472872581 645271987 296602392 56775222 198216655 16179492 974977354 679831551 108787299 172285804 881745181 438307192 526755510 579204998 215174245 376437213 312902022 321877993 570327351 295146979 987509832 49689913 934344703 494341689 571615878 327622921 859051472 758165124 944913860 977186256 483627968 964566315 260583680 946691527 769833903 175462179 335918662 329239289 14278266 443445875 450868740 916218985 172150265 188695699