A = [
1517578 1409416 5900739 1371618 1301608 1267637 1224648 1239454 1226527 1198368 1200312 1223710 1231900 1242367 1260925 1269581 1283121 1310180 1303599 1298825 1317385 1307906 1307968 1325529 1400588 2405959 2419876 2479892 3467386 3363337 3462979 3491305 3379480 3451870 3491471 3465166 3387894 3377734 3349654 3301693 3273524 3263572 3244611 3225450 3223676 3177201 3138912 3098818 3049072 3009179 2977935 2950527 2931789 2905356 2877103 2866765 2812904 2772175 2740533 2700523 2664950 2633814 2603597 2574452 2550076 2521127 2486112 2454938 2424651 2390351 2357416 2321809 2295771 2267181 2241930 2209940 2184960 2153723 2122600 2091322 2059185 2026793 2004870 1976480 1949326 1925521 1901687 1873824 1845843 1812537 1787289 1760691 1734136 1710879 1689876 1670178 1640763 1617026 1595307 1568675 1543402 1520481 1496684 1476021 1455204 1437422 1415842 1397262 1372392 1352684 1330353 1305677 1285764 1264203 1245480 1227074 1209171 1190516 1182493 1155684 1132606 1113417 1095122 1076030 1056072 1038484 1020811 1004899 990320 976968 962228 946422 929920 914690 898581 881888 905442 852703 839979 827022 812208 798409 784783 772505 761392 745838 732810 720593 706912 695503 684695 672257 659317 649900 636432 625412 616071 604741 591832 582780 574741 563440 551231 541902 533838 522250 514647 504051 494652 485892 478177 468706 461348 453718 445332 436589 428110 421412 415090 406331 399987 391369 386326 378409 373071 366773 359506 352437 345301 339767 334874 330511 322839 317646 313262 307861 302930 297505 291904 286577 280249 276168 270277 265591 260837 256265 251378 247220 242595 238801 234949 229516 225547 220909 217954 214683 210593 205489 202181 199319 196432 192135 189431 185281 181823 177660 175644 173004 170298 167517 165286 162083 159015 156067 152397 150671 147826 144930 141422 138323 137312 136131 133743 130938 128855 127761 126248 123408 120964 118836 116469 115147 113423 111750 109839 107122 104684 104241 101978 101155 99656 97377 95963 95573 93059 92081 89615 87915 86452 86096 84307 83351 82138 81736 80279 77256 77215 75187 74065 74730 74988 71916 72065 70749 70380 68877 66640 66598 67552 65657 64220 62993 62462 61608 60905 59654 58826 57924 57248 58315 56734 55245 54637 55323 53602 52092 51294 52151 50854 49912 49036 48209 48588 47664 47200 45683 45920 44765 43117 43007 45693 40641 39961 39144 38281 39739 38461 36583 34833 34596 34240 33805 33203 32803 32303 31644 31782 31053 31206 31039 31835 31584 31269 31207 30884 30018 29634 28534 28991 28168 28262 28705 28811 27381 27673 27125 28276 26400 27483 26669 26788 26111 25487 25179 24104 23770 24076 23492 22881 22802 23516 22229 22073 22420 21916 22041 22034 22083 21430 21220 20329 20279 20052 19849 22784 21627 20978 21325 21635 21649 21876 21433 22235 21234 21097 20467 16347 16587 16713 16317 16265 16001 15730 15445 15578 16193 15143 15327 14995 15285 14722 14735 14654 14951 14813 14616 14528 14094 14196 13927 14052 13793 13489 13368 13260 13295 13400 13298 13391 13159 12893 12233 12692 12498 12141 12188 11982 11849 11710 11704 11484 11430 11003 10863 11010 10600 10670 10509 10533 10322 10204 10225 10248 10034 10126 10058 9969 9794 9808 9654 9710 9649 9430 9270 9109 9092 9269 9129 8897 8950 8835 8692 8771 8740 8540 8493 8470 8355 8515 8350 8423 8147 8151 8172 8342 8084 8139 7958 8133 7959 7961 7959 7778 7687 7816 7847 7913 7825 7636 7722 7668 7376 7468 7513 7524 7285 7317 7336 7141 7052 6969 7265 6954 7380 7323 7027 6900 6938 6654 6663 6622 6820 6644 6580 6488 6799 6540 6578 6664 6566 6623 6514 6555 6304 6182 6374 6394 6249 6093 6252 6264 5780 6089 6272 6292 6026 6136 6212 6249 6174 6155 6032 5859 6013 6170 5938 5925 5997 6062 5819 5514 5505 5486 5639 5365 5399 5288 5409 5439 5348 5465 5425 5280 5421 5422 5050 5052 4931 4954 4996 5090 5013 4797 4832 4698 4692 4602 4804 4663 4688 4851 4782 4760 4817 4630 4542 4530 4389 4490 4472 4579 4446 4214 4337 4326 4372 4326 4510 4404 4392 4341 4241 4420 4393 4135 4150 4109 4097 4089 4110 3961 4017 3862 3968 3916 3916 3884 3920 3706 3756 3847 3934 3940 3789 3580 3861 3644 3803 3648 3442 3553 3447 3417 3316 3275 3453 3107 3238 3244 3126 3222 3076 3033 3115 3272 3272 3114 3043 2984 3181 3077 3071 3121 3072 3164 3151 3050 3126 3132 3259 2864 2858 2801 2819 2782 2787 2874 2787 2667 2754 2527 2714 2632 2604 2616 2577 2604 2549 2541 2579 2609 2549 2602 2620 2696 2648 2639 2714 2592 2616 2644 2627 2534 2552 2787 2568 2637 2573 2451 2509 2613 2669 2408 2498 2499 2428 2473 2611 2615 2583 2510 2527 2488 2642 2686 2537 2496 2448 2565 2604 2568 2613 2598 2756 2450 2645 2810 2583 2618 2580 2401 2439 2415 2617 2312 2135 2622 2451 2434 2422 2398 2476 2455 2394 2349 2564 2212 2303 2237 2268 1982 2008 1983 2033 1993 1872 1884 2014 1977 1934 1969 1940 1881 1884 1829 1823 1849 1778 1647 1762 1699 1711 1704 1696 1717 1630 1739 1789 1676 1650 1759 1777 1632 1896 1738 1792 1643 1655 1629 1523 1649 1576 1594 1493 1474 1388 1439 1450 1449 1445 1408 1499 1517 1440 1444 1468 1451 1511 1479 1472 1485 1448 1440 1403 1383 1457 1483 1557 1591 1574 1572 1534 1549 1371 1586 1467 1514 1594 1642 1575 1674 1561 1582 1692 1612 1620 1608 1658 1510 1574 1516 1613 1678 1491 1524 1612 1499 1387 1308 1204 1245 1181 1182 1195 1213 1217 1193 1240 1210 1237 1329 1244 1239 1304 1267 1304 1312 1297 1445 1490 1447 1496 1501 1511 1509 1335 1274 1332 1332 1279 1034 1179 1176 1177 1045 1034 1096 1025 1040 1065 1029 1070 1066 1005 1066 1096 1053 1018 1128 996 1009 1070 984 1088 938 992 967 1001 972 972 924 884 843 884 864 957 891 882 887 892 925 879 876 906 870 792 846 743 836 812 739 754 837 761 760 745 741 749 696 735 760 705 741 730 710 709 709 704 698 720 795 750 779 765 767 713 768 777 672 704 704 656 664 701 624 635 657 651 622 597 654 623 598 624 587 652 632 640 635 589 632 569 595 586 566 591 637 629 653 630 665 684 627 553 547 571 598 576 608 592 563 580 582 578 602 557 551 537 520 540 579 618 596 586 630 586 612 577 709 610 671 703 694 594 653 650 577 634 588 572 690 624 663 634 581 620 632 646 677 660 515 517 503 458 551 546 551 570 629 652 553 569 579 528 523 563 577 477 469 511 567 529 478 517 490 467 480 462 485 487 484 448 484 450 478 473 451 456 483 456 474 520 514 521 459 469 427 450 426 419 436 438 475 455 454 477 441 465 425 401 403 420 392 409 433 411 451 436 427 463 442 422 412 390 382 418 379 403 398 395 431 402 418 413 419 423 422 415 410 354 360 356 385 362 338 378 370 359 344 331 332 310 402 411 409 356 366 447 415 450 405 415 429 427 452 526 503 408 470 473 510 452 434 392 431 428 461 433 504 415 460 452 450 450 422 427 596 545 555 507 422 407 411 402 413 383 367 391 361 429 406 354 421 289 277 281 291 294 298 284 263 305 285 286 270 270 277 288 286 275 276 284 263 303 288 287 300 266 273 262 308 273 293 295 273 252 263 230 234 249 248 247 245 245 229 245 238 238 236 227 234 225 189 196 231 210 245 228 236 246 237 265 225 249 264 248 262 236 261 220 262 219 220 223 210 235 229 232 193 204 225 205 220 220 208 240 225 194 239 271 294 312 335 335 267 342 322 316 351 336 283 353 328 295 340 294 292 307 315 301 297 299 285 265 243 298 278 225 263 270 236 267 278 194 194 210 198 204 198 173 172 190 162 186 147 184 180 186 170 184 190 197 153 205 186 169 172 161 168 167 140 158 183 177 178 170 144 155 154 163 176 173 149 142 141 174 151 153 148 151 145 148 150 154 144 159 156 149 149 150 157 113 148 177 143 133 149 141 140 146 157 162 166 152 161 159 139 150 124 121 133 163 150 154 136 185 173 203 186 183 243 218 189 193 220 207 253 197 175 177 168 190 191 170 129 122 122 152 136 155 123 143 134 143 120 132 148 132 128 165 153 158 140 164 172 154 136 134 136 146 126 131 123 122 130 135 125 151 145 123 128 132 118 141 138 124 124 135 110 130 142 136 130 114 112 112 124 122 128 132 109 125 104 111 124 118 96 109 142 94 121 117 108 109 114 114 101 135 113 99 120 118 124 120 98 130 105 109 128 128 119 112 153 126 120 105 107 111 148 130 129 139 121 104 113 127 117 121 114 129 121 108 121 114 100 103 109 116 116 112 96 120 118 93 94 103 126 90 93 124 122 109 92 102 109 115 88 93 105 94 92 105 100 106 119 102 101 106 103 97 84 119 122 88 119 133 105 139 119 124 100 142 90 110 88 99 101 114 96 97 97 98 94 122 113 114 108 130 104 137 117 128 137 104 131 127 126 132 109 121 138 117 130 113 127 107 94 90 112 112 116 94 93 97 78 110 114 117 116 116 95 125 97 121 104 135 101 105 122 93 110 129 129 143 121 91 122 89 107 100 104 111 132 129 124 119 135 130 107 117 144 125 131 146 144 149 136 124 138 134 138 143 162 149 147 149 427 356 446 525 576 447 420 407 555 269 66 77 79 81 185 199 187 180 167 187 171 184 248 180 154 83 96 99 91 84 94 92 122 104 105 96 88 92 111 103 94 81 123 103 105 100 92 79 95 84 90 104 94 88 103 103 73 88 103 105 74 76 94 87 79 78 76 85 94 76 76 80 86 115 114 104 78 83 83 94 77 76 70 86 58 75 72 58 62 67 57 73 67 86 59 105 79 85 89 101 81 76 77 69 71 70 78 85 63 68 73 69 62 62 72 68 76 86 60 70 79 59 72 80 62 81 70 72 68 66 71 67 86 79 72 68 77 55 74 86 63 76 61 71 69 78 71 73 77 64 68 65 58 65 66 56 81 69 80 67 56 58 69 62 82 73 64 81 86 85 81 73 70 75 68 82 61 69 74 77 79 70 59 86 67 69 105 89 57 61 69 71 69 61 61 78 80 70 68 71 63 65 72 80 72 55 67 64 76 58 65 80 57 59 56 83 67 69 62 66 56 69 80 80 83 78 80 70 68 56 61 76 72 62 71 53 70 57 72 46 60 59 62 56 61 52 58 67 61 58 61 70 53 74 72 48 57 56 48 71 55 53 67 57 40 52 37 47 48 56 56 54 60 54 67 60 46 50 33 51 48 45 65 52 67 42 60 64 68 75 56 71 65 70 56 60 59 81 59 59 64 61 52 72 57 52 36 52 42 65 62 55 55 67 58 54 69 53 60 46 64 67 63 61 
];
B = [
0 0 0
 619605 97103 522502
 336209 53077 283132
 1083156 190370 892786
 334783 55650 279133
 358821 59207 299614
 488232 80004 408228
 553870 102046 451824
 427793 70661 357132
 1073547 200495 873052
 414157 81950 332207
 466719 92487 374232
 594703 136954 457749
 706995 141077 565918
 349306 76395 272911
 1029931 210277 819654
 357515 66252 291263
 382378 78528 303850
 399728 85071 314657
 802243 156374 645869
 428514 83842 344672
 1222310 257815 964495
 746151 140787 605364
 663153 127328 535825
 1384875 242379 1142496
 1942309 372791 1569518
 318376 69629 248747
 5635222 1149966 4485256
 182552 56297 126255
 380106 105156 274950
 240283 73608 166675
 372363 108955 263408
 168616 50584 118032
 1175990 320654 855336
 139477 46602 92875
 291925 87407 204518
 193143 60161 132982
 326726 99827 226899
 89612 30028 59584
 1397122 395141 1001981
 40877 16884 23993
 76824 29194 47630
 85355 31479 53876
 293320 85474 207846
 150586 53610 96976
 68883 26120 42763
 94517 32173 62344
 170366 57556 112810
 2360151 703026 1657125
 78381 35104 43277
 84933 32632 52301
 76399 31013 45386
 117024 44977 72047
 190236 62991 127245
 2586089 804561 1781528
 121430 45695 75735
 87942 33670 54272
 115093 46651 68442
 1231606 394369 837237
 1056491 358517 697974
 128034785 48383404 79651381
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
49 119 5 3
16 24 3 1
19 26 0 0
26 37 0 1
28 52 1 1
39 61 57 6
744 89 173 27
4375 120 313 109
24745 162 491 260
87436 254 853 537
938399 361 1163 913
1360233 677 1750 1375
1667975 1196 2454 2189
1927232 2361 3551 3245
1877313 4066 4874 4518
1610825 6978 6491 6485
1092541 10516 8278 8325
582577 14790 10195 10535
240456 19070 12576 12692
76854 23400 14641 14604
30244 26714 16633 17155
25553 29014 19788 19601
27215 30313 22563 22303
28970 30653 25491 25233
31121 31114 28533 28174
33818 32442 31505 31141
36937 34819 34732 34691
39526 38274 38098 37878
44255 42266 42539 42260
47544 46853 46400 47115
52288 51253 51415 51837
57699 56256 56942 57152
63926 63286 62700 62496
70865 69664 69255 69382
78727 77990 77522 77993
86759 86919 86745 86333
97725 97252 96334 96749
108794 108477 107901 108494
121297 120329 120717 121084
135288 134823 134426 134606
150621 151148 150158 150178
168581 168555 168393 169155
188537 188479 188930 187530
210308 209556 210374 210866
234742 234995 235858 235227
262196 262405 261925 261867
291569 293828 293249 293046
324164 324721 325765 324787
358962 358941 359471 359214
393175 394544 394574 394086
428403 428140 429727 427196
458468 459600 458446 458982
484629 486376 484941 484969
508006 507488 507219 506551
522805 523316 524026 523980
535006 533975 534824 534319
546141 543798 544877 544013
548690 549205 548635 547709
550459 549767 550994 550400
549882 549104 549082 550344
544403 545893 543682 544225
528966 527307 528854 527386
489180 489217 488087 489712
410295 411673 411750 410845
293184 291919 292394 291791
151102 150944 151760 150884
46249 47058 46314 46391
5615 5534 5618 5517
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
