A = [
101140 99939 266291 64260 63089 60801 58927 60496 63182 62178 67957 88093 109726 120643 150654 181894 189090 195413 196091 192021 191985 184706 176771 180967 186899 237306 252803 262527 312779 287922 289374 291514 266843 271052 272895 272845 267392 268054 264491 255686 262792 260507 257925 268936 266827 261556 261280 256489 248130 248234 243814 239181 248931 248481 243224 251315 250621 242985 249128 247547 240323 247590 246403 239367 247211 246243 239386 247565 243242 235321 241718 238269 232801 240799 236948 230801 236676 233695 226589 231968 229994 223252 226976 224435 217066 223494 219687 213675 219230 215855 205758 209876 207098 201571 206133 202826 197282 202568 197947 191747 195939 193354 185568 189274 185381 179946 184024 181788 175676 178742 176567 170467 171714 170173 164322 165759 163708 159547 161797 159001 153001 157336 152202 148048 149768 146997 143164 144547 143166 138131 140115 137674 133065 135552 131589 127876 129432 127632 124219 125569 124029 120079 120995 118987 114575 116256 114283 110799 113749 110584 107314 109671 107505 104056 105170 102872 99838 101089 98336 96388 97729 96311 93010 94458 92675 88942 89672 88470 85053 87445 85559 82582 83376 82515 79431 80093 78933 75839 77058 76478 73110 74784 73330 71123 72084 69948 68639 67478 67644 64486 65909 65171 62115 63592 62577 59675 60610 59365 57482 58072 57473 55313 55877 55056 53347 53645 52839 50524 51745 50138 49121 49780 48833 46966 47630 46787 44946 45758 45162 43263 44036 43029 41722 42207 41325 40022 40051 39490 37933 38577 37682 36260 37091 36008 34997 35548 34803 33565 33456 33406 32242 32339 31897 30674 31310 30743 29542 30491 29300 28280 28511 28141 27000 27389 26986 25899 26274 25593 24770 24928 24672 23779 24255 23455 23199 22885 22513 22097 21781 21364 20620 21033 20389 19638 19624 19436 18930 18965 18767 18170 18346 17858 17352 17731 17118 16665 16733 16184 15886 15868 15848 15320 15204 15370 14209 14256 14284 13945 14019 13485 13249 12999 13088 12491 12600 12302 12032 12128 11969 11626 11411 11148 11020 10831 10726 10368 10429 10218 9929 9950 9681 9377 9667 9337 9203 9048 8820 8476 8700 8846 8252 8389 8168 8010 7950 7974 7650 7715 7554 7212 7248 7274 7098 6973 6784 6613 6611 6404 6445 6525 6334 6092 6066 5973 5743 5978 5696 5547 5513 5519 5307 5354 5423 5070 5010 5133 4858 4809 4793 4671 4644 4668 4526 4457 4381 4278 4260 4103 4239 4032 3976 3979 4085 3956 3874 3952 3776 3794 3633 3721 3462 3535 3421 3389 3382 3375 3341 3292 3256 3124 3044 3172 3081 3090 2919 2897 2900 2833 2787 2734 2565 2680 2566 2700 2501 2585 2499 2400 2406 2399 2296 2464 2359 2279 2325 2220 2262 2094 2094 2139 2213 2103 2113 1979 2136 1995 1886 1937 1972 1988 1927 1837 2004 1866 1771 1798 1814 1733 1817 1810 1735 1663 1681 1671 1755 1516 1686 1558 1668 1640 1613 1585 1498 1674 1519 1650 1510 1571 1398 1504 1574 1510 1401 1429 1360 1453 1427 1428 1377 1377 1328 1387 1298 1356 1339 1377 1308 1295 1290 1294 1328 1349 1157 1347 1286 1260 1334 1263 1213 1188 1276 1212 1173 1180 1195 1185 1153 1099 1147 1114 1187 1143 1104 1116 1075 1066 1090 1149 1067 1151 1086 1153 1049 1108 1046 940 1054 940 996 1065 973 1018 981 1012 977 935 1015 894 933 993 954 948 924 896 957 920 974 947 1036 922 942 845 896 926 878 828 925 877 997 811 837 820 870 923 868 915 922 814 944 866 820 805 839 938 947 910 865 761 816 924 862 743 824 741 767 809 761 802 790 772 794 817 833 758 867 846 827 847 827 872 752 758 769 722 781 772 743 756 743 722 749 734 741 757 786 683 723 723 766 721 772 645 733 698 704 790 686 669 704 764 748 622 699 657 685 658 608 647 655 684 605 608 582 635 633 631 658 627 608 626 598 612 585 594 593 649 641 564 595 552 627 545 526 589 571 571 531 573 531 581 506 477 476 492 512 521 467 568 554 580 487 531 495 512 504 503 487 543 534 474 532 513 470 531 502 500 545 470 520 528 458 475 514 483 485 509 532 545 440 541 501 500 510 472 481 481 518 453 497 487 479 457 528 488 504 493 501 517 498 529 496 477 457 480 514 464 487 497 490 531 540 484 559 520 457 496 471 445 467 400 490 461 491 519 475 499 506 417 529 525 447 473 549 452 448 475 479 510 504 466 463 430 431 430 417 433 463 422 433 338 430 419 432 387 401 370 434 412 377 387 388 355 379 366 385 361 453 371 385 415 488 431 401 396 424 401 428 389 364 371 365 380 420 384 360 379 382 401 385 421 414 402 360 420 369 392 361 373 359 359 367 370 312 348 370 374 365 437 386 329 418 371 346 423 377 380 413 443 320 449 373 423 401 318 385 414 304 441 370 382 326 334 326 351 302 366 314 322 358 377 438 310 354 350 364 303 361 360 299 354 319 281 356 338 352 381 341 326 354 326 313 367 287 332 339 277 356 372 340 373 342 328 365 337 349 385 296 359 357 292 295 260 340 320 362 322 351 350 347 373 348 341 336 364 335 337 321 433 314 308 374 293 338 328 347 366 316 324 329 364 302 363 298 311 345 354 437 353 390 310 381 317 317 316 341 268 361 326 294 290 309 267 417 268 289 310 362 339 315 297 311 290 289 326 336 294 323 357 459 307 305 370 395 397 451 318 358 436 288 264 276 264 238 295 204 221 269 234 232 241 213 263 292 264 303 202 193 256 254 208 220 269 248 210 194 250 217 254 218 197 201 185 216 208 217 234 181 237 232 238 205 194 216 199 203 207 179 183 196 224 259 214 226 177 157 199 191 200 157 182 196 168 213 194 166 166 212 186 242 188 214 201 198 155 198 192 169 174 140 220 170 203 162 219 173 178 251 180 208 188 172 191 220 210 173 206 178 183 159 249 230 188 204 322 163 227 224 432 243 251 274 159 206 226 249 162 178 213 204 171 232 204 300 304 230 242 236 165 206 133 148 194 166 146 164 179 165 180 225 128 182 191 154 224 142 151 193 171 198 146 156 173 140 101 141 116 78 99 123 126 104 92 80 100 118 98 99 124 108 136 91 168 120 126 123 137 134 110 99 117 107 125 109 91 80 127 109 120 102 104 103 114 88 99 114 111 125 141 115 115 98 110 107 112 97 107 86 111 91 89 104 95 83 109 72 100 61 102 84 94 77 91 88 110 109 86 91 62 83 84 113 83 86 79 111 101 80 126 96 80 85 103 98 84 90 58 62 63 73 92 82 72 52 87 77 55 55 67 69 65 76 71 49 89 87 78 100 60 80 94 100 64 90 88 72 69 72 67 81 61 71 83 81 63 71 73 124 86 80 95 70 77 80 52 86 84 96 98 77 97 88 59 107 96 88 87 80 72 104 101 76 95 74 89 81 130 108 105 96 78 95 94 61 100 129 72 80 77 96 86 87 61 63 82 69 80 87 81 66 62 73 97 61 50 71 58 56 55 72 52 68 74 67 74 46 48 48 48 63 64 54 64 50 76 37 48 61 61 84 59 95 60 70 67 72 53 79 63 94 61 66 64 72 45 60 59 66 41 51 36 53 62 60 39 62 59 47 61 68 59 75 44 54 49 77 55 47 69 51 56 44 59 76 40 61 46 35 32 56 27 51 53 35 46 44 63 32 60 35 34 51 35 55 44 43 53 38 39 52 63 82 45 32 36 34 32 41 29 39 35 31 43 27 60 59 36 46 36 49 43 71 30 42 44 39 43 29 15 30 42 52 33 36 53 50 35 27 31 30 33 43 25 31 46 30 41 26 25 31 47 44 40 23 38 35 26 29 35 61 31 35 43 38 28 24 45 43 21 31 37 40 26 30 18 25 22 16 24 20 21 30 38 19 30 26 16 26 16 20 18 14 21 20 20 28 22 18 13 28 24 22 31 25 19 25 18 26 31 22 18 19 22 22 31 34 23 18 27 7 43 34 23 24 20 33 32 32 20 31 17 31 29 21 25 23 22 31 19 29 16 15 18 18 20 32 34 25 32 15 32 16 17 27 23 29 35 26 34 19 22 23 25 22 21 25 35 28 20 22 40 28 26 19 20 17 19 19 20 25 27 25 22 31 18 24 32 24 15 31 41 23 13 40 39 32 21 26 28 29 25 30 37 16 24 15 16 14 16 25 17 11 25 18 13 25 18 12 38 14 23 23 10 19 18 24 10 23 16 18 33 25 15 22 38 23 18 25 16 36 25 30 19 26 28 25 34 26 22 28 25 40 31 20 18 24 28 28 21 31 84 82 49 27 31 34 33 35 36 30 48 37 44 35 29 36 38 50 29 26 43 48 38 42 35 52 51 69 66 36 42 48 32 31 21 33 21 31 22 16 24 44 19 27 24 22 31 13 33 11 27 26 25 20 23 29 22 29 23 13 21 15 18 18 21 11 24 12 10 10 23 11 23 13 26 23 23 14 11 17 27 17 21 14 20 16 7 12 41 28 9 16 17 13 9 12 13 20 22 12 26 23 25 32 9 24 23 16 20 16 11 29 18 12 14 13 17 38 18 11 11 18 27 32 14 42 23 31 14 36 23 10 20 11 9 12 22 7 20 11 25 9 19 11 14 14 34 16 19 12 3 13 19 6 19 14 11 12 15 12 9 17 14 10 15 16 9 9 19 11 8 7 17 15 17 5 7 0 0 10 7 11 12 11 10 10 11 10 11 7 12 3 4 9 13 11 5 10 3 5 9 4 14 14 13 15 3 12 18 15 17 13 10 6 17 21 13 9 18 11 19 10 5 19 30 12 17 24 18 21 16 22 8 31 17 15 12 22 7 7 8 15 9 11 9 18 11 6 5 10 8 14 10 8 6 5 6 9 8 11 6 3 5 12 5 8 7 6 4 5 4 3 8 7 5 4 2 3 6 3 4 5 1 2 5 4 5 9 1 5 14 9 12 2 8 9 3 10 7 11 4 4 7 4 6 5 11 14 5 2 4 
];
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
 37651 12930 24721
 36516 11995 24521
 31074 11355 19719
 37563 13981 23582
 29238 10502 18736
 32614 12226 20388
 31231 11176 20055
 26471 10131 16340
 37399 14174 23225
 33205 12785 20420
 28914 11661 17253
 41882 15372 26510
 27807 11548 16259
 65849 24058 41791
 35089 15101 19988
 25164 11181 13983
 34152 14096 20056
 36766 16490 20276
 40368 17071 23297
 43728 19908 23820
 29436 13115 16321
 33103 14920 18183
 46018 20967 25051
 32169 14222 17947
 59430 28876 30554
 43724 19406 24318
 58658 24708 33950
 35703 18553 17150
 46664 21179 25485
 90516 48188 42328
 17580039 11052266 6527773
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
0 9 0 0
0 1 0 1
0 0 0 0
1 2 0 1
0 3 2 2
2 2 10 5
11 1 28 32
109 6 46 54
1877 10 74 51
13156 8 109 74
52261 18 132 120
183054 26 208 159
395795 49 295 247
562586 96 430 415
590380 220 686 700
570808 398 1184 1126
480583 748 1733 1715
325926 1131 2499 2466
161409 1777 3469 3367
45334 2478 4395 4371
9820 3600 5409 5628
7342 4817 6887 6913
8491 6433 8252 8260
9894 8339 9809 9959
12012 10465 11676 11670
14130 12635 13653 13812
16163 15867 15864 16035
18823 18290 18705 18815
21509 21426 21583 21505
24831 24776 24708 24874
27573 27613 27845 27897
31006 30505 31038 30698
33701 33487 33197 33793
36430 36432 36209 36535
39047 38998 39146 38713
40814 41005 41201 41087
42439 43488 42881 42688
44608 45448 44699 44595
46543 47258 47046 46847
48695 49425 49189 48834
51603 50872 51351 51248
53616 54235 53989 54071
56470 56531 57181 57042
59992 59356 60234 59723
63918 63506 63045 63718
67301 67437 67612 67574
71780 70945 71252 71471
76079 76011 75465 75416
78616 78696 78703 78254
82125 81784 81290 81466
83726 83721 83415 83941
86136 85250 85527 85615
86213 86355 85927 86495
85331 86082 85551 85851
84253 84962 84435 83965
81122 81402 81216 81102
76964 77614 77350 77932
69379 69286 68527 69695
60583 61103 60145 60867
49877 50186 49498 50456
40102 41274 40507 40886
26601 27778 26895 27558
10768 11513 11079 11142
1728 1840 1878 1745
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
