A = [
3004371 2764389 51179847 1684796 1873546 1651818 1644573 1829159 1575869 1515684 1540357 1329780 1322793 1317165 1333348 1321229 1319091 1317100 1314673 1291732 1292949 1304251 1282420 1292195 1330774 1887344 1899813 1973333 2551439 2541645 2618446 2638346 2617888 2673682 2654468 2646828 2641088 2615146 2612290 2565408 2544499 2536605 2505363 2486573 2462239 2445207 2420016 2400536 2373095 2361390 2325874 2297477 2289566 2266987 2242201 2205832 2201785 2172555 2142081 2123597 2114243 2090189 2072072 2060422 2031731 2021893 2000243 1969818 1953037 1924068 1909720 1885258 1861155 1849819 1825953 1808697 1784147 1764301 1741472 1715611 1693243 1674997 1649761 1628705 1612644 1585033 1561966 1527482 1502646 1482991 1463709 1438520 1425399 1402400 1385349 1367084 1348663 1330031 1313680 1296859 1278118 1263209 1242443 1226401 1210167 1194575 1175813 1160578 1148479 1131439 1113476 1100496 1087684 1071606 1055716 1041618 1026521 1013427 997674 984474 970946 954524 944191 928409 914649 900487 889527 876604 863103 851601 839500 825771 814258 804682 792135 781476 770212 757756 747522 736656 727644 717650 706097 694737 686483 674721 665537 656543 647374 637750 627668 618899 610414 600502 591927 584427 575144 565927 558554 548085 541892 531827 525092 517622 509575 500631 494402 487244 480594 473283 463935 458445 451905 446437 440301 430780 424749 419539 413023 407436 401877 395154 388299 383138 377840 372261 365202 360886 355757 350087 345549 339442 334623 328691 323627 320120 315660 309104 304343 300686 296732 291119 286348 283218 278175 274761 270499 266153 261704 258118 253920 249625 245780 242185 239446 234934 231293 226950 223498 220854 218018 214030 210797 207887 204291 200937 198112 194499 191567 188127 185346 182529 180521 176783 174392 170869 168625 166101 163460 160944 158639 155645 154144 151062 149054 146016 144623 141895 139489 137104 135189 133817 131572 128986 127225 125108 123197 121544 119876 117654 114730 113340 111893 110313 108712 106613 104611 102342 101346 99622 97783 96374 94857 93735 91908 90346 89155 87796 86113 84508 83273 82062 81292 79393 78144 77075 75941 74341 73307 71929 70893 69275 68947 67305 66554 65494 64275 63355 62283 60988 60088 59585 58282 57583 56441 55007 54616 53402 52867 52174 51281 50187 49422 48488 48056 47009 46209 45715 44980 44133 43600 43040 42199 41556 40585 40206 39146 38617 38057 37929 36629 36444 35710 35160 34425 33948 33668 32620 32025 32208 31798 31054 30370 29859 29531 29200 28458 28000 27480 26890 26324 26203 25359 25401 25043 24401 24229 23741 23172 22978 22606 22157 21923 21235 21081 20843 20655 20353 19912 19472 19051 18902 18629 18418 17959 17747 17451 17119 16993 16611 16470 16170 15864 15398 15225 15043 14872 14607 14229 14170 13833 13492 13307 13324 13168 12849 12977 12539 12435 11948 11869 11594 11573 11457 11266 10869 10892 10571 10503 10394 9942 9988 9766 9495 9577 9230 9178 9120 9114 8799 8790 8683 8427 8270 8069 7960 8089 7787 7722 7550 7440 7240 7238 7164 6906 6875 6708 6704 6491 6398 6362 6307 6060 6160 6064 6001 5758 5809 5693 5559 5404 5364 5362 5148 5198 5176 5086 4887 4949 4841 4793 4765 4627 4494 4453 4384 4464 4368 4241 4166 4082 4000 3930 3992 3842 3967 3824 3869 3596 3700 3536 3541 3505 3554 3364 3327 3329 3214 3198 3191 3202 3189 3139 3041 3037 2977 3029 2984 2904 2835 2850 2709 2788 2675 2681 2645 2576 2570 2514 2505 2521 2450 2360 2364 2302 2287 2384 2242 2153 2205 2111 2172 2091 2158 2102 2042 2070 2024 1980 1931 1958 1965 1933 1829 1850 1860 1780 1809 1818 1801 1681 1753 1682 1651 1707 1676 1683 1635 1557 1607 1601 1516 1583 1526 1584 1485 1505 1508 1444 1398 1422 1415 1386 1398 1387 1348 1340 1303 1363 1296 1296 1266 1235 1285 1259 1239 1218 1272 1169 1262 1192 1154 1181 1133 1116 1165 1076 1131 1105 1098 1116 1042 1011 1066 1078 1077 1040 989 1070 1015 1006 1001 1033 983 981 942 982 938 970 901 928 941 915 927 870 904 913 903 905 899 834 811 850 852 877 833 785 852 830 798 810 814 808 854 852 766 753 755 785 726 752 698 712 740 733 706 809 774 724 721 772 746 696 741 691 695 727 708 697 658 683 652 666 659 690 693 685 636 620 628 651 590 604 670 633 581 610 634 586 600 585 621 635 513 572 563 530 566 574 595 610 595 591 578 548 556 522 536 558 529 507 513 537 544 541 524 509 470 531 508 485 529 518 495 499 485 476 534 439 501 493 471 523 444 505 455 485 426 500 457 460 457 456 453 432 465 493 436 442 438 441 423 452 410 445 454 417 427 430 435 397 401 420 420 438 432 442 398 424 394 415 372 385 402 360 413 402 363 409 394 369 357 327 385 371 382 354 371 340 358 346 362 357 347 394 398 359 348 344 370 330 350 295 356 397 340 344 344 315 320 324 345 329 321 331 329 326 309 317 304 326 297 307 325 285 324 312 318 293 290 289 293 297 248 309 305 349 273 294 319 282 295 262 256 282 306 274 242 253 270 259 284 242 256 252 248 266 255 263 264 289 264 251 268 247 270 258 245 238 216 259 253 231 242 222 241 239 249 233 218 228 232 234 232 218 213 213 230 239 217 221 242 213 224 213 194 209 238 221 202 203 214 210 183 203 194 232 201 211 186 205 185 212 215 189 198 203 212 172 191 213 177 205 189 197 181 186 180 195 172 167 178 194 154 171 191 201 177 176 182 156 190 155 165 180 187 199 171 176 162 167 180 165 193 158 173 170 191 158 176 160 197 191 151 172 180 157 148 171 171 162 154 162 147 128 167 167 122 143 144 140 142 147 164 138 171 155 180 160 159 144 117 135 139 129 143 139 151 118 136 151 136 126 127 133 131 127 131 133 137 133 114 132 120 120 131 130 107 110 131 109 130 125 85 127 123 121 117 114 104 112 123 112 136 130 119 125 134 113 120 112 102 121 112 134 112 109 100 123 106 120 104 108 129 134 108 101 127 96 102 103 97 91 101 98 99 94 104 88 98 114 107 123 103 129 123 100 117 89 109 97 101 95 103 108 97 92 96 89 100 94 104 104 85 110 103 94 89 112 87 102 93 74 88 81 77 83 92 93 85 88 85 86 87 89 68 76 81 77 70 72 65 79 82 74 89 78 77 80 91 77 78 100 77 70 75 69 66 72 85 81 58 70 83 77 71 68 63 71 74 62 94 57 69 49 71 70 70 71 55 63 53 68 67 63 53 89 61 64 77 84 71 203 196 243 220 245 196 196 223 191 210 196 212 156 166 139 131 73 57 65 84 75 69 65 44 57 61 56 55 62 54 56 51 48 66 45 54 69 62 66 53 54 53 66 78 50 51 57 55 62 64 48 39 45 53 47 63 42 53 52 40 35 52 52 44 55 51 55 46 52 45 55 49 77 67 53 51 71 48 51 58 62 46 58 46 46 49 44 34 39 36 44 30 48 55 42 42 33 43 47 33 49 49 37 53 40 35 32 42 40 45 49 46 50 54 44 46 87 58 46 48 37 40 39 43 44 38 40 26 43 39 36 42 34 34 37 39 37 28 35 35 40 38 32 38 38 38 33 28 34 28 33 37 46 38 39 38 26 37 35 36 53 34 39 24 38 34 30 35 29 27 36 26 28 27 34 38 37 22 27 27 15 26 25 28 32 26 32 21 37 22 33 25 31 20 28 25 32 40 66 36 41 40 28 17 31 24 37 26 39 28 26 26 23 16 25 23 27 28 19 33 25 25 28 22 30 28 15 26 32 27 23 22 19 14 29 17 24 22 24 20 26 19 28 35 26 26 26 23 19 16 19 18 22 19 32 15 15 20 27 24 23 22 18 19 20 22 21 26 17 22 18 15 16 13 19 19 13 25 14 16 16 16 25 36 27 21 16 15 20 16 13 20 13 13 20 18 17 21 18 21 19 19 18 19 14 16 18 19 12 22 19 17 15 21 19 15 19 27 13 15 13 16 24 23 34 34 29 40 61 45 37 24 28 17 25 26 25 25 26 27 22 8 13 9 13 14 13 19 15 10 14 18 17 20 15 14 22 22 17 22 14 20 19 12 16 22 13 18 13 18 9 18 16 12 15 11 9 14 13 18 20 10 8 11 16 7 12 19 15 10 13 9 9 17 14 12 21 16 13 10 14 12 14 12 13 13 6 12 5 7 11 9 14 16 15 12 8 16 12 16 14 6 16 19 11 9 11 13 14 6 11 8 13 11 9 7 12 12 10 8 11 11 11 7 8 11 9 16 22 9 16 16 12 8 14 13 5 17 12 10 13 15 21 7 11 12 12 8 4 12 8 12 9 10 8 9 5 11 13 12 9 9 5 9 9 9 8 8 10 5 7 6 6 9 11 9 8 11 8 5 14 10 7 10 9 9 11 3 6 6 9 11 12 6 13 12 9 8 6 11 8 8 4 8 11 11 6 14 9 10 14 10 4 11 7 6 2 10 4 7 7 5 4 6 10 7 2 8 8 11 8 10 11 6 8 7 9 9 5 7 5 4 9 6 5 7 7 5 7 10 13 6 8 5 7 6 6 8 9 4 5 6 8 5 8 7 6 7 4 8 6 7 9 6 7 7 7 5 7 4 5 11 9 5 7 6 3 8 2 12 7 12 5 8 6 7 6 7 4 4 6 5 10 6 9 6 4 6 5 8 6 3 3 3 2 4 1 2 6 5 4 8 7 6 5 4 7 5 5 5 5 2 5 2 1 8 6 7 6 4 7 4 5 3 5 2 2 6 5 7 6 8 4 5 2 4 4 6 6 3 2 3 5 6 10 3 6 8 4 7 6 5 8 10 1 5 4 7 10 2 2 4 3 7 5 2 1 6 3 5 5 9 8 8 4 6 2 5 6 5 3 5 5 2 7 6 5 6 8 12 7 3 8 8 6 9 3 8 5 5 4 4 4 5 6 1 4 4 3 3 2 6 5 4 2 7 3 2 5 8 10 6 11 6 11 7 6 6 10 10 9 4 8 4 4 2 2 3 4 7 2 2 4 3 3 2 3 2 4 11 7 1 2 6 3 4 2 4 4 4 0 2 2 1 1 1 4 6 5 10 3 2 2 4 8 4 1 3 3 2 3 2 3 4 2 8 3 3 8 6 4 3 2 1 2 4 5 6 
];
B = [
0 0 0
 1792916 1383554 409362
 909674 690452 219222
 1991156 1595944 395212
 1739812 1382905 356907
 958725 762352 196373
 2268717 1861853 406864
 1219394 985542 233852
 1776244 1468890 307354
 2113562 1744713 368849
 970137 798534 171603
 2937657 2446985 490672
 1740639 1458675 281964
 592352 491838 100514
 1565340 1329540 235800
 1076744 915255 161489
 354583 298618 55965
 1676078 1429614 246464
 721864 621307 100557
 163344 137126 26218
 99246 83670 15576
 52264 44149 8115
 37801 32345 5456
 2547617 2172402 375215
 1134953 977356 157597
 283917 240284 43633
 2622649 2243244 379405
 1311668 1132055 179613
 276955 239139 37816
 3808052 3251500 556552
 1657565 1433610 223955
 496174 431540 64634
 2951136 2551633 399503
 1657499 1457248 200251
 3579301 3111210 468091
 1371647 1227801 143846
 2351761 2089429 262332
 6292078 5513204 778874
 1837228 1645018 192210
 4052291 3624514 427777
 6246464 5488366 758098
 2208352 1970859 237493
 4716836 4202481 514355
 4971130 4399642 571488
 1549524 1383122 166402
 5643718 5076639 567079
 5859416 5217888 641528
 1742222 1529404 212818
 6907949 6316539 591410
 11368212 10199446 1168766
 289407 254529 34878
 12738934 11683865 1055069
 17064760 15452767 1611993
 860544 760518 100026
 6 6 0
 27189596 24767083 2422513
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
320 466 3 3
69 76 0 1
110 131 2 2
151 137 5 4
127 145 21 23
612 187 1677 154
179008 265 4825 657
877692 313 5960 1424
1861604 428 7495 2168
3060717 564 9758 3489
4263187 742 10992 4933
6414700 1134 13367 6760
8739071 1709 15413 9197
11430373 2810 17878 12268
12935765 4595 20070 16094
13308380 7710 24506 21241
11476631 11554 29116 27107
8195707 14807 36224 35573
4682441 20315 46573 46166
1917365 29111 58641 59135
529451 41615 71894 71982
143771 55801 86548 86447
106530 75733 102672 103295
120490 98691 120136 120609
140449 125735 140634 140642
160857 153656 162760 163496
183912 183560 187082 186505
209000 211629 211497 213062
234311 239815 237973 238103
258268 267458 263007 262831
281040 289859 285187 286373
300275 310508 304663 305429
314891 326983 319872 320881
325749 338642 332374 331311
333062 344903 338356 339402
337466 347259 341162 341949
336379 347980 341962 341864
338651 346037 339938 341399
336847 344624 339866 340079
338400 343237 340328 340326
342549 346248 342573 344346
348458 352566 349091 350633
359004 361717 359460 361320
371686 375194 373365 374481
390303 392301 390859 391668
409876 411821 411086 411577
431468 432762 432941 432200
450977 452399 452453 451791
467274 469940 469078 469655
481078 481378 481243 480398
484606 486379 485701 485202
480369 483582 482565 483455
468290 471469 470777 471841
452401 453056 454008 452752
426598 428540 428220 428248
396896 398250 396588 398599
361009 362560 363220 363007
325873 328500 326472 326833
290906 292874 292353 291575
259315 261538 261328 261175
234074 235327 234307 233981
208095 208373 209087 208588
190569 190785 191605 191118
180318 180952 180909 181242
173429 174096 173294 173178
170333 170851 171131 171183
178220 179334 178496 178485
207939 206226 206798 206679
190403 191337 191055 190734
199335 200011 199978 200216
187499 188944 187441 187366
167506 166967 166718 167762
175521 176354 176716 176430
119488 119741 119991 119126
99795 99653 100120 99895
81398 81336 80295 80765
66417 66265 66229 65934
57220 56826 57391 56744
48204 48875 48005 47960
37962 38276 38358 38466
24154 24258 24142 24108
11866 11847 11977 11738
596 590 602 573
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
