A = [
545794 488140 6908750 431951 422907 419427 415044 413927 419742 425569 486795 601364 705014 831966 1095465 1335211 1452839 1563592 1537949 1408277 1336624 1279919 1250076 1273585 1351131 2190854 2318327 2577992 3405220 2874467 2914625 2888374 2581126 2669948 2631215 2618049 2539196 2416592 2351515 2305330 2337030 2443655 2480192 2542138 2601379 2562777 2517209 2448000 2356293 2317765 2306129 2292639 2316071 2319602 2301053 2283148 2243218 2173396 2129430 2091871 2047106 2040830 2037426 2023202 2020007 1997098 1955566 1922857 1881641 1832035 1805073 1786220 1761286 1752858 1746169 1721642 1699529 1675137 1629754 1594753 1569867 1540887 1521745 1510565 1494203 1474225 1460815 1429855 1407260 1377151 1349295 1327171 1310351 1288459 1272240 1265088 1245983 1227082 1207512 1177419 1154834 1133015 1110250 1100697 1086652 1070836 1058231 1045237 1024173 1004014 986081 962318 949916 935321 917691 909627 899408 881565 870594 861393 838259 825891 810476 794253 782890 774557 761212 749626 745566 729255 715575 706698 692684 677081 671596 657600 648436 642131 633293 623261 615693 602035 592864 584101 571806 563343 556020 545971 538753 533181 525625 515192 507685 496834 487318 481070 471174 466114 460277 451901 448807 440165 430304 426086 418446 410346 403487 397870 391504 386326 383485 375812 370514 364557 356593 350313 345370 340467 332890 329468 324589 319432 315367 308671 305078 299685 293319 288088 285036 278574 276152 271712 266637 263537 258480 254169 248981 245587 239842 237485 234595 229661 227488 223921 220460 216647 212752 210683 206658 202533 198180 196599 192956 190403 187836 183779 180342 177224 174621 170870 169597 167374 165096 162857 159424 156128 153557 151405 149471 146142 143876 142190 138917 138002 134754 133066 131340 129469 126197 123999 122043 120588 118511 116654 114638 112651 111641 108395 107742 105330 103387 102303 99991 98727 97227 96558 94661 92396 91279 89901 88330 85876 85049 83605 82440 80748 79504 78527 77110 76218 74928 73245 72311 71369 69747 68812 68259 66816 65851 65457 63838 62348 60573 60281 60108 58643 57421 56641 55792 55042 53916 52665 52584 51646 50708 49659 49105 48417 47184 46691 46265 45407 44465 43708 43282 42723 42524 41167 40854 40177 39788 38992 38178 37556 36832 36852 35912 35376 34814 34254 33849 33089 32478 32286 31771 31593 31004 30252 30019 29861 29211 28786 28253 28015 27472 27135 26690 25874 25969 25131 25273 24890 24423 24449 24057 23789 23316 22827 22546 22121 22240 21740 21232 21372 20967 20480 20324 20115 19751 19443 19228 18807 18670 18396 18005 17881 17436 17405 17037 17131 16671 16432 16209 16133 16025 15621 15624 15436 15169 14948 14869 14541 14702 14400 13758 14328 13810 13627 13165 13369 13208 13054 12715 12595 12807 12742 12583 12163 11897 11909 11838 11769 11684 11558 11298 11291 10889 11106 11121 10722 10554 10502 10371 10238 10064 10022 9877 9684 9659 9666 9316 9341 9207 9163 9144 8844 8789 8917 8739 8716 8678 8687 8457 8233 8168 8408 8294 7955 7710 7800 7800 7821 7558 7966 7518 7548 7619 7319 7423 7374 7290 7061 6888 6901 6898 6922 6914 6832 6701 6896 6503 6460 6886 6520 6422 6334 6219 6067 6250 6088 6106 6095 6057 5931 5655 5809 5859 5803 5757 5666 5375 5547 5553 5423 5461 5314 5394 5350 5248 5176 5231 5033 5100 5206 5006 4859 4996 4861 4978 5001 4929 5027 4866 4767 4672 4588 4618 4659 4583 4523 4642 4597 4462 4606 4303 4499 4374 4463 4493 4219 4365 4115 4211 4148 4124 4164 3937 4062 3858 3839 3984 3867 3952 4061 3949 3956 4012 3787 3953 3785 3800 3776 3669 3987 3878 3652 3663 3770 3697 3612 3487 3752 3724 3645 3649 3555 3621 3509 3696 3638 3445 3359 3570 3490 3408 3232 3398 3366 3320 3321 3271 3298 3106 3285 3224 3253 3202 2991 3278 3075 3230 3146 3161 3062 3024 3102 3171 2907 2983 3009 3072 3066 2962 2947 2960 2951 2921 2762 2917 2793 2668 2818 2881 2909 2660 2691 2650 2707 2756 2681 2841 2776 2832 2639 2656 2753 2592 2735 2664 2513 2741 2650 2521 2567 2490 2472 2459 2508 2568 2569 2441 2424 2411 2590 2432 2523 2395 2391 2410 2493 2367 2358 2344 2333 2381 2352 2303 2415 2246 2323 2260 2256 2316 2339 2263 2107 2196 2271 2236 2178 2187 2193 2152 2171 2100 2043 2120 2017 2127 2135 2054 2190 2121 2131 2055 2119 2087 2081 1997 2065 2059 1966 2007 2098 1922 1988 1950 1954 2048 2082 1835 1877 1904 1985 1868 1894 1874 1962 1944 1925 1882 1877 1874 1860 1810 1836 1851 1756 1934 1841 1808 1921 1790 1834 1903 1858 1848 1716 1744 1740 1828 1892 1825 1714 1835 1888 1648 1744 1777 1799 1793 1797 1768 1784 1645 1747 1804 1673 1692 1766 1722 1745 1587 1609 1666 1672 1621 1563 1696 1544 1527 1729 1539 1626 1664 1692 1535 1526 1531 1531 1644 1535 1520 1540 1526 1591 1582 1466 1468 1580 1430 1386 1427 1490 1348 1356 1452 1389 1353 1326 1381 1366 1385 1276 1342 1406 1370 1368 1335 1350 1283 1335 1323 1203 1218 1311 1316 1198 1269 1241 1340 1237 1294 1264 1246 1322 1277 1284 1267 1213 1224 1161 1306 1279 1239 1149 1194 1235 1182 1151 1132 1136 1187 1182 1172 1201 1219 1258 1208 1184 1241 1168 1139 1194 1278 1117 1304 1198 1184 1243 1156 1130 1204 1195 1186 1122 1168 1200 1133 1075 1106 1052 1201 1095 1121 1176 1180 1079 1098 1132 1042 1041 1056 1091 1102 1126 1094 1044 1123 1037 1077 1074 1110 1057 1078 1081 1034 1038 1076 1066 936 1026 959 948 1036 978 992 973 1023 947 967 922 895 1003 950 919 1034 990 912 965 990 908 1003 942 1009 1005 962 887 959 1019 894 915 939 914 898 882 912 977 990 958 926 887 950 897 842 901 835 829 833 923 841 867 773 876 835 899 869 845 829 781 757 900 896 855 897 861 901 806 784 817 816 828 877 859 770 893 893 883 861 716 734 744 992 756 781 631 687 709 741 678 703 716 645 750 671 677 662 725 674 718 695 714 646 708 686 720 667 668 664 670 616 697 728 719 654 699 677 684 696 650 694 662 695 690 607 703 688 659 668 629 680 636 647 673 635 597 624 620 640 655 662 615 600 559 579 613 602 591 581 577 587 574 626 573 603 601 594 608 605 567 580 561 580 539 528 524 540 570 507 518 531 551 489 495 494 476 538 493 475 537 499 532 569 553 530 527 492 483 522 538 455 512 507 525 548 553 563 604 503 553 562 508 559 550 571 530 509 499 504 538 574 573 509 539 483 548 544 568 510 547 481 532 504 496 482 549 599 496 512 454 482 503 495 490 502 437 480 464 458 497 417 467 435 476 436 406 416 440 412 365 408 370 421 456 376 372 363 388 404 378 466 396 418 431 486 367 404 417 392 382 440 410 376 345 392 379 364 371 389 353 394 360 380 397 377 390 390 435 368 371 367 387 362 386 394 364 349 434 354 421 368 368 395 382 376 441 358 346 385 422 387 363 356 374 334 350 351 358 355 351 348 350 367 385 381 394 369 394 368 339 346 321 382 391 350 372 381 319 323 349 360 316 332 323 362 331 333 331 331 342 297 321 313 339 322 321 349 352 339 348 323 284 308 297 303 299 296 253 267 250 264 268 274 270 273 269 276 276 283 303 289 306 289 318 262 315 297 272 295 254 261 310 250 291 295 259 285 300 308 305 299 234 235 260 258 244 254 211 236 253 244 243 218 220 210 231 263 247 237 245 233 204 251 246 224 235 234 229 280 216 221 230 217 226 229 247 236 240 223 240 242 222 209 245 234 240 240 259 238 246 242 257 255 256 231 275 217 221 253 239 254 254 257 264 313 249 258 228 300 279 259 244 260 279 270 260 277 243 256 260 273 275 239 238 274 227 214 245 286 236 233 239 260 242 231 239 216 249 228 245 223 300 252 270 236 189 221 255 246 216 197 204 167 209 191 175 187 190 220 206 221 220 212 223 176 188 199 200 183 193 160 200 200 206 188 174 210 187 189 201 175 212 194 145 209 201 204 181 185 159 217 208 218 169 206 181 198 219 160 153 200 183 202 177 181 203 201 165 211 173 206 206 176 174 176 179 174 163 146 197 182 198 145 172 138 158 194 179 182 186 174 165 163 178 193 204 183 177 151 150 198 183 197 180 179 213 164 191 171 193 210 175 166 173 182 176 170 180 172 188 190 196 187 175 174 163 197 145 192 160 203 145 187 168 141 190 216 195 174 189 189 179 155 172 213 174 188 190 310 171 166 159 149 173 171 211 161 197 199 181 178 181 196 163 204 161 157 162 184 162 156 221 142 162 164 164 171 130 156 161 168 183 160 120 159 161 147 152 108 137 136 140 132 139 146 143 148 132 117 125 135 119 104 119 121 134 120 108 136 127 99 107 122 144 131 128 173 128 127 158 135 140 112 111 133 135 147 145 137 129 163 135 148 144 157 146 165 134 125 122 114 120 116 126 136 133 123 111 112 115 128 121 115 143 121 113 171 151 122 125 91 140 117 162 129 135 136 141 174 148 161 130 135 144 158 142 164 173 167 152 161 185 167 155 190 133 174 169 151 180 143 176 142 156 150 158 160 189 135 178 164 191 178 203 186 171 189 200 184 191 185 186 164 159 155 174 141 143 140 127 124 106 109 130 130 108 131 121 159 125 108 96 150 100 102 124 110 117 112 121 150 117 99 107 122 124 105 114 141 113 105 103 129 94 122 97 95 112 99 83 120 106 129 111 94 116 117 109 117 98 93 89 96 94 119 120 103 102 92 91 101 116 130 110 113 97 112 106 116 116 101 95 96 115 79 125 113 106 123 95 89 127 105 68 92 66 71 105 72 80 87 80 75 78 94 68 89 95 79 71 97 96 83 67 67 77 88 94 79 75 105 79 67 63 101 78 73 74 88 94 57 97 100 70 73 100 90 66 95 83 54 77 67 88 77 83 72 75 84 77 98 88 96 100 84 68 79 75 90 81 75 83 86 93 64 87 82 86 88 79 49 109 73 79 68 70 70 54 91 68 76 83 91 59 75 72 80 88 78 82 86 54 96 71 87 71 86 61 61 92 89 75 70 70 92 81 92 77 66 88 68 52 71 52 71 69 151 70 63 72 67 65 66 60 72 44 62 45 55 54 53 47 46 45 63 68 51 45 54 43 61 51 51 48 33 43 28 33 47 41 46 39 38 31 29 34 36 32 32 72 25 32 38 44 42 56 46 45 44 54 54 45 43 49 49 57 41 47 44 48 71 40 43 43 51 59 46 44 39 55 47 32 53 59 43 48 41 57 37 43 42 41 36 39 40 29 51 40 35 41 
];
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
 118902 97034 21868
 82264 66223 16041
 133003 105856 27147
 144981 119682 25299
 87974 74831 13143
 144444 115835 28609
 68966 59376 9590
 79988 69350 10638
 105691 85646 20045
 141513 120944 20569
 65032 57082 7950
 137531 114013 23518
 92486 81771 10715
 62978 54942 8036
 271086 218659 52427
 83376 73171 10205
 91755 81240 10515
 160152 136109 24043
 173699 146590 27109
 169043 148410 20633
 126822 110462 16360
 93661 84602 9059
 185538 164118 21420
 99715 86603 13112
 324235 290981 33254
 155256 135099 20157
 113208 100091 13117
 130450 119771 10679
 221250 186153 35097
 394202 365028 29174
 125459887 117830838 7629049
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
35 273 7 2
4 47 0 2
11 82 0 5
22 123 3 3
16 114 5 3
32 115 15 10
2736 193 45 31
30532 227 580 141
458641 294 1909 514
1547128 410 2687 1034
2356915 522 3247 1578
3120464 842 4338 2742
3573113 1505 6061 4716
3901509 2709 9961 8630
3592211 4719 16187 15134
3273191 8494 26550 25830
2501086 14463 39416 39434
1504333 22709 54753 54395
693272 35331 71915 72607
279967 53954 90696 90676
149435 76292 109086 109335
139656 103121 130954 131117
160188 133953 156896 157383
190114 168162 185220 185402
222283 205989 220030 218505
263662 249233 257160 256840
305227 293565 301250 301010
352820 342885 348448 347939
401770 393978 398031 397628
452578 444687 448741 450129
504233 496469 499589 499045
552813 543617 545568 545972
595642 586492 588717 590679
633804 630155 628705 630617
668351 664369 666042 666048
698095 698680 696610 698319
722608 723198 723096 723702
744883 747233 745343 748688
764007 767027 764367 764888
780387 784369 782589 786276
797499 801005 798910 799028
811477 816562 811828 814290
819187 824088 821349 821941
821103 828420 825018 824520
815345 819438 817653 819691
808627 811430 809135 809738
783648 783930 782681 784354
743014 742946 742166 743722
694704 696172 694731 696075
641648 642239 642309 642329
582589 583582 579141 583504
526556 527667 526693 527149
474494 476235 474799 475007
429437 429685 430278 429988
393291 393828 394194 393282
364624 366505 365536 365124
345900 344764 346172 345786
326477 326397 325703 326042
318734 318524 317456 319382
315041 313752 313663 315131
327570 326009 325202 328091
333883 332403 333933 333844
327547 328078 326271 327212
317668 317026 316548 317868
290820 292637 291758 292036
254583 254208 253379 255052
209073 210542 209138 209635
163412 164803 163698 163952
118177 117932 117790 118170
73020 73203 73249 73339
28551 29231 29080 28750
3928 4092 3980 3876
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 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 
];
