A = [
60689 59867 177170 41864 40326 39817 38293 39197 40501 40081 42450 54185 68296 77229 97575 118229 126976 135367 135722 132092 129823 124426 119023 121586 126176 156811 166004 170847 199947 181373 182362 180873 162868 165212 166064 165756 162000 160811 159790 153461 157595 157053 154810 160907 159681 157143 157412 154627 149385 149897 146523 143898 149492 149251 146228 149995 150995 147159 150561 148059 144309 149198 148028 145091 148887 149013 144536 149606 147190 142927 146076 144133 140792 146225 143333 140491 144599 142395 137429 141115 139988 135982 138602 136615 132536 136146 135898 131049 134433 132600 126591 129613 127905 124986 128350 126596 122593 125191 123582 119249 121143 119988 115452 118245 116110 112947 115204 113909 110880 112517 110946 107591 108060 106616 104251 106279 104056 102011 103070 100583 98674 101167 98313 95230 96152 94670 92135 94213 92712 89472 91073 89639 88122 88498 87191 83529 85260 84365 81728 83225 82113 79376 80144 79155 76833 77618 76942 74288 76287 73943 72414 73491 72962 70811 70614 69928 67289 68948 67745 65806 66869 65575 64349 64314 63974 62327 62102 61736 59068 60566 60295 57908 58698 58282 55537 56381 55591 54096 55099 54235 52469 53170 52245 50814 51655 50345 48891 48821 48778 47013 48250 47706 45639 46864 45195 44000 44318 44202 42353 42889 42745 41267 41713 40918 40173 40332 39898 38438 38956 37962 37099 37874 36756 35947 36717 35886 34787 34773 34274 33488 33750 33534 32761 32576 32404 31657 31355 30962 29765 30700 29938 28761 29221 28849 27959 28547 28235 27516 27381 26863 26088 26563 25864 25458 25925 25283 24329 24822 24266 23559 23709 23472 22679 22961 22481 21930 21930 21938 21028 21132 20876 20301 20299 19949 19710 19757 19303 19173 18966 18805 18130 18100 18047 17428 17597 17420 16705 16931 16719 16017 16112 16028 15435 15942 15338 14981 14998 15033 14469 14548 14286 14006 14093 13848 13353 13408 13104 12926 13169 12641 12665 12478 12397 11889 12094 11635 11677 11658 11671 11118 11074 11016 10786 10622 10798 10367 10287 9950 10028 9919 9671 9412 9579 9662 9158 9276 8934 8888 8899 8950 8367 8620 8531 8278 8105 8199 7898 7815 8040 7542 7543 7584 7230 7377 7328 6992 6932 6819 6754 6956 6905 6530 6502 6357 6198 6344 6223 6016 6047 6022 5726 5872 5769 5579 5642 5571 5407 5475 5242 5199 5093 5168 5072 5054 4941 4920 5034 4750 4589 4647 4551 4439 4550 4409 4381 4437 4312 4236 4161 4203 4094 4069 4032 3903 3864 3832 3780 3720 3722 3709 3633 3632 3519 3519 3379 3277 3307 3299 3203 3209 3038 3114 3063 3075 3017 3040 2888 2926 2836 2827 2667 2910 2711 2688 2690 2654 2713 2478 2517 2521 2492 2401 2487 2366 2533 2328 2190 2324 2192 2304 2226 2150 2141 2020 2156 2054 2101 2019 2015 2071 2049 1968 1973 1922 1970 1807 1884 1830 1775 1761 1830 1792 1735 1763 1749 1735 1672 1640 1570 1696 1645 1556 1542 1496 1467 1529 1501 1413 1456 1472 1468 1429 1436 1466 1383 1443 1308 1366 1382 1326 1339 1286 1236 1322 1284 1240 1293 1195 1246 1208 1293 1185 1207 1197 1120 1108 1173 1125 1222 1071 1085 1132 1052 1029 1079 1069 967 1074 976 1051 1006 1048 1008 1034 986 965 974 955 898 971 877 952 901 941 947 847 890 869 909 859 808 870 856 814 845 834 894 814 843 851 809 797 773 789 816 702 777 730 864 764 750 716 761 793 762 801 755 728 770 661 708 649 684 685 739 769 670 657 706 775 689 670 687 677 639 686 607 627 599 666 632 670 656 635 650 685 654 685 652 662 631 617 654 605 632 666 566 569 584 575 628 568 586 581 616 533 576 577 595 517 587 522 581 512 598 560 507 550 577 530 530 479 551 509 563 486 462 444 449 471 490 423 469 491 484 477 488 468 420 462 456 485 444 461 451 480 465 424 467 448 473 401 433 474 448 447 459 423 434 453 376 401 387 382 408 394 394 411 441 401 408 412 346 391 444 405 368 414 408 330 340 398 343 378 411 338 417 375 365 358 351 399 384 322 394 395 393 394 328 367 347 371 324 356 341 362 397 370 380 322 395 369 369 346 395 353 373 340 355 380 368 367 355 325 376 326 363 364 344 335 370 342 380 344 322 357 349 333 365 299 368 330 364 377 346 386 352 314 357 345 331 332 389 350 323 323 361 382 340 310 335 326 304 312 357 336 263 298 334 248 327 310 297 260 292 277 304 271 271 324 295 271 261 274 288 287 303 247 311 338 314 320 316 271 295 294 334 287 294 292 268 275 287 282 259 298 279 280 267 286 278 302 260 298 271 288 248 261 258 279 278 271 277 263 289 271 250 331 258 258 290 276 228 310 264 280 282 319 281 265 257 308 300 204 278 300 267 318 248 283 212 241 236 256 208 243 229 239 255 273 303 216 230 240 233 252 236 227 229 223 202 220 260 248 236 261 222 226 241 236 212 242 243 250 251 179 231 270 244 207 247 242 255 251 217 288 227 246 261 229 199 185 215 258 257 214 249 268 206 212 257 249 209 240 262 256 228 259 250 249 280 188 246 211 222 237 203 221 208 235 230 308 201 238 237 245 247 218 251 235 260 235 217 261 249 179 233 241 171 208 223 180 286 212 186 238 264 242 247 210 216 214 218 215 173 198 170 227 265 209 250 266 259 272 339 176 231 286 190 156 192 183 170 200 147 155 181 187 203 146 197 177 195 165 185 155 143 184 192 145 169 181 171 163 162 167 166 197 132 149 155 145 133 152 145 148 147 139 153 151 135 118 112 140 156 166 107 152 132 148 198 154 151 127 124 141 150 127 124 117 101 138 158 160 112 128 134 133 156 165 151 147 117 119 133 143 116 109 112 144 117 158 134 135 129 141 158 119 141 136 137 133 146 131 114 114 133 132 133 167 154 115 151 179 122 179 148 302 158 179 199 138 140 131 187 113 128 159 155 132 148 127 191 194 154 179 167 106 142 113 109 125 109 114 111 126 107 146 143 89 127 109 139 159 86 106 122 125 127 137 104 107 89 73 95 84 58 71 80 86 64 90 59 77 79 67 66 65 90 86 81 101 70 105 79 77 91 98 76 104 72 83 71 73 69 80 79 61 85 89 71 80 79 70 82 63 101 88 67 80 70 86 73 89 82 82 64 77 63 61 58 82 69 75 55 85 60 56 65 79 72 65 56 81 62 68 77 56 90 64 72 66 63 66 82 56 59 68 73 51 55 61 76 67 70 48 49 67 61 60 56 60 47 73 49 45 47 66 56 55 58 48 42 60 61 65 54 68 51 69 55 44 59 56 52 57 46 63 48 34 39 55 54 48 56 52 73 70 51 47 53 62 50 36 69 60 61 63 54 53 55 40 60 52 66 69 57 49 62 82 61 74 52 64 67 66 72 64 72 53 53 63 50 61 75 47 57 62 59 55 76 49 57 47 56 53 41 41 56 51 62 64 37 41 37 47 25 37 52 41 41 51 47 62 36 34 43 37 43 46 36 52 35 61 42 31 28 27 66 44 70 42 48 48 52 35 38 42 66 35 51 48 48 38 45 59 56 34 45 29 41 35 32 35 29 35 29 59 52 37 35 51 28 34 58 40 33 48 45 48 30 40 52 27 47 29 28 21 47 17 49 38 25 40 39 39 27 39 35 29 47 26 38 39 42 33 22 46 28 44 50 41 33 34 26 26 22 28 38 23 38 33 28 28 71 29 21 29 24 36 54 20 28 29 28 25 21 16 21 33 41 34 33 38 53 32 14 28 20 15 28 21 12 26 39 25 30 22 38 29 42 38 23 25 30 21 25 31 28 30 29 47 19 31 28 26 28 30 17 26 26 19 19 14 28 13 14 17 10 18 30 34 19 27 19 18 22 18 14 14 11 12 17 18 18 14 20 8 13 13 16 19 16 18 20 9 21 25 13 11 19 21 11 15 24 27 10 33 11 28 25 20 26 11 22 20 23 16 22 17 22 20 18 12 21 14 15 13 17 23 12 15 15 22 22 28 22 21 21 24 16 11 15 15 15 16 16 24 17 22 28 20 9 18 7 22 16 18 22 27 16 20 15 17 9 21 17 18 12 19 19 17 24 21 23 20 29 19 29 34 29 19 23 22 24 13 32 19 33 23 14 13 18 18 16 9 9 16 17 12 14 11 12 17 17 8 8 19 22 12 20 8 12 13 10 11 11 6 13 21 14 13 22 26 20 18 17 11 18 13 26 15 17 18 14 29 23 17 20 13 15 7 15 13 17 14 16 10 31 53 42 23 10 27 17 18 19 22 19 17 30 24 22 19 16 23 28 19 24 28 28 25 22 31 41 33 35 39 21 30 40 15 21 17 15 17 15 23 12 20 27 18 19 17 18 14 13 19 4 16 22 13 20 19 20 12 9 24 13 23 12 17 14 15 12 18 22 6 10 6 10 17 9 18 6 16 7 9 13 16 14 13 11 9 5 18 8 40 10 1 11 14 9 4 4 9 10 11 6 13 25 12 15 9 16 11 13 17 16 11 10 22 13 15 12 18 30 6 11 11 11 25 20 5 16 22 15 11 32 21 7 16 13 11 9 10 6 11 6 12 11 24 5 15 9 21 14 5 2 3 11 14 5 15 11 3 6 8 10 10 10 9 13 9 12 7 4 19 6 8 7 7 5 8 6 6 4 4 9 4 6 6 9 2 7 2 9 6 6 5 5 8 7 5 10 7 7 3 5 5 3 7 10 6 13 4 9 13 9 10 15 6 3 14 8 10 3 13 10 12 13 11 14 20 10 16 14 18 14 11 15 7 26 6 18 11 22 11 6 7 11 5 5 5 12 1 8 8 4 10 5 7 13 5 3 8 4 3 9 3 2 4 6 4 8 7 4 4 5 7 1 3 3 11 3 2 6 7 3 7 0 3 1 4 4 3 4 3 3 3 5 7 5 6 7 5 7 3 10 5 8 11 6 2 7 15 11 3 6 3 
];
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
 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
0 1 1 2
3 3 2 0
1 1 7 4
2 2 25 24
71 6 24 30
1166 4 45 65
8070 9 62 76
33052 15 107 113
117017 20 161 160
250006 41 224 210
348683 62 341 347
367395 134 503 519
359108 239 840 840
311930 419 1215 1222
230119 709 1739 1741
140354 1033 2377 2355
62021 1628 3147 3099
18564 2239 3870 3978
7138 3276 4799 4947
6338 4329 5807 5853
7267 5808 7071 6899
8748 7376 8498 8473
10200 9124 9850 9950
11736 11060 11591 11709
13744 13337 13338 13648
15594 15633 15491 15978
17944 17593 17949 17859
20131 19842 20134 20244
22317 22258 22223 22391
24457 24198 24228 24347
26519 26200 26375 26198
28099 28444 28116 28257
29741 30093 29768 29877
31058 31124 31434 31128
32532 32839 32836 32398
34127 34406 34085 34455
36137 35893 35964 36144
37543 37860 37803 37733
39784 39759 39751 39876
41354 41484 41628 41386
43797 43344 43828 43919
46382 46468 46365 46454
48638 49000 48636 49012
51673 51427 51058 51507
54487 54001 54082 54017
56112 55561 56062 55935
58284 57875 57479 57575
58668 58671 59481 58795
60251 59910 59805 60524
60091 59884 59990 60536
58844 59116 58894 59277
57599 57900 57853 57661
55386 55688 55547 55457
51658 52639 52551 52476
46655 46861 46277 46895
40378 41087 40829 41074
32923 33417 33015 33589
26836 27407 26745 27242
17399 18220 17482 17463
6854 7422 7141 7095
1104 1092 1098 1038
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
