A = [
1180417 1247378 28948481 836573 804574 774264 793075 787116 795575 776437 790235 862734 931868 979566 1077461 1147666 1186186 1217690 1204866 1136945 933889 875201 796570 654700 687566 994616 1000834 1060994 1378530 1377793 1408344 1428605 1443538 1479099 1482827 1487406 1477159 1471805 1467897 1460843 1467446 1468466 1472669 1480316 1474896 1473060 1469205 1458374 1446914 1442812 1443788 1440709 1443375 1445664 1441920 1439771 1433154 1425899 1421750 1409348 1409099 1407227 1405931 1404478 1409728 1401865 1398497 1394856 1385779 1378072 1377457 1376730 1371793 1375872 1373811 1369895 1371762 1366785 1360358 1354868 1352853 1348990 1346546 1345011 1345157 1343300 1340532 1333873 1334218 1324305 1322523 1317561 1317026 1313385 1313191 1313415 1312908 1309778 1303580 1300712 1297228 1292275 1288181 1287138 1284452 1285686 1284522 1278687 1278236 1275019 1269455 1264748 1261216 1259174 1254756 1257711 1254507 1253082 1253135 1246538 1240371 1239228 1233470 1228259 1229893 1228776 1222911 1224791 1220005 1214991 1215222 1209213 1202531 1200130 1197601 1197364 1195158 1194947 1190705 1185296 1182698 1178084 1174924 1173038 1168675 1169435 1163660 1162195 1157925 1157584 1153095 1152242 1145335 1141238 1138741 1133464 1132615 1132920 1126834 1125203 1127091 1119565 1116253 1112307 1108946 1103660 1103341 1100454 1097804 1095488 1092938 1087593 1084965 1082744 1077507 1072154 1069676 1067985 1065279 1060943 1060518 1053985 1052363 1048676 1045357 1040251 1038528 1036024 1032853 1030754 1026633 1024398 1022263 1017312 1014782 1011195 1007708 1005008 1000151 1000229 994859 992996 993435 988756 981823 978457 976870 974185 970837 965746 964267 961105 957201 955515 953105 947758 943118 939912 937595 935996 932843 931557 925715 922792 920752 914253 914517 911184 907428 906211 898720 896336 893166 891547 887604 884912 880774 879156 874657 871317 870656 868360 862010 860399 855751 852382 849941 846250 843533 838247 835784 834457 828953 827146 821682 819803 815415 815023 810836 808295 804841 797645 796404 791749 788722 787493 783977 777695 776513 773151 770759 767720 764495 760270 756570 752771 752309 747895 745228 738846 736461 729084 727365 723449 720198 719766 715497 712601 706422 704808 703385 697817 694421 690250 687655 684133 679650 676945 673798 669317 668781 662591 660754 654627 651351 647225 644971 641270 638060 635116 631479 627534 622544 619166 614303 611921 607176 603688 600801 598117 593828 588045 586538 580575 577329 572384 569589 565341 562622 557952 555244 549337 546213 543163 538046 536365 532271 530279 525763 520872 517966 513450 511248 505771 502125 497421 494154 490150 486454 482838 479814 475580 471644 468052 464262 459783 457728 453162 447161 447041 441530 439662 436657 431388 428055 423999 420258 415953 412382 407998 404780 402458 399901 395608 392812 388768 386175 382204 378186 375742 372239 368947 365411 362571 356543 354683 352660 347313 343295 339764 335992 334812 329777 327387 325438 321547 317502 314354 309526 307556 304878 301550 299295 295144 292069 290261 286518 283010 279849 278055 274349 270824 268063 264171 262210 258772 255718 253136 249808 246576 243455 241254 239274 235753 234401 229620 227395 225063 223438 221375 217725 215250 212595 210788 207827 205505 202411 200851 197320 195081 193176 190223 187643 185742 182531 181836 179276 177352 175325 173226 170557 168279 166950 164747 162122 160505 158179 155306 153672 152027 149937 148038 146288 144553 142966 141084 138336 137474 134856 132143 130514 129998 127491 126073 123854 121388 121332 119264 117434 115841 114098 112312 111212 109754 107817 106422 105079 103380 102602 101265 99428 98229 96328 95775 93585 93382 91546 90265 88446 87404 86937 85427 83518 81934 82008 80442 78696 78045 76907 75714 74833 73869 72625 71307 71131 69453 69097 67893 66307 65730 65124 64168 62870 61380 60788 60348 59523 58097 57412 56671 55869 54786 54309 53487 52475 52009 51490 51016 50267 48918 48104 47900 47198 46693 45563 45101 45012 43530 43275 42451 41953 41219 40730 39948 39351 38884 38229 37651 37390 36560 36252 35843 35168 34682 34345 34011 32550 32928 32461 32034 31505 30923 30521 30245 29809 29152 28625 28542 27706 27616 27626 26724 26394 26170 26202 25200 25074 24791 24539 24240 23433 23534 22999 23053 22411 22344 22054 21436 21424 20815 21009 20340 20266 19880 19892 19366 19102 18770 18611 18330 18152 17788 17632 17290 17303 17115 16706 16608 16487 16135 15939 15649 15424 15514 15080 14897 14525 14475 14352 14289 14042 14001 13805 13642 13612 13239 13203 13024 12646 12910 12609 12390 12248 11876 11872 11805 11654 11624 11421 11265 11309 11111 10971 11000 10744 10410 10534 10261 10031 10441 10151 9769 9934 9763 9615 9388 9569 9225 8974 8939 8808 8831 8762 8648 8488 8500 8372 8491 8280 8174 8015 7975 8188 7869 7556 7713 7730 7529 7444 7448 7394 7418 7126 7294 7227 7154 7181 7120 6875 6818 6652 6887 6629 6511 6637 6461 6563 6599 6377 6229 6177 6071 6135 6028 5975 5891 5935 5678 5876 5847 5600 5692 5596 5610 5708 5616 5541 5431 5329 5432 5376 5472 5439 5302 5064 5092 5105 5056 5243 5055 5019 4967 4980 4822 4621 4709 4736 4709 4567 4686 4723 4631 4623 4558 4735 4543 4500 4630 4487 4506 4515 4443 4185 4189 4236 4130 4045 4141 4108 4032 4104 3944 3930 3835 4012 3917 3960 3962 3981 3973 4026 3826 3821 3817 3937 3849 3730 3673 3660 3753 3872 3570 3579 3676 3570 3686 3605 3720 3657 3515 3649 3479 3533 3488 3278 3313 3386 3288 3298 3404 3322 3304 3290 3213 3163 3325 3264 3429 3226 3338 3112 3332 3170 3125 3133 3036 3131 3007 3134 3134 3118 3029 3160 3144 3017 3011 3047 2974 2932 2915 2897 2875 2884 2826 2876 2811 2876 2825 2868 2743 2845 2773 2832 2771 2861 2818 2928 2695 2622 2746 2683 2712 2703 2816 2614 2821 2686 2756 2660 2645 2766 2581 2636 2631 2535 2714 2672 2578 2678 2545 2565 2523 2547 2490 2561 2541 2478 2476 2557 2595 2563 2533 2490 2533 2481 2442 2403 2415 2453 2377 2503 2367 2425 2403 2413 2420 2447 2451 2384 2434 2306 2286 2219 2327 2287 2248 2253 2298 2266 2273 2282 2304 2201 2255 2204 2108 2235 2157 2080 2091 2120 2026 2040 2076 2080 2135 2124 2036 2026 2086 2069 2047 2016 2021 2054 2014 2134 1989 2043 2028 1997 1934 1998 1956 1964 1975 1983 1912 1917 1898 1796 1799 1961 1845 1879 1857 1848 1877 1878 1830 1802 1872 1897 1886 1791 1667 1759 1773 1796 1758 1774 1828 1729 1880 1760 1837 1733 1677 1749 1692 1662 1751 1711 1690 1699 1641 1574 1623 1575 1629 1637 1636 1600 1541 1513 1821 1636 1609 1693 1618 1627 1563 1640 1623 1576 1568 1551 1618 1510 1599 1571 1496 1539 1536 1550 1491 1413 1510 1532 1483 1483 1424 1537 1392 1385 1458 1434 1579 1350 1388 1367 1450 1396 1388 1356 1438 1278 1258 1298 1293 1314 1283 1326 1293 1372 1310 1299 1340 1282 1271 1316 1308 1268 1329 1302 1259 1296 1252 1284 1247 1222 1268 1244 1288 1201 1281 1203 1273 1219 1260 1309 1306 1244 1277 1247 1291 1206 1272 1200 1183 1278 1279 1243 1170 1192 1191 1142 1256 1179 1172 1153 1162 1180 1189 1247 1173 1145 1143 1159 1124 1105 1218 1143 1110 1197 1150 1100 1058 1145 1088 1149 1083 1165 1141 1165 1117 1111 1140 1130 1112 1081 1079 1118 1069 1079 1109 1070 1054 982 1005 997 1089 1094 1110 1019 1047 1065 994 983 1060 968 978 988 985 951 975 1019 938 981 979 937 992 951 1008 1057 989 1009 924 979 1001 957 1037 1062 1023 978 1068 987 959 905 1009 987 894 951 954 933 921 943 1001 992 903 927 985 963 904 961 948 915 909 946 905 881 893 893 891 909 864 868 803 813 815 847 853 843 823 871 838 843 851 880 873 858 931 898 814 813 912 850 901 872 833 843 845 812 856 821 836 854 758 823 800 872 841 798 794 792 846 731 795 794 807 782 786 748 720 731 789 742 747 724 801 757 701 725 715 775 742 694 762 688 737 779 779 746 758 743 740 765 681 709 676 703 698 666 637 624 666 712 678 729 680 660 627 633 640 710 693 641 664 713 687 671 643 643 631 599 619 560 617 655 607 600 558 568 572 584 601 586 642 551 567 579 565 523 551 545 584 571 568 488 491 562 501 632 565 524 537 515 448 537 466 469 484 539 467 474 505 503 511 486 527 571 528 501 474 527 553 495 465 531 511 504 518 527 507 489 482 482 443 511 571 468 484 501 628 509 485 467 480 483 500 488 495 459 475 507 532 512 490 546 456 504 502 463 482 496 473 522 467 511 517 493 515 459 465 492 492 507 505 508 519 527 501 480 477 454 487 509 481 496 452 488 448 463 434 457 448 456 416 442 427 430 436 457 448 454 419 452 388 448 450 422 428 403 439 411 397 442 371 399 429 470 447 389 415 415 411 406 415 407 401 383 419 426 398 394 375 440 418 417 388 448 386 381 405 406 356 360 376 361 402 372 373 373 373 406 350 359 372 382 373 421 367 361 377 354 317 374 325 303 349 389 338 357 370 361 354 328 373 364 357 371 337 346 339 368 345 331 473 351 375 326 352 307 326 351 341 355 321 311 332 345 383 414 350 321 355 310 310 326 302 343 363 342 347 320 310 329 324 303 293 330 353 341 338 351 332 347 330 338 340 325 340 313 316 301 333 323 300 313 326 308 320 314 327 314 318 341 357 264 267 287 317 287 326 288 250 265 249 269 244 237 283 274 274 256 248 247 258 265 271 280 250 241 256 255 256 280 244 262 239 292 294 297 270 282 268 296 276 279 280 235 236 252 268 293 248 271 299 259 267 247 274 259 275 268 249 244 243 250 250 245 236 252 245 220 245 253 245 239 251 264 251 278 229 259 235 271 252 274 241 267 268 242 246 266 239 202 243 251 245 258 271 252 251 233 230 245 257 231 268 220 254 224 230 256 256 239 220 206 221 236 252 260 226 193 244 210 238 191 224 209 234 226 233 237 222 259 244 259 220 225 221 212 226 216 193 207 237 240 222 212 208 236 237 211 207 230 205 218 208 209 195 232 218 201 194 190 251 210 192 185 250 239 220 236 216 203 218 228 256 237 209 235 209 214 216 196 226 224 229 219 212 213 236 185 186 224 242 217 218 208 233 228 225 197 216 224 214 237 212 201 215 197 205 214 183 182 198 192 165 200 176 151 195 183 205 192 179 204 183 191 156 161 178 173 198 165 171 195 178 163 163 131 140 167 153 156 168 160 188 180 217 179 171 169 169 168 166 161 175 182 173 163 175 170 173 191 157 157 168 184 175 153 169 162 162 144 128 154 163 184 160 161 139 166 150 152 165 152 143 131 143 150 165 145 182 165 150 147 143 163 157 163 168 139 163 139 191 169 157 152 161 130 134 159 135 136 153 150 142 161 150 134 153 136 118 130 163 123 154 153 154 143 148 126 126 139 104 114 129 135 141 125 110 139 147 131 105 134 136 136 121 108 115 101 105 123 135 126 122 131 115 122 107 111 118 96 132 102 103 104 134 134 121 119 123 123 122 122 147 114 116 123 94 118 118 119 116 112 97 112 133 119 120 132 126 107 131 127 121 134 120 149 156 122 136 109 121 145 127 123 128 120 141 120 131 128 125 142 121 123 126 124 117 103 111 121 94 127 130 
];
B = [
0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 125196 105119 20077
 252413 219838 32575
 288848 209997 78851
 272184 218515 53669
 338046 302098 35948
 914599 636911 277688
 125457 104735 20722
 377589 336103 41486
 80535 71710 8825
 436433 336449 99984
 78901 70316 8585
 368185 333554 34631
 362172 278941 83231
 73663 65894 7769
 1745240 1585073 160167
 138249 123991 14258
 349548 271041 78507
 116304 103769 12535
 838995 722923 116072
 261639 232394 29245
 392613 312725 79888
 737860 670731 67129
 121746 106783 14963
 682619 540587 142032
 686167 586676 99491
 651868 583598 68270
 164933 145513 19420
 415761 343069 72692
 129490 116980 12510
 1058763 961871 96892
 214207282 194969180 19238102
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 
];
D = [
223 1293 9 15
72 225 3 14
84 266 15 26
136 403 58 188
138 367 122 439
152 439 655 882
1076 670 1677 2462
1472 726 2367 4178
2055 939 3536 7374
2894 1245 5605 13040
3688 1654 8337 20234
5401 2243 13768 33547
8420 3254 22217 52780
17222 4780 38206 82499
51169 7169 62550 121491
223042 11675 102982 175884
965447 18042 153121 229100
2948179 28070 191910 258490
5731397 42767 189012 234308
6211055 62749 152789 172528
3166939 88818 142548 146631
751889 122958 170012 171365
259909 168634 211707 212226
275000 221003 260638 259172
330840 282578 313835 314410
397984 351528 378195 378375
471897 430130 451374 454192
559831 521157 538934 539311
656320 618346 633931 635643
764936 724928 742069 744075
885530 839679 856044 858799
1012209 958225 980149 979278
1145517 1080415 1100247 1100738
1257963 1202159 1222048 1226538
1361956 1323387 1341159 1344807
1474722 1437432 1448591 1456264
1564272 1533480 1548414 1551856
1638144 1618623 1627138 1627592
1697755 1681990 1686551 1693281
1739241 1728637 1731511 1734567
1760914 1754381 1750674 1758694
1761757 1758782 1758185 1763214
1743342 1743629 1739043 1746125
1708593 1712011 1708810 1710205
1662824 1663605 1658740 1664158
1589753 1591908 1588254 1595673
1485105 1486789 1482656 1488141
1362472 1364835 1359711 1363753
1237447 1238175 1236312 1240290
1113963 1115247 1112360 1116349
1007247 1007266 1007875 1005306
894757 895387 893207 898357
827109 827727 824073 828341
784122 784635 782709 787219
741546 741642 739845 741912
705548 706821 703634 708287
690818 690534 688396 692430
671687 673514 670774 674304
682762 682344 682011 683670
690591 692345 689590 692830
699688 701900 698115 699797
695869 694881 693469 696004
705306 701939 702907 703733
682457 678566 680512 681436
630003 627345 626857 631127
544475 544788 543041 543987
441667 440896 441002 442219
353281 354912 353602 354692
282427 282816 283334 282496
190319 190296 189723 190240
85737 86645 86220 86322
17162 16878 16890 17160
0 2 0 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

];x = [
10 12 15 19 23 28 35 43 53 66 81 100 123 152 187 231 285 351 433 534 658 811 1000 1233 1520 1874 2310 2848 3511 4329 5337 6579 8111 10000 12328 15199 18738 23101 28480 35112 43288 53367 65793 81113 100000 123285 151991 187382 231013 284804 351119 432876 533670 657933 811131 1000000 1232847 1519911 1873817 2310130 2848036 3511192 4328761 5336699 6579332 8111308 10000000 12328467 15199111 18738174 23101297 28480359 35111917 43287613 53366992 65793322 81113083 100000000 123284674 151991108 187381742 231012970 284803587 351119173 432876128 533669923 657933225 811130831 1000000000 1232846739 1519911083 1873817423 2310129700 2848035868 3511191734 4328761281 5336699231 6579332247 8111308308 10000000000 
];
