A = [
634921 584358 2138761 613319 599827 565961 560990 563601 570473 558605 581926 626531 671869 733579 822533 882651 944148 1028463 1047473 1051652 1081212 1071214 1064229 1075453 1096384 1284764 1268409 1248225 1407199 1234558 1247387 1220457 1027670 1039444 1039836 1028934 1004081 990437 985768 968444 960254 956355 956941 951231 949987 946396 932693 929318 914142 898693 892066 890430 884680 879699 875158 868599 859235 851893 844358 838506 829190 823331 817678 811630 807547 796869 793755 787584 782919 773742 764568 756922 748226 741617 732027 728708 720523 711658 703408 698994 690973 680756 675914 666152 657424 651597 646704 637165 629767 621686 616251 607820 601219 592463 589202 581637 573036 566363 561723 554416 544987 537708 531413 527506 521689 516807 512666 505956 497883 493154 485803 480187 475483 468896 461283 457960 454476 448023 442267 437738 434008 427334 418000 414029 406973 404223 399491 395367 386492 382644 378245 375023 370869 364319 359562 353843 349738 343683 340609 334661 330371 328796 324132 322636 316892 311472 306551 301564 297005 293637 290073 287822 282234 277763 270421 267777 265012 259279 255404 251371 247714 244617 240359 236206 232785 229034 226940 224027 220107 217651 213721 210496 208937 204665 202824 198148 196109 195330 189063 185925 183188 180656 177439 173456 173429 169191 166408 164552 160638 158900 156491 155564 152752 150730 148989 146354 145696 144550 142375 138068 136956 133218 130819 129914 127444 126124 124353 121107 119054 118383 116729 112416 110458 107467 106852 105288 103453 102528 99935 99786 98269 95711 95029 91602 90691 88577 87635 87341 85746 84429 82749 81181 80485 78062 76703 76486 74510 73743 72539 70496 69869 69270 68197 67234 67539 65388 64532 63779 62431 61873 60245 60263 58803 58271 56614 55959 54548 54303 52455 52338 51945 50680 50047 49970 49070 47579 46586 46114 45969 45602 45640 44725 44415 44056 42854 41623 41340 40740 40633 40554 39756 38897 38392 37972 38014 37126 35649 35563 36118 34633 35499 34577 33629 33475 32246 32243 31092 30709 30661 30852 29467 28851 28380 28822 28190 27430 27436 27855 26384 25485 25206 25474 25593 25260 24893 24542 24720 22985 21836 21450 22060 20803 20526 20368 20174 20165 19982 18723 18750 18685 18363 18762 18830 18506 18031 17436 17753 17615 17184 17331 17258 17067 17569 17187 17698 17942 16004 15392 15348 15324 15270 15720 15055 13879 13848 13563 15856 13602 13986 13365 13468 13409 13115 15026 14001 13246 13599 12865 12184 11803 12129 11646 11236 11347 11140 11779 11670 10707 10708 10424 10192 9912 9715 9572 10650 10137 9633 9684 10073 10133 9968 9720 10194 9734 9793 9398 7977 7991 8033 7913 7696 8200 7668 7863 7887 8087 7488 7549 7808 7987 7847 8041 7778 7968 7921 7574 7588 7494 7609 6945 6688 6364 6230 6147 6310 6270 6062 6236 6777 6459 6043 5744 5917 6056 5756 5643 5885 5621 5789 5432 4990 5342 4951 4950 4741 4721 4624 5029 4635 4572 4740 4762 4978 4573 4721 4700 4731 4621 4483 4368 4693 4353 4342 4719 4448 4527 4835 4320 4338 4506 4722 4314 4292 4193 3997 3903 3808 3678 3795 3719 3784 3948 3784 3871 3813 3820 3730 3658 3723 3801 3902 3723 3764 3584 3924 3634 3626 3631 3612 3604 3728 3671 3706 3706 3580 3557 3331 3254 3377 3225 3300 3251 3305 3292 3151 3297 3126 3024 3046 3112 3157 3033 3124 3062 3080 3002 2895 2953 3004 2888 3075 3129 2894 2880 3030 3110 2885 2765 2795 2976 2892 2611 2867 2845 2949 2897 2731 2823 3141 3183 2988 2911 2922 2954 2891 2944 2789 2833 2887 2845 2605 2578 2629 2576 2490 2472 2442 2547 2439 2489 2634 2517 2480 2400 2354 2387 2283 2196 2157 2095 2191 2164 2297 2288 2235 2081 2109 2041 2002 2072 2068 2149 2156 2194 2142 2181 2131 2142 2126 2079 2053 2035 1989 1995 2121 2000 1945 1999 1858 1898 2007 2106 2138 1969 1842 1999 2041 2077 1999 2041 1889 1945 1988 1950 1972 2113 1870 1946 1815 1859 1931 2043 1988 1787 1809 1841 1938 1865 1694 1741 1740 1616 1721 1709 1562 1707 1781 1888 1956 1612 1636 1472 1439 1529 1523 1477 1492 1372 1421 1391 1394 1324 1380 1307 1335 1417 1585 1470 1412 1360 1337 1353 1360 1395 1414 1394 1487 1404 1282 1242 1394 1336 1463 1362 1621 1505 1454 1345 1343 1343 1328 1355 1374 1408 1377 1465 1487 1511 1392 1408 1397 1320 1379 1392 1317 1139 1200 1247 1286 1264 1636 1560 1559 1479 1441 1461 1543 1833 1862 1544 1496 1584 1374 1451 1535 1727 1517 1335 1416 1444 1356 1342 1309 1806 1767 1896 2800 2319 2109 1805 1495 1595 1481 1716 1376 1581 1836 1445 1584 1508 1537 1283 1502 1475 1245 1264 1194 1372 1029 1000 1166 1148 1122 1245 1238 1154 1246 1103 1062 1098 1155 1298 1279 1346 1264 1194 1817 1661 1198 1134 1056 1068 1066 1329 1198 1443 1803 1897 1413 977 1164 1260 1484 1042 1259 1081 1213 1073 1041 1116 1136 1123 1077 1064 1097 1045 1157 1196 1588 1503 1130 1103 1040 1028 1011 1086 1201 1225 1149 1058 1017 982 874 940 835 898 885 814 926 982 836 857 832 793 959 1131 1150 1140 1202 1159 1301 1319 1183 1139 1298 1377 1089 1125 1047 1106 1150 1126 1466 1467 980 1016 741 710 674 662 730 628 731 702 643 715 681 677 753 808 762 710 636 726 665 763 817 742 807 781 777 753 718 757 677 703 746 634 621 661 609 617 579 647 592 564 630 599 621 563 545 526 589 619 549 566 572 594 572 573 689 704 573 559 541 592 549 562 584 610 572 432 471 456 481 447 438 419 364 410 406 464 417 375 430 322 383 341 383 385 390 473 400 394 412 366 405 365 442 413 372 354 375 402 431 384 376 336 366 404 413 401 436 405 383 478 531 425 362 356 364 354 426 366 394 356 337 341 403 355 332 348 365 343 355 312 326 295 347 382 291 325 356 351 300 349 355 332 343 373 366 381 301 275 317 306 366 327 319 357 357 325 308 339 345 349 325 365 363 361 326 314 343 337 339 352 318 303 365 369 396 374 383 363 392 336 342 447 439 451 441 450 457 388 359 401 448 422 411 405 387 370 341 326 359 361 365 382 410 334 359 401 352 387 345 330 378 355 311 379 330 335 355 390 344 354 353 317 279 350 339 360 369 303 316 330 304 331 336 311 371 357 366 324 387 358 338 295 291 319 292 273 369 305 343 359 401 344 340 283 355 337 309 343 354 333 358 305 349 396 278 284 256 274 293 237 269 239 243 257 273 254 337 308 394 277 282 272 254 229 225 252 234 312 261 284 249 230 289 294 258 229 271 289 264 236 212 302 279 267 279 264 257 261 378 325 346 315 284 343 327 322 292 351 378 287 391 333 389 340 352 369 383 337 360 377 409 416 458 448 312 336 335 336 336 309 286 308 277 322 276 278 305 250 232 205 204 244 241 225 292 264 309 223 243 253 238 228 241 207 208 206 245 200 208 217 234 205 242 218 266 220 233 227 202 197 173 161 152 169 196 161 160 162 188 154 120 164 162 154 164 187 157 230 178 160 170 173 180 181 213 170 167 208 175 173 189 186 159 183 185 182 202 198 190 226 173 189 163 233 165 189 153 149 168 164 152 142 145 176 166 178 224 185 205 250 216 194 200 222 200 207 212 199 234 184 171 178 198 209 178 196 182 149 162 174 140 145 140 175 168 179 138 134 144 139 116 127 162 156 123 135 114 108 109 115 85 136 125 120 109 130 101 109 121 90 136 111 103 123 115 111 137 123 131 120 135 119 122 106 122 100 77 115 108 102 101 89 96 93 83 81 85 71 104 149 134 183 153 123 116 124 133 135 110 107 118 113 133 124 134 134 128 126 135 137 136 162 145 120 140 117 122 126 117 104 110 114 120 131 186 107 143 121 138 153 156 105 146 131 133 167 132 120 86 91 91 103 84 112 86 98 106 111 93 112 98 90 83 80 111 70 56 86 95 83 67 60 67 61 72 76 66 75 68 65 69 59 78 63 57 60 79 87 76 66 59 70 64 83 64 73 78 85 81 87 90 75 98 90 81 61 70 64 67 80 70 80 68 82 73 60 64 74 61 65 63 75 86 62 79 82 71 60 71 55 61 71 58 65 64 76 68 58 67 66 61 45 58 65 61 59 86 61 64 70 80 59 68 60 81 73 60 57 63 60 69 76 73 64 47 57 61 56 57 78 65 50 63 65 58 64 84 105 84 94 81 53 72 102 94 88 74 73 90 103 124 106 109 109 91 95 101 97 60 77 69 68 64 89 82 80 72 62 63 82 90 89 71 80 70 76 74 100 90 99 96 125 88 80 89 99 92 85 76 82 60 72 66 92 86 67 85 72 82 97 115 75 67 69 88 79 76 88 95 93 129 110 70 99 89 117 116 107 134 136 117 158 135 171 203 226 184 199 172 189 139 139 187 164 199 164 181 177 210 200 205 236 203 194 203 179 162 157 235 156 141 135 248 204 316 212 184 183 167 155 298 445 857 774 683 472 425 288 381 172 32 56 32 35 57 53 44 50 59 73 56 60 47 58 47 63 56 64 55 54 71 47 66 60 77 71 94 98 161 80 94 75 71 90 66 83 69 94 70 75 89 59 73 69 46 96 96 80 78 67 51 63 61 75 67 64 87 90 108 64 69 51 63 106 72 81 76 64 68 62 74 58 47 59 54 54 44 39 63 41 48 55 30 51 39 31 53 48 44 47 40 54 44 44 45 35 36 37 32 34 32 27 22 33 37 27 50 42 22 28 45 45 37 33 33 42 43 35 22 28 34 31 43 44 36 28 38 28 34 44 37 36 27 41 34 35 33 30 32 37 42 31 40 36 41 26 45 32 43 28 26 23 34 34 38 27 28 26 35 43 38 29 35 28 33 39 22 58 41 33 38 36 22 39 26 32 32 36 37 35 35 37 24 39 32 41 32 33 33 43 37 35 31 22 37 32 33 40 41 35 26 28 29 36 33 32 31 27 21 37 41 32 37 47 35 48 39 47 44 40 26 40 40 26 28 38 30 35 23 37 39 34 28 39 24 31 28 26 38 37 24 33 31 29 38 29 30 21 15 39 41 38 33 34 31 31 23 30 44 41 29 25 34 30 25 29 36 36 28 26 35 28 28 22 43 33 32 37 29 41 24 41 23 35 38 23 42 38 31 35 26 31 29 29 30 33 21 23 20 17 50 44 42 37 25 43 35 37 20 25 28 33 29 33 
];
B = [
0 0 0
 441878 115212 326666
 410021 116021 294000
 571169 158707 412462
 682739 205114 477625
 410190 120942 289248
 1440877 527841 913036
 729435 244455 484980
 495718 189602 306116
 674369 247620 426749
 455950 152958 302992
 195608 65873 129735
 882762 278546 604216
 200043 63587 136456
 204297 86943 117354
 309095 118778 190317
 176949 65430 111519
 360401 153370 207031
 420728 160747 259981
 236054 93474 142580
 187920 72903 115017
 201068 86694 114374
 192017 87899 104118
 149321 66733 82588
 449673 183115 266558
 156904 66883 90021
 280976 124287 156689
 483362 196942 286420
 177858 76913 100945
 236212 104383 131829
 603687 237206 366481
 244626 113541 131085
 254524 115229 139295
 478355 207237 271118
 425463 186887 238576
 501814 220793 281021
 821324 356892 464432
 1097766 443353 654413
 505801 221431 284370
 924102 405716 518386
 850398 345350 505048
 284812 137961 146851
 1194071 508051 686020
 258906 127991 130915
 299629 148703 150926
 1424308 618256 806052
 310845 151955 158890
 754345 321020 433325
 1485750 693619 792131
 771490 334499 436991
 275170 141050 134120
 8823669 4109841 4713828
 277635 147406 130229
 505999 237452 268547
 257356 136350 121006
 550694 261490 289204
 536417 258957 277460
 278540 153332 125208
 536635 259627 277008
 238837 135915 102922
 25638095 14465160 11172935
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
74 75 9 8
31 29 1 1
60 40 0 2
123 50 2 7
135 54 5 10
231 64 27 7
1118 112 93 21
4835 137 127 38
26431 247 195 95
181116 352 252 165
853007 442 346 227
1555555 728 516 358
2184280 1078 1155 554
2869806 1869 1777 825
3248005 3536 2526 1204
3296421 6821 3604 2177
2743950 11870 4867 3545
1791389 18107 6408 5395
833616 24438 8047 8391
253793 31421 7954 8156
58906 36452 11381 10490
23456 43453 14473 12366
19193 50215 14060 10356
17104 43327 18748 14549
16515 40779 17795 23841
17321 38970 12334 16195
25064 21127 10783 10871
17553 16850 10547 10384
14207 20606 11644 11167
12832 15374 14215 12342
13278 15093 12500 12933
18538 17589 13052 13330
15829 15618 13668 13948
24893 24280 15155 14945
18606 18069 16406 16551
19502 19220 18253 18301
21629 21461 20035 20174
24334 23501 22640 23035
25195 25614 25103 25933
27764 27741 27447 27024
30760 31269 31218 30589
34567 34229 34571 34388
38559 39107 38926 38832
43081 43914 43455 43623
48756 48648 48744 48593
54891 55751 55066 54766
61532 61362 61944 61739
68225 68339 68503 68506
75999 75943 75802 75999
82740 82425 83330 82997
89660 89696 90779 89521
95579 96193 95940 95856
100997 101027 101569 101004
105081 105453 106518 105940
109399 109747 109871 109749
113429 113577 114351 112989
117510 117256 116982 116975
120611 120095 121676 120261
124073 124107 125663 124618
125924 126311 126100 125786
125828 126063 126283 126023
122337 121388 121881 121532
112053 112044 112173 111753
92076 91633 91665 92352
63901 63816 64311 63638
32499 31921 32145 32267
9340 9613 9480 9537
1159 1162 1058 1175
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
