A = [
380510 415373 1413773 322214 363517 315856 310250 316083 309001 292807 293196 294723 293783 286504 284686 279606 275259 275340 270845 269111 266524 264784 263142 260809 260745 298653 299206 299604 337303 338914 341170 341368 343415 345532 345426 344630 341133 338807 336419 334366 331096 330182 328355 326277 326034 322663 320482 318554 314493 311676 310369 307684 306101 304539 302370 300265 297875 295224 292297 290431 287350 284345 282809 280132 278263 276469 274426 272606 270094 266480 264529 263184 260233 256684 255390 252537 250711 247924 246209 243254 241568 238064 235688 233853 231265 229191 226684 224605 222123 219373 217792 215179 214015 210176 208539 206278 204676 202145 200118 198037 195434 193630 191247 188669 187991 184807 183402 182119 179142 177497 175536 173873 170972 170069 167623 165143 163766 162091 159867 158076 156178 155066 152061 150057 148255 147258 145787 143379 141526 140117 138606 137039 134897 133864 132249 129915 128468 127496 125738 123815 122739 121423 119515 118238 116641 115359 113612 112419 111213 110193 108782 107017 106391 104768 102925 101537 101132 98988 98078 96817 95919 94088 92616 91066 90280 89019 87968 86917 85656 84874 83551 82352 80863 80034 79030 78222 77091 75620 74520 73758 73112 72175 71123 70088 69395 68876 67569 66141 65605 64676 64519 62977 62563 61611 60449 60031 58913 58497 57651 56764 56230 55494 54203 53510 53091 52139 51874 50848 50464 49797 48830 48315 47542 47180 46042 45784 45240 44766 43794 43760 42877 42496 41573 41309 40984 40114 39564 39499 38507 38199 37638 37423 36473 36392 35544 34772 34605 33858 33472 33342 32855 32374 31746 31661 31598 30786 30622 29917 29750 29392 29111 28631 28333 27945 27527 27064 26715 26538 26195 25506 25681 24872 24687 24648 24297 23937 23863 23075 23067 22464 22487 22316 22136 21737 21470 21284 20609 20316 20473 20449 20059 19740 19458 19238 19277 18719 18302 18358 18028 17848 17725 17452 17243 17425 16951 16745 16572 16435 16156 15873 15662 15637 15444 15334 15381 15061 14728 14609 14402 14386 14245 13959 13719 13536 13395 13057 13360 13020 12606 12472 12464 11979 12080 11956 11567 11611 11438 11169 11056 11155 10867 10872 10858 10572 10453 10289 10270 10106 9778 9853 10048 9843 9783 9522 9498 9476 9185 9172 8940 8899 9054 9503 8573 8831 8482 8263 9099 8273 8331 8103 8056 7947 7929 7910 7663 7710 7683 7513 7345 7431 7266 7056 7075 7005 6890 6928 6788 6591 6712 6555 6486 6463 6335 6242 6490 6239 6034 6008 5959 5933 6010 5990 6016 5865 5748 5685 5459 5433 5369 5501 5479 5315 5155 5248 5167 5096 4881 5037 5029 5023 4802 4773 4844 4764 4818 4689 4484 4529 4423 4400 4280 4328 4253 4307 4210 4378 4125 4006 4080 4051 4029 4064 3926 3947 3943 3883 4006 3772 3887 3534 3715 3719 3526 3599 3534 3490 3300 3484 3358 3372 3336 3253 3453 3203 3242 3114 3138 3070 3009 3031 3120 3018 2960 3018 3058 3046 2948 3031 2934 2887 2845 2933 2870 2817 2778 2701 2693 2756 2700 2675 2617 2605 2574 2461 2570 2527 2564 2472 2446 2541 2483 2405 2434 2403 2431 2351 2356 2352 2283 2301 2253 2252 2132 2250 2227 2147 2213 2205 2197 2159 2067 2152 2129 2099 2064 2005 2018 2049 2012 2010 1911 1953 1976 1931 1904 1924 1899 1789 1859 1935 1884 1858 1822 1851 1735 1805 1800 1836 1835 1803 1795 1807 1771 1814 1831 1859 1744 2040 1851 1736 1820 1723 1745 1675 1702 1705 1644 1637 1563 1680 1611 1619 1608 1723 1640 1475 1521 1483 1576 1491 1442 1506 1526 1501 1506 1554 1571 1448 1469 1431 1443 1391 1440 1473 1415 1331 1361 1380 1397 1429 1342 1274 1410 1371 1336 1298 1325 1304 1374 1297 1193 1220 1198 1227 1193 1206 1195 1179 1159 1196 1205 1223 1166 1086 1142 1089 1134 1118 1134 1084 1003 1028 1132 1114 1005 1075 1066 1148 1004 1016 1034 1027 1040 952 1053 1062 1055 1037 985 993 1070 960 1002 946 931 889 948 853 933 934 859 956 929 880 922 860 915 881 821 880 804 903 829 828 931 898 869 859 810 839 817 809 846 776 827 753 760 844 799 749 789 812 761 772 757 769 719 773 739 772 784 785 774 751 726 723 750 668 692 720 707 740 697 683 730 711 690 690 677 678 661 649 630 660 675 651 664 652 691 696 672 677 662 701 696 698 674 632 674 685 676 666 704 780 737 803 919 822 745 696 702 668 727 707 642 619 703 680 690 660 687 665 679 645 568 569 603 640 564 547 607 597 552 525 535 555 513 551 568 533 554 568 604 602 581 553 596 568 536 508 515 600 482 513 575 509 553 565 515 499 471 496 457 492 480 501 496 518 484 522 506 434 486 473 508 491 428 466 489 449 436 463 412 437 439 422 428 377 422 423 446 402 415 375 400 428 428 460 395 417 420 416 413 413 396 431 417 459 413 401 414 420 423 362 408 372 387 424 411 394 351 365 401 408 358 365 369 360 353 311 362 336 349 352 314 311 319 317 370 313 304 310 339 331 332 339 344 333 368 334 363 300 349 346 305 311 328 329 305 333 297 298 260 332 324 296 319 292 328 341 298 242 294 293 244 280 269 307 265 261 254 258 235 269 290 263 246 306 281 314 357 281 251 321 224 234 263 279 242 295 250 229 246 252 224 236 239 223 268 245 262 225 232 257 204 229 214 219 207 228 239 222 210 220 220 239 228 247 225 238 213 214 209 201 211 197 194 181 218 201 188 200 188 201 194 183 189 175 195 176 204 212 214 191 190 181 172 187 173 186 171 173 186 197 180 218 188 197 203 180 218 193 166 170 185 161 183 177 174 184 162 167 170 175 180 179 162 175 200 175 180 173 181 170 165 159 153 145 183 155 157 157 171 155 175 151 154 145 161 170 180 171 178 144 169 154 174 137 144 149 176 159 145 154 171 164 175 149 162 180 183 145 173 182 147 169 155 145 166 178 180 164 181 170 168 147 138 166 152 153 168 128 155 142 117 141 138 150 122 157 125 132 137 149 138 155 135 170 110 120 128 122 133 127 111 113 156 117 123 124 108 119 121 116 115 129 141 124 119 120 128 134 121 124 116 125 124 141 112 130 129 128 161 126 130 116 127 137 131 132 114 130 121 128 140 116 111 121 102 110 121 110 143 136 96 106 102 137 122 125 105 138 108 102 133 109 109 120 104 115 103 114 135 124 133 98 114 126 111 104 103 117 135 103 111 117 112 110 113 109 126 114 108 93 113 91 101 108 92 86 109 90 111 94 93 69 86 97 112 78 89 111 106 102 94 91 109 82 84 77 73 101 95 78 76 70 80 81 94 72 59 75 76 84 85 55 72 74 81 103 69 96 75 85 61 75 67 108 83 75 89 69 85 62 95 75 83 83 64 90 90 90 81 94 76 90 78 81 62 54 68 94 74 69 71 71 66 77 70 67 84 87 85 79 77 67 63 73 81 81 67 71 82 92 72 95 84 75 79 91 75 86 69 78 60 57 71 83 87 65 67 70 67 65 60 62 68 86 74 53 62 82 60 63 48 59 65 56 52 52 54 57 54 54 66 51 58 60 54 74 46 59 58 50 57 43 55 54 45 60 56 50 68 53 75 53 53 58 48 52 46 62 57 51 47 43 49 60 68 46 49 52 47 37 44 42 43 43 65 52 59 49 65 41 56 52 50 39 41 49 43 48 52 43 56 61 49 67 69 59 55 33 54 45 59 41 60 68 55 62 52 58 70 60 71 80 64 61 59 64 59 63 51 50 49 61 50 49 56 56 47 53 56 55 59 56 50 34 48 57 49 46 53 51 51 54 43 60 41 41 60 42 44 41 36 43 46 52 44 48 36 50 32 42 40 45 36 44 42 47 45 43 38 42 41 42 43 45 43 39 38 39 50 44 38 39 48 33 30 32 39 34 33 32 44 47 41 40 44 44 41 38 41 35 46 35 40 31 32 34 38 32 40 39 42 33 29 48 32 41 38 48 39 38 25 32 40 41 33 36 30 32 29 38 36 41 45 28 31 33 29 29 27 34 24 29 37 33 33 28 31 25 35 32 35 30 21 21 28 21 39 38 38 43 30 33 29 28 48 44 22 27 34 32 32 28 28 32 34 30 27 31 32 36 33 29 35 40 27 28 22 33 28 24 35 29 33 34 30 29 37 24 27 38 40 39 32 36 32 27 41 30 33 51 30 37 34 36 31 44 39 32 33 23 30 28 33 27 25 35 28 38 36 48 33 35 36 32 25 32 27 39 28 33 27 32 31 27 24 25 27 32 24 28 25 35 26 32 20 27 31 44 34 36 41 33 29 40 36 27 30 41 39 47 43 33 35 68 148 160 154 118 92 100 103 42 25 20 30 22 19 32 21 30 33 29 34 26 28 34 33 26 24 16 18 32 13 29 28 26 26 37 37 30 53 27 47 35 26 43 30 21 22 23 22 20 23 24 31 27 32 21 28 31 25 26 22 19 28 23 24 17 18 23 20 23 29 23 29 23 15 27 22 29 32 25 37 30 19 28 29 28 16 24 18 16 21 24 29 33 19 20 27 24 27 29 28 26 32 21 22 31 25 27 19 16 21 22 22 19 23 25 19 22 28 23 19 23 17 17 24 26 23 21 27 14 18 22 19 33 20 26 23 21 26 24 19 27 21 18 22 20 21 18 12 26 26 27 16 22 13 24 21 26 26 23 21 23 25 23 25 29 28 18 19 16 28 13 18 37 34 28 23 26 24 25 26 49 29 32 24 23 27 20 22 24 30 23 10 33 26 19 26 17 18 21 22 30 23 14 33 23 25 22 15 23 19 18 20 23 19 14 26 9 18 15 17 22 20 28 23 28 25 18 25 23 16 21 25 17 19 14 21 20 13 17 14 16 25 21 28 20 22 19 20 17 17 9 26 25 20 21 20 18 21 32 20 16 17 20 18 23 22 15 23 17 11 16 31 21 16 22 20 19 17 22 22 29 29 29 20 24 27 13 23 25 25 24 15 17 19 23 16 33 16 19 27 23 18 18 18 18 25 17 25 21 30 20 21 24 34 29 25 19 13 24 23 18 13 20 
];
B = [
0 0 0
 126593 39491 87102
 60182 18321 41861
 215364 77799 137565
 133149 43286 89863
 76069 23955 52114
 211364 78874 132490
 163295 55053 108242
 91184 29969 61215
 282062 103289 178773
 290700 99868 190832
 51746 16385 35361
 837621 311629 525992
 110034 38247 71787
 34690 11484 23206
 190319 81033 109286
 60146 23765 36381
 18525 6448 12077
 208875 89952 118923
 17082 5882 11200
 17498 6389 11109
 4086 1471 2615
 104 35 69
 3962 1560 2402
 309803 135907 173896
 20121 7094 13027
 25967 10146 15821
 322341 143056 179285
 18428 7528 10900
 38684 15515 23169
 506347 217354 288993
 36554 14841 21713
 64193 26942 37251
 362443 167234 195209
 243899 111928 131971
 406970 191267 215703
 746208 350768 395440
 603272 260552 342720
 375283 172264 203019
 874155 416516 457639
 341555 140947 200608
 23580 9787 13793
 797612 372231 425381
 12585 5217 7368
 22500 9316 13184
 1097917 534035 563882
 23020 9744 13276
 279964 115523 164441
 1525567 808712 716855
 280000 119100 160900
 9 2 7
 10988022 6100616 4887406
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
58 77 1 2
82 15 0 0
128 22 0 1
166 35 0 0
113 36 1 0
118 37 33 0
293 66 66 8
1443 82 75 17
9660 101 106 40
44991 147 157 75
115262 180 196 112
254419 230 267 168
489271 298 363 251
898038 404 497 347
1315150 505 654 511
1543379 690 862 799
1362464 959 1218 1179
980198 1251 1510 1526
599900 1870 1901 1903
309584 2441 2252 2355
128212 3299 2612 2668
34172 4008 2868 2870
8205 4287 3005 2826
6046 3852 3018 2990
5398 3881 3098 3255
5103 4399 3081 3284
5473 3999 3219 3248
4863 3880 3432 3420
4748 4369 3647 3536
4624 4244 3842 3796
4662 4441 4101 4107
5321 5020 4298 4453
5979 5355 4644 4568
6406 5726 4927 5104
6594 6086 5493 5513
6878 6432 5940 5983
7465 6936 6548 6425
8189 7741 7288 7216
8335 8201 7866 8107
8973 8863 8589 8696
10014 9911 9597 9701
10925 10789 10898 10957
12227 12324 12280 12096
13697 13881 13748 13722
15390 15388 15229 15345
17183 17227 17404 17684
19388 19637 19318 19346
21389 21430 21634 21457
23645 23901 23671 23699
26402 26363 25851 25521
28267 28286 27859 28057
29779 29823 29650 29654
31681 31552 31478 31487
33172 33048 32944 33323
35104 34608 35201 34481
35811 36193 35683 35934
38047 38153 38280 37724
40697 39988 40077 40052
41836 41586 41705 41437
43821 43162 43532 43205
45684 45703 45286 45331
45924 45546 45724 45621
44821 43783 44505 44009
39050 38809 39117 39462
29197 29294 29987 29156
17379 17896 17410 17154
8882 9346 9305 8782
6314 6366 6243 5704
5924 5183 5273 4883
4748 4914 5663 4402
3666 3700 3620 3967
2728 2245 2561 2701
219 232 194 206
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
