A = [
2676369 2843021 64761775 9365588 2619234 2779451 8660750 2980660 2667134 2608698 2706124 2626952 2576942 2448644 2440395 2352468 2254754 2272570 2204552 2081325 2089756 2041430 1979496 2012174 2013470 2222910 2279154 2312249 2482557 2251245 2205358 2123689 1913639 1868613 1825103 1864437 1794562 1742765 1770380 1714387 1689575 1712605 1656244 1639602 1660393 1620389 1599553 1616374 1569523 1556144 1577827 1532722 1509275 1536898 1504988 1475746 1494694 1459210 1447567 1458466 1423629 1413610 1429001 1389735 1383509 1398755 1359775 1353172 1363291 1333168 1330205 1336966 1309926 1303226 1318289 1282889 1277050 1291813 1262544 1247207 1262540 1236216 1223851 1233305 1205373 1199237 1207853 1183688 1180385 1190043 1156574 1151443 1164362 1137293 1128476 1131748 1116969 1107802 1116381 1095909 1087618 1097026 1069758 1071795 1084309 1055232 1050976 1053453 1042032 1032650 1044055 1029004 1018783 1033290 1015560 1021499 1055967 1039690 1041337 1067594 1052084 1053912 1054665 1032248 1031960 1036427 1016043 1009205 1019127 997842 999352 997703 975613 976167 986469 962850 960593 970847 948736 939505 948220 930409 922394 924537 912325 910663 911372 896910 891509 896883 879350 878371 877903 861089 859232 864876 848928 846090 848988 831140 829980 831984 816697 816105 813752 803350 796889 802455 788353 785267 786346 775691 776221 774747 762691 755278 762793 747817 741315 740671 729686 732189 726503 716408 715958 716351 703357 702261 702292 693485 690721 687909 678901 674242 679535 668606 662860 663529 655322 652315 654571 641300 641556 641036 628652 625793 626435 616313 617818 617086 611669 604783 605343 595428 591404 591072 583669 581302 583554 573711 568934 569423 565049 562649 563174 552606 551846 551896 541092 540792 539148 530715 527636 530792 521581 517785 518089 511785 505006 506671 504117 500718 497560 490325 487643 490709 481678 479980 477523 471991 470896 466938 463907 462660 456450 455589 448997 449172 443896 443255 440969 436552 433452 431063 426791 424838 422500 418979 417513 416578 410434 407256 403679 405555 398963 395295 392387 390866 390354 386085 383082 379690 378226 372840 373808 367906 364817 365510 359414 358855 358437 354828 348292 349537 341911 343026 340763 336926 335740 333349 330471 329975 324071 322804 319760 319676 314365 313876 311721 308652 307028 305635 301520 298753 300217 295190 293779 291594 288328 286616 285523 280462 280132 274092 274363 271539 268919 267378 264967 261691 260693 259282 257446 253305 254513 250272 247452 245292 245347 241893 240141 239260 235382 232475 231282 228834 227280 227607 222061 223449 220770 217601 215107 214523 210786 210207 208575 206264 204866 203222 201283 200568 197709 196040 194323 193492 189221 186509 187081 184779 183281 181477 179138 179238 177392 176718 174434 172924 170270 169927 167678 163840 164954 165329 161139 159793 159415 157354 155641 153276 152526 152141 150132 148046 146526 147792 144350 143503 141792 140272 139201 138224 136827 134063 132250 131394 131584 129510 126944 126435 125141 124253 123376 122247 120029 119015 118126 116270 115573 113887 112829 113419 110921 108561 109088 108124 106014 105432 103703 103133 102815 100722 100956 99944 97782 96734 95803 94713 92878 91926 91489 90655 89484 88567 87584 86312 85182 84251 84926 83175 81997 81291 79512 80185 78356 77283 76139 75348 74518 73621 73169 71871 70876 70763 69448 69493 68137 66879 66499 65332 64700 63147 63116 62393 62121 60810 60007 59170 58685 58129 57699 57012 55802 55389 53995 53889 53234 52486 51819 51507 51116 49913 49567 48601 48215 47682 47053 46093 45472 45769 44849 43718 43634 42551 42449 42244 40632 41337 40184 39719 39130 38894 38333 37517 37420 36642 36195 35425 34967 35156 34523 34445 33226 33266 32691 31910 31358 30858 31121 30367 29568 29776 28980 28890 28195 28022 27974 27156 27125 26569 26582 26277 25647 25872 25454 24884 23679 23844 23494 23239 22740 22675 22313 22505 21526 21324 21483 21147 20415 20396 19891 19597 19502 18947 18888 18897 18796 18385 18061 17882 17565 17640 16921 16900 16455 16474 16119 15914 16131 15667 15181 14973 14978 14623 14655 14114 13999 14173 13903 13786 13729 13216 12942 12952 12899 12431 12510 12520 12141 12082 11799 11612 11630 11316 11339 11372 10683 10777 10862 10518 10281 10306 10146 10111 9731 9955 9588 9338 9335 9384 9067 8790 8939 8652 8572 8633 8529 8446 8330 7953 7922 8090 7651 7718 7832 7419 7283 7295 7297 6984 6984 6879 6808 6905 6897 6782 6504 6588 6558 6472 6182 5994 6112 6051 6066 5825 6000 5838 5735 5451 5584 5255 5334 5355 5303 5273 5009 4979 4998 4934 4820 4724 4865 4768 4698 4769 4692 4539 4458 4504 4420 4208 4233 4240 4204 4085 4004 3964 3918 3867 3878 3838 3765 3696 3759 3712 3616 3508 3634 3490 3521 3467 3322 3514 3526 3344 3253 3366 3325 3163 3138 3136 3099 3073 2974 2947 2906 3031 3029 2894 2949 2745 2858 2801 2801 2524 2648 2708 2610 2766 2783 2693 2566 2625 2663 2603 2405 2567 2648 2378 2367 2400 2450 2484 2398 2342 2331 2395 2540 2334 2266 2310 2128 2247 2078 2192 2121 2176 2174 2129 2179 1978 1935 2041 2059 1950 2058 2022 1961 1923 2031 1925 1958 1940 1848 1901 1781 1954 1749 2267 1738 1867 1766 1788 1692 1750 1736 1787 1644 1752 1825 1638 1644 1673 1632 1630 1653 1678 1604 1607 1615 1577 1632 1613 1565 1537 1687 1404 1550 1491 1478 1480 1541 1565 1636 1463 1476 1457 1679 1598 1493 1479 1521 1481 1397 1450 1362 1423 1470 1472 1524 1384 1357 1478 1421 1401 1370 1503 1400 1344 1442 1365 1313 1331 1254 1291 1387 1397 1370 1394 1329 1262 1245 1406 1186 1328 1258 1275 1193 1346 1214 1277 1208 1201 1214 1222 1224 1226 1180 1293 1225 1232 1129 1218 1226 1283 1184 1133 1298 1115 1261 1118 1159 1101 1156 1249 1129 1156 1073 1122 1116 1216 1002 1034 1074 1015 1143 1154 1147 1074 1010 1014 1015 980 1005 1138 986 1079 1023 1102 1118 905 973 937 1027 1033 935 1016 986 1015 927 997 1059 948 993 979 1039 864 967 863 951 960 1090 897 872 889 953 929 887 850 957 855 939 930 856 845 934 848 834 840 881 813 823 854 874 865 833 789 853 793 890 827 817 827 790 722 960 836 763 796 848 781 799 738 795 785 727 790 770 817 825 831 773 746 782 841 799 798 760 737 736 727 654 732 742 678 783 741 738 708 693 702 855 707 712 915 681 774 748 651 705 676 726 686 729 681 708 724 776 698 749 708 674 634 645 701 645 657 691 755 667 635 696 687 673 704 639 879 651 650 634 674 623 660 575 654 634 722 649 631 614 695 623 596 596 602 547 606 625 629 585 594 581 613 601 565 620 637 571 586 615 581 587 572 568 611 639 669 519 571 611 570 526 550 558 581 686 631 547 543 564 605 539 603 590 568 516 491 522 531 564 563 504 552 695 647 529 534 539 530 550 548 499 507 571 560 495 502 505 488 452 484 495 541 510 494 460 547 524 476 518 527 532 478 477 485 461 445 448 434 431 470 462 418 515 496 431 463 437 452 492 545 439 412 456 439 474 456 418 410 423 427 457 529 436 418 437 475 431 365 414 406 427 430 376 667 430 484 440 414 431 429 459 410 400 396 393 394 461 424 433 412 437 381 361 402 414 402 415 383 421 355 363 374 408 369 416 385 355 436 424 369 321 356 395 363 423 372 378 358 364 382 381 336 369 386 350 369 438 364 377 429 364 366 371 374 349 411 349 356 387 361 340 349 312 322 336 340 388 336 364 320 346 409 344 336 353 326 316 324 335 364 357 369 282 381 354 308 293 323 293 327 285 325 282 377 311 321 287 310 291 322 332 309 324 302 288 334 300 298 306 296 323 327 284 274 292 282 290 292 350 289 262 272 259 312 327 289 295 262 276 284 263 276 263 365 335 285 282 267 281 242 272 294 227 234 261 291 331 284 268 255 290 263 232 282 266 274 243 235 261 264 339 278 249 264 243 266 229 221 233 214 247 260 231 225 245 238 271 254 247 230 256 224 245 237 244 265 223 255 253 250 221 506 227 254 223 241 213 218 215 227 215 248 248 249 247 231 195 232 243 209 237 210 222 230 217 214 264 232 241 232 228 254 222 219 184 238 238 243 210 251 230 198 230 243 187 209 229 207 201 209 205 222 227 213 192 232 211 210 195 178 178 187 202 197 247 180 194 211 207 179 173 200 149 198 210 177 191 168 199 209 270 178 162 202 163 194 182 166 149 173 198 239 193 205 162 190 158 179 205 165 191 171 154 175 217 164 144 161 146 155 164 164 178 164 157 183 179 172 189 157 160 178 160 175 188 172 120 186 169 166 190 137 175 140 143 143 156 153 149 147 186 178 150 144 187 173 176 156 162 125 136 139 167 160 156 133 186 156 154 152 377 173 159 163 163 137 171 162 152 154 184 150 156 182 179 145 167 175 144 181 136 214 190 172 146 153 167 142 139 158 157 186 153 137 144 137 136 139 155 187 169 158 165 161 120 136 154 140 134 150 123 115 129 142 137 195 127 153 147 153 125 125 110 114 143 117 156 133 117 175 124 99 115 165 112 145 108 106 148 151 103 116 112 121 149 103 143 148 123 124 122 127 139 126 127 212 133 107 117 96 145 125 89 117 117 206 146 123 124 123 189 125 136 126 126 99 101 134 121 101 127 127 115 121 123 112 96 124 108 134 91 118 100 118 101 84 99 127 120 100 120 106 104 106 98 111 118 103 117 88 83 109 92 82 93 93 109 119 105 114 108 67 105 100 123 86 83 94 92 75 84 87 88 72 91 87 57 82 93 128 78 92 99 82 76 85 73 77 106 130 84 86 72 88 94 104 94 85 79 90 83 89 105 86 110 114 85 85 91 73 104 90 86 74 86 72 102 84 70 89 87 84 109 91 91 88 103 83 72 88 77 79 74 81 85 77 69 249 85 95 86 115 67 81 83 84 84 56 72 79 77 73 71 74 73 77 70 63 65 81 116 63 78 66 66 83 81 64 75 73 70 65 110 80 74 81 76 72 73 81 93 79 62 105 84 105 63 84 67 355 67 110 98 94 83 107 79 65 64 76 76 84 72 81 67 49 67 72 63 51 45 53 63 64 60 63 56 65 54 64 77 62 52 48 56 45 54 72 61 78 59 55 54 63 49 68 62 63 56 62 82 63 49 47 44 57 62 54 53 70 72 54 57 63 42 58 64 49 44 55 64 59 51 67 55 55 73 47 44 59 68 67 55 60 41 51 42 48 50 44 83 55 39 36 50 53 47 50 49 29 49 43 41 45 53 54 36 41 44 42 48 44 54 42 47 51 46 32 54 43 39 53 53 45 49 47 54 31 53 37 51 41 48 43 41 37 61 48 57 46 44 55 37 48 43 43 59 49 49 43 34 58 44 57 49 42 34 50 67 36 38 49 44 40 45 38 34 45 40 41 52 45 45 41 50 43 47 41 
];
B = [
0 0 0
 332935 190176 142759
 244293 133537 110756
 390691 208584 182107
 278790 174327 104463
 339943 214182 125761
 467400 307022 160378
 267291 187531 79760
 821321 579902 241419
 191556 140642 50914
 174198 125494 48704
 119881 89798 30083
 139045 97620 41425
 73813 54846 18967
 61473 45552 15921
 66771 46271 20500
 70901 48957 21944
 162660 107116 55544
 91022 68397 22625
 151801 109929 41872
 167008 125708 41300
 256536 191477 65059
 656228 469471 186757
 176368 140833 35535
 179351 137453 41898
 176089 138581 37508
 199363 140558 58805
 203461 157333 46128
 188105 152178 35927
 133804 107874 25930
 181592 149429 32163
 145084 121003 24081
 446853 346274 100579
 201896 171055 30841
 143351 122760 20591
 187669 157886 29783
 129653 111016 18637
 195525 160063 35462
 148382 128976 19406
 195931 166888 29043
 149645 129827 19818
 178516 152465 26051
 185093 160805 24288
 314310 255436 58874
 176218 154756 21462
 201454 176655 24799
 153451 135691 17760
 195386 172809 22577
 208534 182118 26416
 184232 165392 18840
 219829 192895 26934
 155108 138628 16480
 229067 199649 29418
 187458 165849 21609
 377483 324152 53331
 197452 178248 19204
 212613 189018 23595
 195702 176463 19239
 239419 204118 35301
 324979 298752 26227
 228449619 218692865 9756754
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
7299 9303 15 10
1288 1734 3 3
1184 2517 6 12
1367 3236 4 7
1097 3055 8 11
1274 3990 22 14
9507 5285 69 42
26065 6145 112 97
62938 7742 186 127
142103 10252 381 266
220618 12250 710 547
362859 16276 1742 1488
578226 20653 14004 7964
988753 28394 44101 25928
1663509 37270 61977 42147
2929824 51736 87982 66999
4845831 74556 125795 105541
7082261 113701 178987 161300
9039725 177302 258530 244797
8956108 266329 361374 351143
5119472 366919 477658 468482
1647522 473466 593214 582656
874916 586568 714748 701228
941929 713099 841372 828908
1085852 846064 977090 959879
1236851 988228 1117278 1099853
1377989 1125316 1255743 1238868
1512815 1258557 1387883 1367140
1621149 1372994 1497798 1480038
1702653 1467312 1588796 1571775
1756970 1545305 1654942 1636214
1796825 1602785 1698797 1681885
1808097 1629342 1713755 1699842
1796022 1657605 1727978 1711760
1768698 1654137 1718829 1706577
1733766 1640400 1689462 1682274
1687677 1612593 1650194 1644718
1637393 1577285 1609088 1601867
1571378 1528324 1553580 1549853
1503015 1472286 1492836 1484788
1437058 1410531 1427772 1418854
1365282 1347689 1358497 1353457
1289608 1276916 1284631 1280369
1206836 1197230 1205670 1202870
1131628 1124076 1129870 1126894
1062851 1056505 1059497 1057721
971584 966419 969771 967247
885811 879809 883432 882479
801940 800730 801320 799007
728130 726196 730143 727291
683249 681581 682402 678770
605787 604705 607515 605638
565470 563279 563760 563703
544274 542152 545490 543318
512657 509931 511149 508826
476129 477632 479790 477321
457388 457390 457264 456906
428221 426327 426414 427236
422030 421238 420993 421219
409958 407645 408826 407567
402658 402744 402846 401733
392386 391682 393394 392052
396408 394970 396724 397403
385923 384428 384911 383209
359957 360810 362612 359043
309580 308677 309653 309424
250100 250153 250020 249955
204055 204097 204598 203858
170191 170114 170175 170232
110768 111859 110707 110339
50573 51342 51513 50767
10686 10727 10806 10376
15 9 14 10
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
