A = [
532910 579328 2020512 439864 493657 429294 421646 428893 418303 395153 395288 396612 396593 387204 384796 376327 369994 370109 364697 362199 360264 355507 353890 352888 352202 407316 407560 408009 464709 465838 470339 470233 474230 476860 476628 474428 470273 467400 464980 460589 458338 456584 453140 450383 451034 446471 442772 438896 434270 430658 428022 425025 422506 420398 418124 415863 412227 408314 404243 401329 397163 394525 390982 387775 385408 384113 379936 377463 373758 369912 366474 363830 359720 355777 353772 349572 347993 344283 340947 337184 334558 330662 327168 324502 321183 318667 314770 311331 307886 305585 301571 299310 296719 292428 290607 286530 284982 281658 279313 275503 272601 269708 266320 263087 261609 258678 256153 254007 250153 247461 244458 242118 239200 237004 234676 230430 228604 225981 223375 221012 218178 216788 213067 209991 207378 206236 203623 200993 199174 195866 194090 191343 188592 188246 185170 181718 180392 178849 176149 173599 171364 170008 167241 166698 163753 161842 159894 158368 156198 154880 153541 150621 149145 147331 144868 143319 141435 139256 138163 136175 134991 132699 129979 127777 126765 124678 124094 122241 120280 119168 117575 115906 114361 112794 110789 109951 108524 106540 105594 104388 102631 101385 100135 98613 97855 96722 94844 93671 92627 91295 90600 88994 87988 86406 85095 84884 83248 82268 81317 79878 78902 77401 76496 75087 74573 73346 72802 71778 71148 70555 69051 68471 67332 66438 65309 65010 63733 62992 62110 61502 60474 60007 58925 58028 57656 56453 55582 55333 54302 53428 52760 52444 51205 51143 50120 49106 48623 48167 47042 46788 45900 45355 44809 44691 44640 43375 42966 42270 41402 41010 40822 40383 39975 39558 38853 37993 37702 37497 36540 36082 35779 35101 34789 34487 33849 33050 33284 32561 32094 31665 31473 31188 30645 30274 29800 29578 29217 28575 28748 28143 27876 27522 27121 26961 26788 26402 25672 25581 25314 24823 24756 24296 24181 24096 23494 23261 22964 22834 22540 22256 21908 21828 21560 21443 21340 20736 20508 20378 20080 19869 19595 19346 19111 18843 18694 18235 18475 18196 17614 17503 17233 16740 16505 16519 15998 16014 15885 15625 15458 15243 15109 15056 15002 14459 14409 14319 14261 13964 13677 13679 13867 13574 13415 13280 13120 12931 12730 12774 12337 12331 12316 12904 11890 11985 11737 11364 12501 11372 11347 11104 10997 10958 10839 10923 10544 10639 10300 10153 10062 10033 9953 9592 9555 9590 9338 9395 9229 9116 9168 8946 8744 8733 8639 8479 8835 8501 8167 8188 8072 8157 8219 8097 8277 8117 7841 7710 7474 7341 7283 7393 7402 7400 6869 7001 6895 7016 6669 6718 6819 6608 6465 6431 6578 6354 6424 6303 6204 6118 5929 5908 5955 5906 5772 5708 5653 5631 5605 5484 5582 5506 5394 5335 5388 5345 5313 5244 5478 5116 5120 4874 4887 4855 4731 4593 4684 4609 4608 4719 4381 4527 4476 4477 4519 4304 4298 4227 4171 4241 4092 4093 4116 4013 4047 4111 4017 4079 3961 4008 3846 3802 3952 3892 3857 3822 3682 3613 3592 3551 3552 3512 3394 3464 3428 3293 3387 3337 3377 3337 3271 3370 3295 3235 3154 3205 3258 3135 3213 3119 3059 3105 3076 3020 2972 2960 2857 2955 2974 2906 2899 2846 2772 2802 2775 2750 2728 2627 2636 2636 2640 2614 2570 2585 2584 2538 2502 2466 2521 2412 2548 2515 2506 2478 2428 2470 2372 2323 2365 2417 2409 2382 2422 2437 2330 2396 2350 2480 2411 2632 2398 2297 2462 2262 2237 2271 2245 2141 2204 2195 2151 2228 2105 2146 2161 2288 2192 1966 1919 1957 2033 1945 1961 1925 1997 2050 2014 2119 2095 2009 1907 1939 1943 1860 1901 1936 1834 1787 1766 1786 1774 1762 1827 1705 1753 1794 1785 1712 1749 1718 1724 1702 1513 1618 1555 1623 1651 1549 1561 1555 1526 1609 1546 1577 1578 1483 1496 1424 1556 1449 1441 1521 1325 1389 1482 1452 1355 1434 1403 1470 1353 1326 1409 1410 1387 1294 1351 1319 1374 1382 1285 1338 1414 1270 1300 1250 1260 1172 1228 1178 1203 1197 1141 1221 1248 1178 1148 1116 1156 1152 1128 1126 1103 1134 1128 1092 1169 1160 1184 1144 1098 1097 1096 1074 1085 1060 1102 996 1015 1048 1024 1003 1073 1013 1025 998 990 1050 954 1039 958 972 1041 1034 1016 1001 955 917 968 894 883 935 937 963 924 884 977 949 897 920 921 890 863 891 860 893 888 814 865 827 870 909 905 867 896 918 861 913 886 873 857 893 882 886 954 978 997 1085 1144 1066 1006 912 940 898 887 934 844 812 949 857 967 884 937 921 930 843 765 784 787 850 766 746 808 760 716 711 741 685 678 730 723 709 759 799 755 835 765 757 786 745 733 669 685 746 639 647 721 717 717 794 673 662 635 667 627 642 641 649 667 650 626 656 639 619 596 611 629 641 547 606 655 571 575 581 567 587 572 527 547 545 542 567 579 542 565 531 511 574 555 553 554 538 556 583 543 552 531 559 526 585 555 548 553 579 562 509 527 453 520 536 527 524 461 499 508 515 462 486 474 476 430 457 491 448 441 450 426 405 422 420 449 419 417 426 442 452 431 449 430 440 473 472 472 409 443 483 409 420 425 415 416 417 415 405 371 408 423 428 421 385 442 441 376 345 373 364 324 363 346 406 350 362 348 357 339 343 337 338 311 395 361 380 484 380 374 404 341 298 358 363 321 357 340 339 288 311 302 296 296 309 328 272 314 305 295 306 286 277 304 319 293 269 321 296 321 282 316 314 294 351 279 323 297 294 294 275 284 265 282 264 264 274 245 250 245 254 239 249 258 257 272 237 241 261 255 262 264 218 255 237 245 226 226 226 268 260 247 285 252 227 248 239 286 251 221 221 243 234 230 245 241 224 219 219 224 221 239 230 233 219 240 220 243 202 278 226 231 199 195 188 243 200 173 216 238 206 243 219 177 220 190 203 234 186 219 185 219 186 228 193 192 198 221 219 191 211 211 208 237 202 219 231 243 186 211 232 202 222 217 174 212 216 218 211 237 235 211 198 163 223 203 189 203 190 210 184 165 185 189 186 164 208 161 187 194 189 187 185 176 193 139 160 148 190 182 171 153 138 188 163 156 171 151 159 166 163 155 174 181 177 160 166 163 161 155 150 175 172 167 159 176 155 163 168 191 178 156 168 164 172 179 164 145 140 169 166 146 148 147 160 144 157 171 147 152 171 123 163 162 182 146 149 145 153 146 143 158 137 157 154 145 160 148 144 166 154 184 141 147 162 132 126 142 171 155 140 156 151 137 141 144 137 145 146 148 137 143 128 130 128 141 130 139 123 137 128 142 101 118 137 137 120 125 130 139 122 122 122 134 119 105 95 97 132 125 121 107 108 112 95 123 92 88 111 110 114 112 78 91 96 101 121 103 114 99 98 82 103 97 129 121 92 108 85 108 107 105 85 97 113 82 108 113 117 100 122 108 107 93 94 86 79 100 116 95 91 98 91 99 88 92 82 97 120 104 82 79 87 92 98 99 95 85 110 108 120 101 119 113 112 95 110 92 92 92 101 87 87 84 104 92 91 82 85 89 88 86 78 89 87 92 86 86 95 82 84 69 81 89 66 67 82 67 79 67 66 78 72 77 68 73 90 66 70 60 85 84 52 83 69 56 75 74 65 79 68 88 66 59 69 64 59 57 74 82 67 62 63 74 64 77 65 71 64 72 49 53 60 74 62 71 78 73 64 86 68 68 63 62 61 65 71 68 64 62 71 75 73 67 79 90 74 71 59 73 69 80 67 76 92 83 72 82 82 92 83 88 94 93 79 67 81 75 84 62 69 71 85 61 73 69 79 67 68 68 86 77 64 64 64 57 69 53 69 61 73 56 71 52 77 68 56 69 64 60 53 54 49 68 67 60 51 49 67 47 54 60 59 51 66 63 55 52 51 43 47 52 57 42 56 65 50 55 48 54 46 45 50 49 32 43 47 52 46 47 39 56 58 61 49 56 51 56 48 56 59 50 54 51 47 36 56 46 46 47 47 59 42 46 58 44 48 62 62 44 46 43 45 46 43 57 49 41 44 55 46 47 50 50 43 47 52 38 46 44 42 31 43 47 40 46 35 41 39 41 40 41 46 30 36 38 40 39 46 45 49 36 34 46 35 56 48 32 35 38 35 34 32 35 44 39 47 44 31 31 38 44 29 46 53 37 42 27 50 34 39 50 36 43 40 44 41 41 35 33 44 45 42 39 49 52 49 49 50 48 47 34 57 40 50 47 51 47 35 39 34 41 30 43 26 38 43 36 68 46 58 51 51 43 48 37 45 38 43 49 38 32 43 33 41 21 37 28 42 30 42 45 42 40 47 40 38 37 52 42 39 45 44 38 45 45 27 44 61 46 54 47 37 61 84 189 205 215 170 107 125 143 62 38 28 31 27 26 35 31 40 43 33 48 40 44 41 43 38 39 38 33 43 26 44 33 35 40 29 52 43 68 41 55 59 40 61 37 37 32 32 25 36 33 28 32 32 38 40 35 39 36 34 20 21 29 25 28 28 22 41 25 31 29 24 30 35 26 28 29 33 39 32 46 39 36 29 28 39 28 32 23 28 26 34 36 42 31 32 34 40 26 34 52 32 42 26 27 46 30 35 23 22 31 29 26 20 28 29 30 35 34 27 28 21 27 24 29 26 30 36 46 16 22 34 29 32 29 24 27 28 27 27 26 32 35 18 30 23 32 19 19 38 33 36 29 21 25 28 28 27 35 36 25 29 26 27 34 29 42 29 28 25 35 26 26 39 40 36 20 27 34 39 25 56 34 41 29 28 45 22 30 21 34 21 23 37 32 38 26 24 23 22 27 39 30 16 33 24 34 20 17 26 32 24 23 37 28 28 33 26 28 24 29 28 32 37 28 16 33 20 31 24 28 26 29 23 25 24 25 19 28 22 21 20 24 21 30 29 27 31 25 22 26 14 37 27 33 23 22 24 25 33 21 20 14 27 28 36 28 16 32 20 13 23 36 29 22 31 26 24 17 22 27 31 28 34 22 25 26 24 36 30 31 29 21 36 20 27 20 41 22 25 30 26 26 23 21 21 34 28 31 33 30 26 34 29 34 36 26 25 21 19 30 28 15 18 
];
B = [
0 0 0
 176121 53731 122390
 83956 25060 58896
 298156 105407 192749
 185769 59008 126761
 106471 32735 73736
 292489 106636 185853
 227306 75189 152117
 127394 40975 86419
 392064 140547 251517
 405680 136251 269429
 73165 22661 50504
 1168012 424611 743401
 154159 52500 101659
 48932 15920 33012
 263521 110155 153366
 84407 32770 51637
 26176 8955 17221
 289593 122216 167377
 24094 8164 15930
 24872 9012 15860
 5724 2068 3656
 148 49 99
 5619 2118 3501
 429059 185023 244036
 28619 10056 18563
 37088 14489 22599
 448417 195931 252486
 26262 10485 15777
 55627 22245 33382
 702814 295563 407251
 51883 21011 30872
 92536 38553 53983
 505528 230631 274897
 352699 160637 192062
 589453 274453 315000
 1059856 491882 567974
 866512 371689 494823
 544738 248226 296512
 1241827 586528 655299
 485105 199563 285542
 33184 13722 19462
 1111914 513566 598348
 17911 7510 10401
 31156 12907 18249
 1519420 730893 788527
 32584 13887 18697
 395480 163203 232277
 2089792 1092916 996876
 399415 170181 229234
 11 4 7
 15047835 8243356 6804479
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
79 93 0 1
95 25 0 0
154 22 1 2
237 41 0 1
157 40 0 0
157 46 40 0
376 88 76 9
1874 104 126 26
11978 134 136 54
55410 187 215 92
143697 225 264 139
320515 287 370 216
625311 423 505 347
1166481 509 699 508
1730362 635 887 724
2058390 953 1273 1125
1845643 1306 1697 1610
1344459 1810 2163 2120
831512 2684 2701 2723
429813 3633 3286 3332
178266 4716 3890 3802
46839 5816 4126 4085
11190 6211 4293 4182
8422 5588 4280 4298
7563 5547 4415 4650
7203 6070 4560 4728
7534 5583 4647 4821
6671 5597 4907 4928
6717 6171 5309 5025
6571 5986 5573 5573
6749 6423 5928 5891
7496 7013 6174 6498
8416 7677 6699 6612
9040 8143 7232 7331
9327 8722 7973 7978
9919 9343 8456 8685
10847 10007 9506 9515
11571 11038 10536 10345
12102 11839 11585 11644
13114 12878 12639 12696
14363 14510 13975 14007
15824 15906 15816 15923
17762 17762 17633 17518
20037 20169 20002 19957
22109 22158 22158 22139
24770 25170 25227 25394
28105 28432 28248 28183
31188 31016 31039 31152
34350 34586 34094 34652
38079 37793 37517 37128
41119 40703 40677 40896
43371 43290 42717 43197
46145 45682 45049 45375
47731 48021 47607 47707
50576 49909 50616 49612
51665 52321 52059 51622
54944 55080 54925 54557
58549 57430 57685 57448
60550 59922 60208 60120
63124 62320 63007 62485
65661 65725 65064 64991
66129 65622 65823 65558
64288 62874 64045 63257
56256 56042 55979 56415
42068 42338 43017 42051
24794 25484 25410 24698
12439 13098 12923 12316
8840 8759 8679 8020
7940 7093 7347 6838
6634 6798 7707 6063
4977 5223 4958 5314
3685 3030 3479 3714
325 317 248 270
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
