A = [
2604322 2767572 62837096 9124548 2548659 2704249 8438006 2902020 2597309 2539341 2634160 2558765 2510158 2382409 2375282 2289707 2193093 2209018 2144821 2024521 2031519 1986804 1927255 1958404 1958592 2164695 2220228 2250932 2416745 2192712 2149571 2067508 1864382 1820724 1777839 1815213 1746525 1697558 1723118 1667634 1644679 1667601 1612072 1594952 1616631 1574683 1555608 1573493 1526303 1511945 1535207 1491235 1469178 1495861 1464558 1436235 1454443 1419610 1408997 1419000 1384973 1375391 1390718 1352033 1346070 1360308 1322635 1316317 1325196 1296294 1293492 1300292 1274475 1267551 1283300 1249311 1242630 1258660 1229211 1214926 1230206 1203839 1192272 1201876 1174125 1168309 1177079 1153582 1149058 1159843 1126376 1121133 1133920 1107614 1099246 1102649 1088421 1079039 1087505 1068153 1059527 1068770 1041861 1044369 1055815 1027370 1023759 1025985 1014581 1005364 1016282 1000283 991608 1006639 988547 992865 1026172 1008643 1009954 1035298 1019597 1021387 1022383 999761 1000292 1003590 983963 978171 987191 966645 967181 966085 944751 945606 955919 933131 930591 939782 918299 909082 918046 901040 894080 895673 883771 882508 882773 869375 863421 868323 851015 850838 850592 833384 832188 838078 821931 818761 820316 804843 804670 807211 792235 790516 789230 779696 772856 778596 764998 761855 763007 752249 752637 751874 739713 732498 739843 725046 719478 718556 707572 709931 705305 695283 694267 694662 682783 680974 682195 672816 670584 667609 659739 655118 660086 649962 644183 644417 636954 634228 636194 623370 623568 623196 611579 608203 608723 598899 600577 599865 594032 587954 587919 578778 574820 574888 566772 565145 567194 557664 553156 553012 548553 547109 547376 537110 537104 535863 526167 525532 524204 516168 512991 516084 507094 503776 503813 498001 491497 492383 490476 486661 484010 476717 473957 477041 468252 467202 464637 459512 458480 453344 451750 450083 444246 443526 437173 437363 432303 431415 429568 424803 421807 419237 415100 413543 411410 407606 406272 404811 399928 396495 392931 395148 388462 384608 381687 380714 379943 375771 372968 369621 367635 362923 363689 357884 355143 355305 349382 349352 349082 345498 339338 340356 332920 333911 332019 328136 326725 324693 322033 321246 315680 314324 311167 311260 306319 305822 303772 300673 299029 297099 293435 291253 292410 287555 286131 283948 280504 279269 278411 272985 272457 266987 267124 264659 261728 260640 258042 255176 253930 252903 250976 247037 247148 244017 240893 239145 239280 235954 234209 233389 229668 226879 225580 223405 221839 222013 216688 217985 215200 212143 209812 209315 205660 205147 203593 201333 199763 198081 196252 195476 192786 191304 189625 188775 184602 182116 182534 180210 178763 176997 174771 174516 173134 172318 170249 168667 165954 165736 163482 159682 160979 161358 157257 155576 155455 153488 151821 149453 148877 148493 146492 144569 142923 144006 140734 140116 138251 136834 135693 134667 133510 130759 128883 128197 128350 126237 123676 123202 121953 121126 120342 119272 116971 115992 115182 113418 112755 111090 109986 110630 107859 105863 106524 105550 103520 102873 101217 100607 100313 98344 98413 97490 95372 94430 93311 92462 90622 89724 89084 88499 87214 86454 85449 84321 83104 82234 82860 81212 80000 79290 77630 78209 76509 75411 74267 73504 72683 71840 71369 70120 69166 68909 67739 67774 66485 65148 64783 63709 63134 61571 61529 60733 60652 59190 58506 57578 57198 56554 56150 55510 54289 53839 52558 52449 51855 51106 50411 50134 49787 48505 48048 47166 46968 46367 45785 44935 44288 44538 43620 42497 42428 41282 41309 41044 39412 40176 39119 38595 38010 37748 37275 36454 36394 35545 35205 34474 33977 34228 33459 33497 32306 32307 31824 30902 30502 29967 30256 29541 28720 28893 28191 28063 27392 27234 27168 26359 26404 25864 25881 25505 24945 25144 24755 24142 23002 23215 22787 22599 22054 22002 21677 21835 20915 20742 20877 20594 19814 19852 19338 19002 18942 18370 18360 18362 18268 17841 17559 17402 17049 17069 16434 16376 15952 15972 15641 15409 15638 15242 14718 14521 14466 14205 14216 13677 13567 13716 13439 13360 13301 12779 12510 12555 12446 12011 12091 12035 11642 11674 11369 11223 11230 10981 10946 10993 10354 10352 10472 10119 9928 9972 9793 9739 9421 9575 9219 8967 8957 9068 8724 8474 8580 8311 8231 8295 8226 8115 7933 7632 7598 7546 7340 7421 7524 7100 6995 6984 6960 6702 6704 6573 6526 6633 6611 6469 6255 6295 6244 6168 5885 5744 5810 5770 5772 5537 5731 5562 5380 5199 5334 5008 5105 5101 5035 5021 4799 4737 4752 4715 4589 4504 4641 4576 4462 4551 4502 4325 4233 4281 4197 4009 4038 4053 3992 3907 3796 3780 3725 3662 3691 3674 3573 3502 3600 3555 3465 3344 3455 3331 3330 3320 3153 3341 3346 3167 3082 3159 3163 2987 2986 2958 2945 2911 2805 2818 2725 2879 2891 2739 2779 2611 2713 2660 2638 2369 2513 2524 2453 2624 2609 2557 2412 2480 2528 2456 2257 2403 2495 2230 2206 2261 2279 2298 2231 2191 2173 2222 2157 2160 2087 2161 1983 2058 1932 2074 1989 2051 2039 2007 2046 1870 1831 1919 1907 1837 1916 1924 1862 1817 1895 1808 1832 1834 1737 1774 1674 1821 1645 1640 1648 1771 1651 1637 1608 1640 1635 1668 1535 1643 1717 1547 1526 1572 1514 1516 1568 1569 1501 1489 1502 1450 1519 1494 1459 1438 1574 1308 1457 1400 1395 1395 1425 1458 1525 1334 1362 1362 1586 1496 1389 1381 1406 1365 1270 1347 1272 1305 1361 1366 1410 1271 1244 1350 1300 1286 1241 1392 1297 1242 1332 1241 1223 1225 1178 1184 1296 1302 1275 1291 1253 1145 1148 1283 1088 1228 1165 1180 1123 1262 1136 1181 1129 1111 1132 1147 1153 1145 1104 1186 1128 1160 1068 1132 1150 1134 1089 1028 1110 1061 1219 1063 1090 1039 1090 1202 1066 1097 1011 1069 1049 1150 956 983 1009 961 1081 1104 1085 1020 963 969 964 935 961 1079 926 1034 967 1038 1068 859 901 854 957 969 882 951 924 937 871 922 1010 892 930 914 970 801 898 815 895 909 1038 844 808 825 909 867 831 806 892 788 890 861 802 796 874 797 769 791 812 765 784 796 819 807 768 736 793 744 826 766 775 775 742 668 889 776 713 730 793 720 737 686 742 704 677 728 712 762 767 763 720 701 731 788 743 760 717 679 681 686 617 673 696 616 728 690 678 652 633 641 701 648 668 840 639 727 701 590 661 640 662 639 662 622 654 670 702 641 690 642 606 588 599 645 572 600 640 696 609 570 624 624 622 649 589 825 593 602 578 619 562 597 523 592 578 669 592 568 561 643 572 533 561 547 497 562 581 584 518 548 551 577 556 514 579 584 534 535 556 541 553 532 523 572 590 622 477 529 571 517 493 511 515 532 645 582 502 498 501 555 494 563 557 500 462 446 474 475 512 516 464 516 669 604 483 495 495 501 513 511 476 468 546 523 469 483 474 469 430 462 467 509 478 471 435 523 492 444 499 506 502 453 439 459 443 412 423 416 418 436 440 395 493 466 412 440 412 436 464 517 417 382 415 413 447 431 403 385 399 411 445 506 412 402 419 455 415 354 398 388 401 409 352 652 409 462 410 395 410 406 438 391 375 383 371 380 444 405 412 396 419 354 347 384 385 374 393 358 396 334 338 348 388 347 389 355 343 414 397 338 312 337 376 353 396 357 357 340 335 354 361 309 341 357 328 338 412 336 353 396 335 344 350 345 327 389 318 326 355 318 312 307 287 299 306 314 349 299 331 291 319 382 315 310 326 297 300 298 317 338 325 342 254 354 327 282 261 294 267 290 268 303 256 355 296 307 268 293 267 301 307 298 308 288 260 316 278 281 285 274 302 313 266 259 279 259 269 274 333 271 246 254 248 295 309 275 274 247 256 263 239 253 246 331 313 246 255 230 245 206 233 248 193 199 230 261 284 230 228 229 263 220 188 249 230 235 219 213 231 226 308 240 212 231 214 245 197 193 205 186 223 220 200 191 225 211 235 215 208 197 224 189 210 205 208 228 199 223 227 214 190 476 197 224 197 200 178 187 186 203 194 218 218 211 215 203 158 206 220 181 198 186 196 207 197 191 236 210 213 205 202 226 189 197 153 215 200 203 189 221 206 173 215 227 168 199 198 193 190 194 191 205 207 200 174 214 188 199 182 166 171 177 189 182 241 176 181 194 195 169 153 183 143 184 200 166 175 150 187 199 260 169 153 191 154 184 176 159 141 165 191 229 186 199 152 177 154 169 194 154 183 164 150 162 209 152 132 158 135 145 157 157 164 156 152 176 172 165 176 148 155 170 156 165 177 157 110 177 164 153 176 125 161 131 140 131 144 141 143 137 173 170 141 138 174 170 167 146 154 119 129 131 162 152 147 126 170 143 143 136 350 148 151 150 154 121 159 156 145 146 175 144 148 172 172 137 156 160 134 160 125 200 174 152 133 141 153 132 129 144 146 171 134 120 129 128 123 125 144 169 159 144 144 142 100 129 139 125 116 137 110 99 109 123 122 185 116 136 139 134 108 114 96 103 131 95 136 125 103 158 113 84 103 153 100 130 101 90 139 131 97 101 102 110 133 91 136 130 114 110 114 110 130 118 115 200 119 96 110 89 135 113 80 100 107 194 124 111 108 111 174 111 116 115 106 88 85 125 109 87 118 118 105 115 111 103 85 111 100 118 84 110 96 107 94 80 92 115 111 93 116 98 95 96 89 106 114 99 107 82 79 105 90 80 83 84 105 113 99 111 102 62 97 94 117 82 76 80 82 69 75 79 82 64 83 83 56 78 85 120 71 83 86 76 64 74 51 72 100 119 78 81 62 75 84 94 84 82 68 78 72 78 96 78 104 105 74 79 82 64 93 74 73 62 74 67 94 77 64 72 82 72 101 79 83 80 98 77 67 77 65 65 70 73 78 69 64 243 77 87 80 109 64 78 78 82 76 51 71 69 74 65 69 72 71 65 63 53 60 77 112 57 72 56 55 79 69 60 65 65 64 55 105 63 58 74 57 63 55 70 70 70 52 95 76 82 50 63 63 343 64 76 85 75 54 70 73 60 55 62 59 70 57 65 63 46 64 69 58 50 42 51 58 63 56 57 49 61 48 57 72 55 47 44 51 39 49 68 56 67 56 46 49 55 44 62 49 56 51 54 70 59 45 47 39 47 51 48 45 66 70 54 56 61 41 57 60 45 43 53 63 57 50 64 52 53 73 46 42 56 64 65 55 60 40 50 40 47 48 40 78 54 38 35 50 49 47 50 45 28 49 42 40 42 51 51 36 40 43 40 46 42 52 39 45 50 46 30 51 40 34 51 52 42 48 46 52 28 49 35 47 40 46 38 39 35 58 47 54 44 42 49 35 45 41 40 53 46 46 43 33 56 41 51 43 38 29 43 62 31 35 45 42 38 41 36 27 40 33 38 50 39 45 37 46 40 42 38 
];
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
 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 = [
7157 9173 12 10
1268 1705 3 3
1159 2475 6 11
1327 3173 4 7
1063 3002 8 11
1223 3937 22 14
9264 5186 68 41
25442 6021 109 96
61461 7602 178 123
138919 10078 367 263
215228 12056 692 526
353497 16014 1694 1454
562139 20359 13779 7837
960308 27950 43478 25564
1619918 36697 61229 41630
2864323 51014 86944 66166
4751211 73479 124245 104211
6951255 112142 176813 159359
8874081 175037 255309 241955
8792040 262924 357104 347095
5021338 362334 471949 462900
1615880 467579 585946 575524
862322 579026 705891 692733
929196 703706 830589 818164
1071505 834804 964611 947680
1220573 974421 1102710 1085391
1359223 1109562 1238712 1222671
1492200 1240569 1368627 1348280
1598565 1353143 1476708 1459829
1678710 1446838 1566697 1550133
1731643 1522492 1631190 1612591
1769594 1578853 1673872 1657344
1779704 1603055 1687636 1673689
1766431 1630340 1699842 1684103
1739165 1626380 1690370 1678335
1703917 1612108 1660399 1653966
1657968 1584130 1620335 1615437
1606731 1547567 1579246 1571966
1540611 1498663 1523091 1519419
1472479 1443063 1462203 1454684
1406965 1381260 1397351 1388496
1334467 1317214 1327711 1322381
1259123 1246606 1254451 1249975
1176926 1167726 1175769 1173159
1101467 1094011 1100396 1097613
1033073 1026288 1029054 1027492
942535 937177 940606 938290
857634 851839 855554 854441
775611 774401 775054 772624
704263 703100 706232 703531
660923 659210 660283 656224
584677 583770 586191 584320
547221 544491 545324 544971
526243 524216 527511 525640
495570 493529 494203 492757
461786 463420 465549 463395
444599 444386 444258 444330
416470 414625 414965 415427
410485 409402 409828 409895
399474 397337 398856 397484
393533 393278 393630 392998
383239 382338 383970 382885
387683 386450 387559 388272
376629 375237 375340 374364
351982 352294 354057 350768
302198 301321 302464 302164
242990 242783 242339 242503
197785 197364 197622 197296
163742 162808 163287 163104
104313 104488 103990 103994
45728 45721 46085 45792
8908 8842 9109 8982
2 1 1 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
