A = [
514201 516695 2400150 164456 168578 157733 153123 157439 166911 175131 221238 254342 273398 333213 370389 374862 371200 368633 364102 357642 352987 345691 338743 337868 351363 479398 500680 537332 667437 609773 628295 624022 573414 593464 590096 592159 585676 572684 566092 558785 559033 553249 553935 561117 560729 561639 546512 538495 530027 513574 505739 502755 506695 505392 505811 506323 504884 500737 499001 493012 488656 489338 487590 486509 487073 484507 480917 482663 475724 471258 468473 461160 457456 456425 451721 449432 450963 444087 440825 439102 431987 425659 424408 421026 413752 414856 411740 405554 405449 400198 392945 389720 382107 378382 375874 373931 368495 368443 360550 355871 353196 347801 342357 338037 333892 328514 327628 323148 319815 317107 310957 306480 301444 296869 292567 287845 285719 280534 279210 275437 272830 269489 262792 259044 254833 250503 248083 244504 240517 237490 236531 231951 226988 225048 220439 214790 212955 210129 206982 205617 202081 197996 197391 191644 188403 185541 182670 179732 178306 174357 171711 170601 167510 163746 161496 158646 155279 153955 150741 149188 147700 144474 142781 140503 137030 133988 132631 128726 127948 125549 123814 122057 120679 118752 114978 114640 110460 108461 108249 105364 103321 102476 101331 98829 97232 94964 93257 91392 88867 87358 86731 84711 83474 83096 81003 78714 77516 75482 74647 73398 72433 71375 70093 68657 66754 65919 64418 63082 62234 60339 59280 58106 57425 56479 55892 54367 53494 52168 51292 50189 49415 48537 47919 47082 46235 45189 44200 43072 42350 41903 40783 39605 39342 38867 38290 37696 37024 36103 35555 34509 33925 33368 32532 32233 31589 31022 30502 30145 29403 28182 28142 27450 27187 26516 26184 25698 25207 24789 24233 23674 23460 22757 22236 21792 21567 20908 20654 20283 20570 19737 18906 18861 18782 18291 17818 17549 16872 16894 16419 16077 15925 15765 15327 14972 14623 14779 14339 13986 13528 13508 13111 12754 12711 12544 12032 12036 11773 11391 11276 11100 10902 10939 10493 10317 9943 10110 9733 9637 9505 9204 9370 8853 8829 8670 8701 8439 8151 7939 7876 7758 7601 7676 7752 7239 7124 7056 6952 6687 6638 6568 6600 6527 6208 6229 6215 5968 5794 5878 5901 5837 5559 5466 5205 5370 5291 5170 5201 4975 4932 4850 5023 4741 4656 4714 4479 4449 4255 4380 4268 4280 4159 4310 4281 4165 4135 4016 3884 3837 3889 3981 3731 3724 3803 3580 3656 3546 3625 3520 3444 3496 3398 3530 3336 3374 3286 3295 3280 3182 3424 3380 3178 3041 3051 3095 2907 3122 3039 3119 3265 3047 2917 2997 2929 2814 2828 2753 2768 2733 2650 2637 2662 2597 2627 2562 2651 2581 2441 2470 2430 2483 2718 2509 2423 2427 2360 2431 2323 2338 2460 2170 2328 2390 2311 2190 2256 2312 2240 2216 2231 2207 2119 2110 2138 2123 2149 2220 2095 2128 2092 2026 2226 2102 2015 2060 2070 2038 2042 1838 2027 2122 2033 2022 1985 1954 1971 2147 2188 1987 1990 2126 1980 1925 1902 1907 1995 1936 2131 1928 1909 1974 1847 1864 1922 1913 1893 1820 1788 1810 1856 1722 1681 1826 1815 1757 1765 1743 1824 1750 1797 1683 1710 1736 1752 1667 1706 1716 1654 1708 1616 1591 1561 1518 1545 1614 1617 1581 1573 1656 1484 1521 1521 1599 1531 1441 1450 1441 1401 1350 1389 1448 1405 1423 1564 1436 1458 1401 1345 1276 1273 1311 1217 1379 1271 1286 1317 1324 1330 1377 1342 1328 1267 1302 1309 1374 1311 1337 1217 1296 1283 1270 1221 1217 1349 1303 1245 1279 1238 1233 1343 1174 1193 1224 1233 1239 1160 1215 1211 1247 1161 1188 1214 1188 1256 1188 1224 1250 1203 1266 1193 1173 1261 1253 1188 1201 1199 1171 1182 1161 1158 1141 1175 1251 1173 1087 1182 1194 1093 1146 1174 1074 1091 1064 1253 1028 1069 1058 1087 1031 1050 1077 1013 975 988 982 995 986 1016 981 955 984 972 984 1003 1029 899 923 877 859 895 879 781 874 864 844 838 922 871 867 881 815 841 862 905 772 792 789 813 828 828 766 838 772 756 833 800 751 761 716 808 746 728 724 715 709 782 830 770 752 719 757 795 752 739 773 833 775 717 739 786 680 661 796 704 700 749 793 800 769 762 728 716 764 758 752 779 690 738 666 766 797 736 710 716 690 661 822 713 651 688 699 690 747 778 745 742 762 780 727 718 735 771 660 736 748 691 700 1030 717 723 746 706 690 765 711 747 663 756 745 691 704 678 672 712 740 784 704 743 725 728 759 664 699 684 681 677 682 696 752 700 695 677 625 665 649 638 638 676 727 612 566 637 587 570 594 589 561 596 733 578 557 620 670 542 538 630 637 533 596 603 608 606 617 578 552 612 552 579 591 658 622 521 540 591 530 553 542 606 631 560 574 512 588 585 503 493 516 536 538 530 534 518 561 542 517 536 575 575 585 584 528 604 550 545 609 545 503 576 541 532 519 551 513 701 561 559 518 494 513 514 507 528 515 561 630 556 539 526 546 523 533 502 562 537 543 524 542 486 511 500 447 503 484 469 471 506 479 468 471 440 472 528 504 461 402 494 445 741 482 466 472 485 444 427 507 525 474 508 474 468 436 433 455 480 476 475 475 530 529 485 515 512 526 488 539 537 526 538 565 563 555 620 570 518 490 520 499 544 511 442 504 472 468 513 532 495 518 477 487 479 527 500 448 504 538 484 503 543 481 446 477 422 460 505 528 422 494 469 442 468 506 487 492 490 492 456 547 466 428 543 575 419 420 476 483 453 531 484 449 447 438 471 422 439 429 443 425 431 455 389 424 489 441 453 462 464 416 378 745 532 431 401 393 380 344 325 320 322 331 377 384 300 303 352 349 376 319 308 304 266 351 313 285 276 303 290 264 283 294 249 278 276 304 281 261 294 265 282 295 270 268 282 255 284 270 269 236 246 477 299 285 284 296 302 270 284 263 258 298 258 314 304 273 271 298 279 316 279 305 305 302 300 288 261 321 312 409 532 280 339 396 393 450 357 464 266 404 412 383 360 382 428 358 395 344 356 313 340 374 361 284 339 340 371 346 339 305 309 298 291 326 301 257 270 272 255 301 227 249 318 208 287 277 296 298 266 231 259 293 293 250 268 235 180 178 197 124 150 145 155 157 157 173 157 192 177 178 195 152 167 180 163 161 194 144 176 169 169 196 182 156 144 174 152 171 143 142 168 174 166 148 151 163 160 149 159 157 159 195 152 166 155 151 150 186 166 152 159 125 123 120 136 119 147 158 133 146 151 133 137 159 139 136 136 145 115 140 149 118 119 118 117 136 112 136 149 139 125 113 139 136 127 137 154 146 108 122 122 107 91 121 107 92 97 129 122 102 97 106 103 115 88 189 108 121 143 93 207 116 123 116 123 113 130 106 120 117 123 108 134 123 105 125 108 127 111 132 130 158 140 136 114 139 117 116 140 128 148 165 141 150 146 127 146 151 152 148 158 145 159 164 154 182 176 161 136 145 165 158 144 143 164 150 136 134 149 136 144 140 129 188 120 122 136 123 113 121 106 125 124 105 106 135 99 113 82 163 94 71 91 90 90 86 103 86 89 93 98 86 86 103 96 89 82 106 75 78 80 122 97 98 92 104 89 95 97 103 111 106 104 147 110 95 91 95 83 121 99 102 108 93 79 101 60 72 65 99 87 68 88 72 80 87 87 93 106 99 84 90 100 75 86 74 103 65 100 81 62 92 53 45 60 66 57 56 65 81 66 73 55 77 55 60 55 73 71 49 64 60 91 55 70 56 44 55 65 48 53 44 55 63 54 60 68 81 70 73 58 61 51 67 77 50 72 51 51 56 39 40 56 62 67 60 46 65 62 37 61 56 47 62 67 51 41 55 54 41 42 43 48 36 65 46 46 72 50 42 51 63 63 51 53 41 52 54 43 55 51 51 55 58 44 33 34 45 41 30 34 36 42 40 37 69 27 54 37 33 29 26 21 34 28 34 32 33 30 27 45 28 34 76 30 30 24 24 32 36 31 31 30 23 28 27 22 23 27 21 34 45 45 40 29 41 39 41 26 34 49 36 53 40 55 51 34 42 33 30 49 34 35 40 21 29 33 31 39 27 35 37 19 27 31 31 26 27 43 38 29 39 31 34 32 26 30 30 32 26 25 30 32 32 43 33 28 37 35 18 26 30 33 33 36 23 22 33 33 44 42 40 32 45 38 43 33 43 32 55 52 37 43 87 50 47 32 44 35 26 29 29 19 19 17 25 28 27 17 18 20 25 16 24 22 43 29 14 23 27 19 25 22 18 19 29 29 31 30 17 29 28 26 27 37 31 40 39 31 34 36 33 32 27 41 25 29 31 65 41 53 68 41 48 65 50 56 48 63 53 63 75 56 56 60 60 48 47 62 53 75 57 47 86 81 67 61 68 82 76 58 39 50 53 62 61 54 40 39 51 62 42 45 49 46 36 27 33 46 45 39 38 38 41 47 41 46 41 23 47 50 43 50 43 38 33 26 27 19 26 31 27 28 24 22 17 22 21 27 30 17 24 23 22 31 29 25 20 10 18 20 49 29 23 23 24 11 20 26 26 24 25 42 35 40 21 31 48 33 37 32 29 33 21 24 26 23 26 25 30 17 34 36 20 20 24 32 24 28 20 28 27 24 23 28 29 14 20 26 18 27 27 18 23 24 25 29 32 31 32 34 15 5 7 19 19 12 18 30 21 20 16 11 22 21 13 20 13 12 10 19 8 7 12 14 9 13 7 7 11 10 5 12 11 13 9 14 6 13 10 12 13 11 14 9 13 17 13 11 10 16 8 24 20 9 9 16 13 21 13 20 26 27 14 26 20 20 24 15 25 19 25 28 25 39 18 23 32 27 41 26 25 23 14 21 23 23 25 21 25 14 26 9 20 7 27 11 19 11 16 10 18 9 10 12 7 8 6 10 9 8 6 13 3 7 9 6 14 6 8 2 9 6 6 11 4 9 3 8 4 3 3 5 8 4 7 5 4 4 3 3 3 9 10 11 7 18 11 4 9 14 4 11 6 8 4 7 4 3 12 7 10 3 8 
];
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
 64927 19822 45105
 64544 18434 46110
 55620 18060 37560
 66650 21760 44890
 49592 15587 34005
 56673 18357 38316
 52512 16216 36296
 43217 14061 29156
 65972 21642 44330
 55796 18880 36916
 48665 17335 31330
 69439 22270 47169
 45066 16371 28695
 112556 37394 75162
 61748 23394 38354
 40917 15692 25225
 57118 20872 36246
 62463 25226 37237
 68114 24936 43178
 73566 30135 43431
 48979 19324 29655
 52161 20541 31620
 80676 32545 48131
 50016 19617 30399
 105239 45930 59309
 74265 29316 44949
 102089 38985 63104
 56720 26959 29761
 80259 32851 47408
 170077 84203 85874
 33782501 19800413 13982088
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
8 37 0 1
0 9 0 0
0 11 1 0
7 11 0 0
2 11 7 1
5 23 10 4
10 21 14 5
95 31 73 12
687 56 367 69
8641 69 444 149
72884 87 607 265
323697 139 788 469
705688 189 1114 724
1050531 341 1441 1176
1220420 612 2031 1706
1255215 1088 2918 2688
977969 1609 3876 3802
511345 2477 5196 5097
151441 3523 6760 6858
28582 5065 8667 8580
12689 6900 10572 10761
13357 9421 12887 13018
15930 12547 15624 15791
18626 15907 18326 18416
22038 19814 21627 21592
25003 24132 25181 25440
29491 28890 29197 29088
34360 33822 34086 34279
38706 39435 38948 39002
44815 45470 45045 44919
50216 51469 50999 50877
56701 56865 56548 56416
62775 63502 63220 62777
69453 70445 70156 70019
76987 77719 76809 76320
83168 84119 83326 83217
90237 91118 90230 91020
96243 96985 96070 96682
102452 103719 102454 103120
108476 109756 107834 108893
113060 113214 113317 113966
117635 118909 117561 117992
121810 122378 121667 121322
124182 125034 125228 125506
128693 128899 128788 129070
132564 132527 132637 132566
136038 136036 136302 135482
138522 138888 138426 138468
138508 138380 138433 138514
137000 137180 137524 136767
132462 132950 132430 133243
128972 130250 129437 129307
125029 125106 125495 125348
121841 120493 120909 121294
116666 116101 115903 116803
110176 110158 110412 110479
104984 104726 104428 104572
93642 94033 93350 93927
82456 83187 82137 83244
69496 70225 69816 69891
58173 59032 58430 58745
39316 39777 39778 39709
17805 17921 18009 17791
3802 3761 3819 3789
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
