A = [
67432 65974 195000 46199 44423 43845 42178 43057 44610 43731 46436 58629 73507 82580 104147 125414 134634 143560 143772 140145 137605 132112 126286 128913 133693 165851 175540 180832 211330 192480 193427 192060 173530 176152 177742 178156 173551 173260 172814 165960 170824 170422 169082 175577 174462 172684 173194 170014 164853 164942 162018 159144 165121 165504 161769 165871 167220 162939 167075 163981 159936 165146 163695 160832 165269 165323 160758 165988 162793 159065 162232 160248 156354 162819 158989 155997 160137 157825 152873 156675 155390 150478 153824 151610 146817 150577 150174 145358 149076 146662 140289 143194 141568 138429 141761 139714 135463 138460 136364 131780 133918 132734 127469 130394 128558 124870 126942 125516 122335 124163 122362 118527 119245 117330 114571 116955 114529 112557 113795 110758 108764 111602 108411 105384 106084 104449 101791 103825 102144 98487 100043 99152 96938 97512 96165 91818 93746 92736 89844 91326 90443 87139 88039 87085 84615 85313 84857 81764 83989 81576 79914 80801 80705 77992 77916 77114 74278 75967 74841 72709 73669 72361 71062 71218 70812 68935 68585 68210 65130 67022 66912 64165 64902 64528 61531 62459 61780 59873 61101 60007 58181 58755 57883 56133 57145 55806 54327 54048 53863 52081 53505 52564 50532 51814 49804 48707 49095 48773 47066 47561 47228 45642 46151 45450 44490 44707 44157 42654 43075 42115 41192 41826 40711 39919 40726 39806 38652 38520 38031 37156 37577 37183 36451 36007 35862 35054 34807 34455 33053 33787 33164 32012 32369 31947 31091 31758 31364 30506 30382 29942 29136 29480 28679 28235 28846 28236 27166 27700 26993 26279 26273 26163 25385 25574 25188 24513 24709 24586 23599 23642 23481 22911 22749 22392 22160 22122 21651 21505 21482 21153 20461 20446 20361 19629 19842 19670 18794 19021 18804 18108 18235 18128 17573 17918 17307 16834 16890 16940 16308 16390 16057 15725 15835 15671 15056 15088 14792 14555 14852 14416 14369 14134 14073 13485 13715 13345 13244 13177 13148 12673 12657 12534 12482 12137 12301 11895 11726 11389 11480 11300 11046 10777 10942 11073 10515 10651 10172 10218 10281 10274 9677 9912 9790 9547 9375 9429 9166 9014 9233 8690 8768 8709 8360 8510 8441 8046 7932 7919 7803 7993 7941 7567 7481 7406 7137 7315 7132 6999 7040 6949 6732 6790 6631 6440 6551 6388 6294 6413 6199 6023 5969 6071 5885 5863 5747 5742 5977 5592 5432 5516 5384 5273 5349 5251 5173 5233 5215 4963 4953 4977 4867 4826 4789 4682 4663 4537 4538 4483 4431 4408 4297 4299 4234 4222 4081 3949 3982 3946 3870 3940 3708 3786 3820 3817 3719 3682 3640 3594 3469 3501 3325 3477 3342 3345 3282 3285 3327 3080 3154 3194 3117 3078 3059 2961 3195 2902 2800 2922 2797 2855 2764 2737 2687 2575 2761 2570 2580 2544 2591 2625 2602 2468 2476 2389 2496 2363 2434 2373 2287 2266 2330 2258 2265 2238 2225 2216 2136 2107 1996 2163 2107 1977 1917 1915 1907 2006 1882 1835 1900 1935 1856 1844 1852 1863 1839 1855 1744 1766 1777 1803 1762 1658 1653 1750 1650 1663 1681 1572 1660 1568 1640 1542 1605 1593 1436 1512 1539 1502 1632 1456 1413 1489 1404 1419 1409 1458 1328 1403 1279 1359 1335 1402 1317 1319 1358 1355 1302 1284 1250 1247 1197 1304 1267 1255 1283 1143 1231 1207 1241 1182 1139 1205 1182 1173 1204 1188 1214 1131 1199 1177 1082 1088 1108 1075 1122 1041 1118 1029 1150 1105 1083 1028 1074 1087 1069 1140 1103 1042 1101 947 1022 956 1011 959 1054 1059 927 963 996 1050 1010 957 1009 970 918 986 887 902 906 947 970 1006 905 925 890 976 1009 1001 918 920 897 864 934 899 906 926 825 870 880 868 913 871 895 824 859 762 850 825 835 778 846 814 859 746 882 810 776 821 869 836 785 757 779 763 810 689 705 676 720 677 748 628 715 731 720 703 706 735 685 682 690 733 693 686 738 706 719 702 721 707 748 654 726 767 738 703 745 672 659 797 638 662 641 616 636 673 630 626 683 660 643 636 618 640 682 637 631 688 653 578 583 630 560 621 625 585 612 586 573 566 552 561 565 543 596 560 601 571 526 573 555 555 503 523 528 543 591 556 587 525 597 556 537 509 613 528 588 536 545 602 534 551 585 527 604 522 623 588 578 576 626 562 575 616 573 630 629 592 579 521 564 589 559 602 584 593 557 518 555 551 533 537 582 583 547 540 587 628 521 551 540 509 520 518 565 532 515 475 481 453 534 521 539 464 485 471 484 421 414 496 488 435 383 428 439 439 447 409 528 520 465 484 493 432 455 449 509 434 421 467 426 420 453 424 418 452 437 440 382 449 399 446 401 418 423 423 405 416 389 448 415 445 445 422 446 441 394 492 385 404 428 432 384 478 420 418 427 480 388 409 378 455 456 361 426 460 398 475 390 438 368 397 367 389 361 374 360 401 369 399 442 309 347 340 348 385 339 334 379 357 326 347 389 365 354 431 339 371 368 365 356 381 382 367 386 283 368 418 360 344 382 343 393 400 328 407 350 379 404 339 315 310 339 375 372 346 369 376 298 312 385 366 343 386 361 384 330 387 351 358 374 294 320 327 339 311 292 318 292 337 333 391 295 318 329 359 341 307 377 314 344 319 303 356 341 235 296 335 246 289 322 271 389 287 264 298 375 322 345 310 305 299 308 296 273 298 264 314 389 310 347 380 374 384 439 297 337 383 303 244 294 274 267 297 234 243 280 293 303 227 311 260 319 270 288 254 242 262 300 245 262 278 282 283 268 280 268 336 231 265 241 228 225 260 267 246 280 247 276 276 217 222 196 213 246 247 176 223 216 227 301 233 213 204 213 215 243 178 189 194 166 192 210 243 178 187 192 197 205 225 209 203 175 186 206 193 174 172 169 203 161 207 184 192 187 212 212 175 213 189 204 191 209 204 184 191 207 213 202 246 249 189 224 263 183 255 234 362 236 250 252 198 195 173 248 163 173 219 235 193 211 201 260 261 229 270 219 172 234 169 176 241 202 211 202 206 176 236 196 160 183 178 209 227 143 162 192 190 169 200 153 177 130 138 163 125 113 111 135 126 112 137 109 121 113 119 114 127 139 131 133 138 113 150 125 125 118 131 110 155 142 125 107 120 116 138 141 115 125 132 112 136 130 108 127 129 150 153 112 126 107 119 109 126 113 129 102 106 95 96 90 121 107 122 95 121 94 89 100 122 112 107 94 127 103 97 115 93 135 121 131 123 122 99 135 84 107 106 106 87 87 94 124 114 120 71 90 112 108 113 98 97 91 111 85 75 78 94 91 96 101 78 94 92 108 99 94 101 89 117 84 97 83 85 75 86 79 91 92 65 77 87 95 81 86 78 105 104 82 100 103 103 69 68 92 88 104 103 83 90 100 76 87 83 98 92 90 75 88 103 93 105 69 90 94 90 90 83 97 69 70 88 90 96 96 88 105 89 108 96 115 84 89 89 91 90 70 77 78 119 94 120 65 85 72 82 68 74 84 68 68 94 78 116 98 72 83 68 81 89 74 80 71 104 79 64 64 43 107 75 94 84 71 76 92 75 90 70 134 63 105 98 127 95 89 121 95 79 90 88 96 82 57 65 58 74 62 85 83 61 55 81 70 54 87 81 63 65 77 82 58 77 80 62 80 67 52 39 75 41 83 65 45 56 55 57 49 54 45 49 55 53 69 65 76 74 52 79 56 80 89 88 92 72 90 83 66 65 78 82 79 68 76 72 107 74 44 71 48 74 92 52 53 61 53 61 48 39 48 64 70 67 71 68 94 70 38 66 51 44 50 50 40 61 77 56 52 46 66 65 81 61 50 52 60 43 48 54 53 47 48 73 31 64 54 50 48 52 43 40 49 44 44 34 55 37 35 47 48 33 50 52 37 36 34 35 39 29 28 33 20 26 33 40 39 29 39 25 30 19 31 34 39 40 42 28 39 46 28 30 35 42 28 34 44 62 26 48 29 43 43 36 51 25 43 60 39 42 47 43 44 40 40 33 31 35 44 32 39 31 32 30 33 46 37 44 40 42 36 47 41 29 33 33 33 43 31 49 29 47 48 42 20 40 26 37 32 34 36 39 31 25 26 36 22 30 27 35 27 26 31 34 40 30 32 40 34 38 40 45 43 29 32 32 32 26 48 28 49 41 26 23 46 35 29 32 23 31 39 22 38 32 38 26 41 24 27 36 31 32 37 26 28 20 22 28 26 12 30 30 22 25 35 35 33 27 25 20 32 40 40 24 30 37 32 42 39 26 43 32 37 25 27 41 30 25 33 25 54 74 77 38 25 58 63 36 41 41 46 55 55 51 40 29 34 43 49 35 41 41 69 46 41 61 69 58 65 62 42 41 57 30 48 35 36 41 43 46 48 42 50 33 40 39 50 28 38 34 32 32 50 33 34 33 37 34 33 38 48 42 29 29 32 32 37 32 29 21 17 13 28 31 23 30 18 28 32 21 24 30 27 31 23 21 14 31 30 53 31 19 17 31 27 22 18 26 27 26 21 29 39 30 26 21 28 17 30 31 39 28 28 47 37 33 40 33 63 31 45 33 40 43 49 33 37 46 34 22 47 44 31 40 28 36 23 28 20 27 18 31 20 31 17 24 15 28 23 8 14 10 19 20 19 22 21 9 21 14 21 18 16 13 24 13 17 16 9 34 23 19 14 10 10 17 16 13 12 18 18 7 12 16 17 18 19 16 26 20 19 17 16 17 16 10 16 13 19 10 12 11 16 18 22 12 22 15 23 15 16 18 21 13 10 22 20 19 10 14 22 13 21 25 21 26 19 23 17 24 18 19 23 17 40 8 31 19 30 13 12 15 18 10 16 9 13 4 12 12 11 15 8 13 16 13 7 14 8 10 14 10 10 8 12 25 18 15 13 17 14 19 10 7 10 20 21 16 12 14 13 23 5 15 17 13 13 11 16 15 12 12 17 20 15 10 16 23 23 26 18 24 19 32 13 16 11 26 26 16 17 10 
];
B = [
0 0 0
 43212 10017 33195
 51070 12319 38751
 52652 14029 38623
 45543 11260 34283
 52547 13697 38850
 61304 16233 45071
 66689 17615 49074
 76218 20931 55287
 95535 28969 66566
 72879 21831 51048
 187900 72212 115688
 41550 13446 28104
 35496 12138 23358
 26086 9194 16892
 19570 6337 13233
 14712 4326 10386
 16522 5105 11417
 11746 3354 8392
 16963 4924 12039
 16124 4584 11540
 26772 7944 18828
 26512 7718 18794
 31226 9733 21493
 25245 7476 17769
 34543 10863 23680
 32216 10505 21711
 61538 21610 39928
 20493 7443 13050
 59326 21607 37719
 24961 9234 15727
 23982 8478 15504
 20510 7983 12527
 25041 9964 15077
 19597 7362 12235
 21837 8860 12977
 20849 7891 12958
 17644 7127 10517
 25341 10133 15208
 21902 8993 12909
 19231 8235 10996
 28147 10954 17193
 18522 8238 10284
 44495 17226 27269
 23241 10768 12473
 16515 7784 8731
 23497 10388 13109
 24440 11812 12628
 26263 11748 14515
 28705 13858 14847
 19678 9350 10328
 21774 10293 11481
 30651 14855 15796
 21586 10040 11546
 38737 20006 18731
 28767 13689 15078
 39567 17682 21885
 23925 13299 10626
 31068 14875 16193
 57099 32007 25092
 11595839 7666179 3929660
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 3 0 0
1 1 0 0
0 2 1 0
1 1 1 2
4 3 3 0
3 1 7 4
4 2 25 25
72 6 27 32
1211 5 49 68
8413 10 67 80
34547 16 111 114
121730 21 170 164
257744 47 230 217
357201 66 351 356
375624 145 526 535
367401 249 873 873
319381 450 1255 1258
235984 745 1792 1801
144141 1083 2456 2423
63754 1705 3240 3198
19193 2318 3999 4124
7482 3449 4966 5154
6625 4529 6012 6048
7614 6075 7305 7154
9154 7654 8806 8759
10643 9509 10168 10265
12396 11582 11984 12160
14413 14194 13838 14117
16416 16353 16027 16505
18767 18374 18588 18502
21092 20795 20830 20972
23393 23318 23077 23191
25826 25224 25158 25338
27821 27409 27381 27289
29695 29904 29297 29512
31197 31487 31144 31328
32718 32633 32836 32640
34555 34659 34483 34193
36190 36435 35882 36312
38559 38382 37868 38114
39943 40045 39932 40067
42168 42133 42141 42261
43923 43978 43985 43846
46639 46506 46535 46669
49450 49433 49125 49357
52500 52899 51705 52247
55171 54870 54189 54677
57953 57627 57453 57312
59542 59079 59475 59452
61676 61367 60791 60930
62146 62134 62961 62268
63726 63458 63196 64187
63721 63696 63803 64441
62470 62947 62403 63174
61469 61736 61550 61565
59353 59528 59424 59473
55135 56060 55835 55941
50015 50137 49375 50437
43137 43817 43393 43970
35158 35692 35125 35883
28883 29764 28900 29338
18527 19432 18663 18684
7640 8354 7970 7980
1563 1568 1552 1454
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
