A = [
789627 862283 2932944 669144 754812 655944 647252 658160 643424 609636 609622 613371 612146 596914 593669 581623 572263 571242 562814 558618 555980 549594 545478 543587 542735 621919 622279 622391 701579 704867 709996 710877 715471 718639 718598 715163 709237 704603 700282 693708 690568 687673 682693 678546 678420 672453 666257 662230 654443 648277 645908 639545 636765 633534 629424 625459 619803 613799 607998 604210 597225 591792 588151 582586 579152 576403 569658 567038 560774 554109 550353 546093 539586 533733 530138 524828 521075 515527 511188 505493 500718 494940 489779 486111 481051 476029 471043 466727 461061 456536 451638 446947 443599 436758 433777 428211 424115 419707 415819 410868 406274 402408 396709 392148 389074 384495 380846 377966 372309 368649 363933 360083 355944 352095 348316 342648 339846 335363 330959 327749 323923 320761 315997 311244 307492 305467 301352 297606 294211 290156 287276 284181 279609 278077 273743 268796 266835 264099 260566 256770 253340 251304 247530 245613 242105 239011 236249 233756 230148 228045 226319 222236 219957 217186 213487 210958 208450 205601 203302 200482 198280 195692 191459 188595 186422 183896 182078 179958 177584 175436 173167 170970 168202 166204 163505 162209 159864 156803 155101 153611 151288 149822 147584 145240 143770 142141 139779 137576 136153 134441 133767 130912 129723 127528 125456 124977 122259 121392 119394 117399 116429 114678 112798 111041 110032 108122 107226 105581 105095 103757 101734 100798 99163 98087 95849 95539 94004 93134 91271 90634 89146 88562 86623 85856 85075 83203 82326 81945 80008 78800 77776 77454 75766 75550 73960 72634 71873 70909 69610 69366 68140 67397 66387 66000 65775 64431 63676 62519 61633 60733 60483 59777 59106 58368 57669 56441 55915 55628 54557 53447 53251 52109 51528 51314 50406 49226 49734 48405 48008 47165 47071 46390 45670 45223 44623 44311 43399 42696 42456 42238 41611 41258 40410 40142 40235 39425 38301 38217 37980 37194 37079 36340 35979 36317 35211 35103 34332 34197 33847 33264 32851 32765 32217 32088 31776 31113 30746 30501 29968 29877 29515 29176 28827 28354 28256 27469 27792 27260 26514 26463 26011 25372 25156 24890 24182 24301 23946 23461 23415 23094 22819 22804 22718 21986 21887 21592 21654 21139 20667 20874 21049 20614 20316 20034 19867 19718 19377 19382 18714 18721 18727 19720 18024 18212 17988 17339 18902 17343 17366 17012 16813 16665 16482 16573 16015 16312 15959 15513 15373 15314 15162 14787 14782 14668 14427 14423 14206 13927 13934 13739 13567 13478 13267 13026 13574 12997 12663 12616 12446 12428 12683 12437 12656 12460 12120 11926 11559 11403 11259 11424 11436 11279 10628 10882 10773 10716 10393 10387 10576 10298 10028 10042 10123 9829 9996 9824 9508 9499 9188 9208 9177 9191 8974 8850 8763 8810 8658 8508 8722 8512 8462 8392 8383 8319 8236 8181 8337 8082 8073 7531 7636 7629 7417 7358 7311 7258 7170 7287 7009 7127 7056 7056 7083 6737 6765 6631 6567 6645 6489 6409 6506 6291 6350 6390 6339 6316 6195 6301 6138 5980 6194 6096 5918 5854 5757 5691 5598 5682 5629 5605 5419 5431 5353 5153 5361 5275 5334 5242 5154 5338 5251 5046 4997 5056 5087 4956 4971 4870 4868 4798 4794 4747 4691 4701 4620 4697 4663 4598 4522 4457 4396 4418 4380 4424 4288 4218 4203 4181 4223 4209 4044 4122 4131 3979 4044 3976 4001 3796 3997 3918 3916 3942 3846 3886 3689 3690 3807 3817 3810 3803 3803 3826 3705 3730 3704 3942 3646 4106 3767 3555 3858 3545 3517 3613 3503 3551 3446 3462 3342 3517 3304 3441 3328 3505 3423 3082 3096 3129 3181 3163 3088 3051 3167 3175 3213 3316 3243 3106 3061 3043 3038 2911 2950 3031 2938 2863 2830 2841 2838 2857 2802 2704 2834 2784 2799 2701 2718 2650 2724 2727 2540 2555 2453 2613 2547 2479 2496 2459 2411 2510 2425 2485 2462 2367 2380 2225 2442 2309 2278 2330 2141 2202 2328 2281 2145 2234 2192 2323 2113 2114 2200 2176 2187 2026 2185 2157 2163 2175 2024 2090 2215 2024 2067 2001 1997 1885 1984 1911 1980 1833 1841 1930 1927 1845 1814 1804 1841 1805 1787 1834 1747 1821 1755 1739 1857 1842 1860 1818 1715 1693 1751 1721 1753 1633 1663 1611 1606 1661 1606 1648 1622 1616 1607 1611 1581 1616 1510 1625 1515 1564 1631 1647 1621 1582 1502 1512 1566 1411 1405 1504 1495 1506 1472 1426 1525 1501 1462 1460 1405 1402 1384 1431 1362 1408 1395 1353 1385 1335 1437 1435 1408 1398 1383 1434 1420 1423 1399 1339 1359 1389 1381 1423 1471 1527 1517 1668 1763 1648 1562 1461 1460 1417 1435 1458 1281 1282 1462 1364 1471 1408 1426 1404 1436 1355 1211 1188 1227 1316 1206 1154 1244 1198 1154 1134 1156 1103 1098 1145 1139 1122 1182 1188 1209 1320 1198 1163 1219 1183 1132 1076 1062 1180 1032 1040 1146 1106 1145 1206 1053 1047 1004 1034 942 1031 1006 1020 1036 1016 989 1051 1012 948 940 963 1023 1013 885 941 1040 931 887 915 867 922 895 853 870 842 889 887 892 861 854 825 849 883 902 903 821 870 846 914 858 827 838 877 867 932 854 839 893 863 868 786 841 751 827 837 840 814 738 778 801 821 721 761 744 766 706 696 753 692 705 702 665 615 694 677 724 660 647 681 727 692 690 703 674 707 725 710 743 668 704 727 663 664 678 658 677 670 641 640 604 666 625 657 679 586 656 661 608 532 599 576 534 593 558 652 572 559 585 576 528 538 559 552 510 644 589 588 777 578 575 616 516 493 528 576 481 598 537 509 497 511 465 493 476 483 521 476 515 469 502 514 474 455 470 512 448 430 503 473 511 451 496 495 450 522 435 473 453 476 447 428 450 430 451 412 414 429 394 403 401 406 379 384 404 396 423 395 402 426 404 412 402 354 396 388 369 370 366 350 410 387 369 421 394 365 399 372 437 409 376 353 363 366 368 368 390 391 345 360 338 354 366 345 353 344 373 360 373 365 387 370 374 326 303 300 365 322 308 338 358 326 375 334 297 345 318 316 354 336 339 298 341 322 351 312 324 311 342 320 307 333 335 317 361 329 327 351 371 312 348 353 315 351 338 295 324 334 341 348 363 341 335 325 275 336 319 308 320 289 329 299 275 295 288 302 262 328 277 271 290 286 278 291 288 307 241 263 250 292 267 273 234 240 297 259 238 266 255 261 262 266 260 270 279 269 258 251 270 262 238 251 256 268 251 251 264 249 258 274 302 268 251 269 255 265 262 263 238 233 254 270 235 232 243 241 234 247 267 221 263 257 206 241 229 278 238 235 227 265 238 234 265 216 238 231 216 249 228 245 248 235 283 213 221 248 226 210 213 259 252 221 246 235 228 225 239 213 226 225 237 207 222 205 200 206 223 189 211 201 204 198 215 162 193 200 209 169 188 212 220 186 198 184 191 186 171 155 161 212 185 191 157 161 186 150 189 143 141 159 168 177 177 135 153 154 159 188 161 171 155 155 137 174 140 200 174 156 187 135 162 158 171 140 161 169 132 178 193 190 159 180 175 182 150 149 132 131 154 202 145 148 161 156 151 154 143 143 148 186 168 142 151 128 133 163 172 152 140 158 164 174 162 196 167 167 149 177 150 158 140 150 131 139 131 161 139 145 126 140 136 145 125 132 145 155 131 131 139 159 138 125 107 134 141 119 108 118 110 128 113 106 133 130 125 104 108 131 114 121 110 122 128 85 124 117 87 129 127 110 143 121 151 107 110 121 100 103 92 125 124 102 97 102 115 108 130 105 119 101 112 82 100 107 97 104 123 122 116 106 127 110 118 99 97 103 100 116 98 103 109 109 121 110 103 125 138 115 101 92 115 117 123 105 124 128 112 118 123 136 146 128 130 149 151 129 112 129 113 137 104 101 114 122 97 118 114 118 93 101 104 130 120 111 104 93 94 107 89 106 107 106 99 111 88 127 97 89 112 103 96 85 90 88 94 118 85 92 74 94 72 82 90 99 82 97 99 85 91 101 74 80 84 89 68 90 93 84 94 91 83 78 64 90 88 70 62 74 86 72 72 71 93 101 86 75 95 92 85 87 82 85 94 82 82 77 75 79 68 73 83 79 97 78 74 94 73 78 88 95 71 80 62 74 92 74 83 75 65 71 76 74 79 82 85 65 73 74 61 63 65 75 59 58 69 67 75 59 59 63 62 64 69 63 42 55 68 59 71 63 66 79 66 62 65 60 86 76 47 57 68 65 61 59 52 66 54 74 72 62 59 65 63 61 66 80 58 63 48 77 56 66 69 61 74 67 66 62 68 63 58 79 74 77 70 85 80 74 80 67 72 91 58 75 67 78 72 77 73 60 71 58 65 59 72 49 61 69 65 90 69 87 69 76 65 72 62 71 59 72 69 67 55 64 60 54 41 62 51 63 47 64 67 62 68 65 60 69 64 78 63 55 71 73 61 68 69 45 73 95 72 82 69 69 87 137 285 300 318 245 171 199 199 100 54 45 61 46 41 58 47 63 58 60 73 63 62 68 60 57 62 55 57 70 41 60 48 62 60 64 71 65 111 59 88 82 74 85 58 59 48 52 40 52 52 42 53 58 53 53 52 56 53 52 39 40 50 39 48 42 39 56 42 57 52 43 49 48 36 52 47 54 62 51 70 60 50 52 50 65 37 43 36 38 47 57 59 64 45 50 53 61 39 61 67 60 67 42 46 62 45 53 41 39 49 45 44 42 40 48 47 53 49 44 46 41 43 36 47 50 45 55 63 26 33 50 45 54 41 48 51 37 45 44 40 44 52 39 47 40 47 48 33 52 53 63 46 45 33 49 39 47 53 52 35 47 42 47 53 48 62 49 41 34 52 36 47 62 61 51 43 48 59 54 49 81 59 59 48 45 63 40 47 42 56 47 34 71 58 52 51 38 37 45 52 52 51 28 56 42 49 37 29 44 41 40 41 50 46 39 46 37 40 35 39 45 41 56 42 45 45 38 41 45 44 50 43 37 43 38 43 36 39 40 35 42 42 39 43 44 48 40 39 33 37 23 47 41 46 37 38 35 43 56 36 33 26 41 36 51 45 35 51 37 24 33 56 37 35 41 44 43 34 36 43 55 47 52 38 36 46 34 51 45 45 50 36 45 41 45 41 57 39 39 49 47 39 44 41 39 46 44 61 44 52 41 51 43 55 61 47 43 33 41 55 46 31 33 
];
B = [
0 0 0
 261839 80257 181582
 124597 37481 87116
 443584 157452 286132
 274619 87796 186823
 157507 48894 108613
 434351 159960 274391
 336875 112276 224599
 188448 60820 127628
 581355 210406 370949
 601285 203514 397771
 107864 33761 74103
 1732467 635994 1096473
 227171 78118 149053
 72200 23553 48647
 393622 166109 227513
 125225 49252 75973
 38708 13273 25435
 431823 184525 247298
 35542 12035 23507
 36678 13165 23513
 8676 3081 5595
 225 81 144
 8239 3185 5054
 641701 279675 362026
 42180 14835 27345
 54433 21192 33241
 670473 296702 373771
 38691 15558 23133
 81657 32808 48849
 1049302 446385 602917
 76611 30992 45619
 135137 56501 78636
 754145 347486 406659
 514077 235221 278856
 857962 402100 455862
 1563141 731732 831409
 1269420 545662 723758
 791087 362449 428638
 1833036 872478 960558
 716464 294762 421702
 49184 20290 28894
 1664565 774872 889693
 26344 10990 15354
 46844 19468 27376
 2282305 1108579 1173726
 48443 20694 27749
 587513 241802 345711
 3162441 1674669 1487772
 587203 249666 337537
 15 5 10
 22779141 12626661 10152480
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
115 140 2 3
153 28 0 1
260 40 1 2
361 63 0 1
222 63 1 0
222 74 58 1
576 131 127 14
3201 158 165 35
20837 195 223 79
96190 273 321 154
244964 348 395 215
537250 434 535 335
1027448 611 766 511
1870472 809 1033 747
2706991 994 1351 1058
3164099 1428 1815 1662
2807721 1902 2419 2358
2036010 2613 3114 3076
1257185 3868 3918 3928
653421 5127 4749 4765
273314 6668 5441 5381
73642 8299 5845 5789
17286 8768 6086 5934
12466 7902 6144 6184
11117 7958 6264 6549
10589 8655 6395 6627
10898 8065 6608 6828
9809 8042 7046 6996
9762 8836 7561 7227
9578 8732 7896 7941
9783 9189 8408 8459
10763 10104 8875 9224
12365 11236 9585 9443
13259 11734 10313 10387
13566 12613 11404 11450
14269 13394 12162 12341
15573 14344 13604 13546
16856 15924 15064 14878
17346 16939 16557 16687
18595 18503 17958 18209
20567 20681 19835 20110
22652 22687 22622 22579
25362 25309 25192 24898
28352 28558 28443 28369
31737 31632 31577 31639
35531 36003 36016 36354
40326 40658 40352 40375
44411 44326 44495 44495
49021 49521 48922 49245
54387 54083 53372 53349
58647 58146 58088 58500
62252 61918 61228 61934
65784 65363 64721 64644
68604 68674 68311 68552
72408 71631 72432 71341
74160 74784 74421 74231
78961 78948 78633 78530
83980 82740 82798 82566
86983 86039 86478 86070
90318 89484 90515 89961
94304 94215 93708 93321
94816 94374 94495 94199
91840 90374 91845 91097
80583 80284 80315 81265
60357 60901 61628 60408
35773 36665 36489 35430
17964 18971 18666 17745
12595 12456 12472 11580
11419 10330 10633 9923
9561 9889 11056 8894
7286 7579 7235 7755
5287 4430 4996 5337
458 462 377 387
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
