A = [
428467 448993 2939823 467252 409996 403574 410336 401936 408993 413144 471434 637532 877598 1176783 1725246 2156720 2343890 2572236 2688891 2597001 2391011 2191734 2051369 2104673 2339501 2568255 2574218 2426365 2258983 1780139 1666421 1415007 792022 792498 761652 745323 718012 688478 676835 673855 689325 722637 740611 765022 782849 781378 775452 762682 742892 737723 744444 747770 762858 771623 769399 770420 762052 743635 735036 729073 715792 719631 723869 720856 723956 720349 709266 698946 687807 671294 665100 662292 657314 655194 654377 647285 642066 634081 617916 605567 597643 587008 583160 579653 574006 570738 565451 553447 547205 534685 525305 515954 510414 501500 498150 495875 488416 481165 473136 462345 452863 444396 436973 432849 427151 419282 414806 408885 399968 392510 384443 373809 368343 361648 352025 348493 343335 335356 328763 323585 315262 309139 301916 293155 287780 282359 275367 270570 267284 260664 253900 248804 241840 236157 232841 226590 223481 220269 215901 212132 207716 203210 198561 195326 191149 188352 184963 181118 178590 175963 172466 169415 166044 162955 158951 156870 153586 152049 149246 146499 144561 141621 137860 137275 133940 131649 129476 127246 124522 122292 121978 118617 116829 115285 111762 109248 108531 105928 102538 102459 99898 98705 97530 94611 92942 91204 88457 87952 85691 83453 82866 81025 79621 78310 76755 75386 73152 71511 70155 68839 67642 65693 65493 64379 63251 61633 59996 59094 57910 56502 55554 54363 53156 52186 51459 49914 48927 48384 47446 46153 45606 44519 43954 42902 41567 40680 40205 39415 38550 37596 36765 36573 35226 34790 33691 33445 33023 31908 31116 30600 29694 29322 28779 28000 27560 27046 26376 25477 25629 24527 24041 23398 23261 22848 21925 21632 20908 20727 20195 19742 19342 18879 18762 18130 18008 17536 17046 16669 16388 15975 15643 15443 15166 14610 14218 13791 13577 13075 12889 12873 12674 12259 11843 11236 11400 11139 10715 10624 10272 10156 9937 9657 9520 9168 9152 8772 8559 8361 8234 7969 7836 7685 7563 7300 7127 7045 6710 6739 6556 6519 6383 6244 6011 5766 5828 5780 5640 5264 5473 5181 5128 5074 4872 4850 4548 4660 4473 4416 4387 4325 4113 4330 3955 3959 3927 3765 3598 3541 3599 3522 3440 3299 3257 3359 3220 3293 3120 3080 2962 2856 2752 2889 2731 2780 2731 2592 2659 2510 2513 2458 2452 2518 2426 2222 2248 2185 2142 2148 2127 2147 2107 2046 1959 2006 2016 1926 2004 1859 1812 1782 1789 1741 1702 1660 1627 1739 1654 1597 1606 1576 1573 1539 1477 1487 1527 1489 1505 1418 1345 1325 1398 1338 1333 1368 1342 1305 1271 1304 1333 1293 1235 1266 1221 1172 1131 1189 1085 1101 1119 1112 1048 1113 1098 1015 1026 1038 1014 1012 1043 994 1053 1059 972 1001 955 1062 970 930 926 901 936 889 918 910 916 854 948 848 884 912 951 845 828 816 815 773 834 790 822 842 812 805 889 786 738 776 741 717 710 736 766 735 698 732 753 664 701 714 639 750 663 626 715 690 652 689 666 644 651 650 656 604 681 659 618 608 573 585 674 641 611 598 675 636 598 639 577 649 700 627 703 629 610 635 524 615 546 624 619 581 580 519 543 553 521 617 588 560 530 522 589 560 515 562 564 553 495 501 511 513 503 450 508 549 464 498 492 522 438 434 442 525 463 470 493 467 488 429 526 527 461 468 470 430 456 432 457 441 461 456 446 458 429 430 428 399 490 417 479 390 433 429 410 391 420 413 430 370 362 456 420 461 441 398 417 389 443 383 381 420 357 393 412 398 357 395 355 387 368 397 391 378 389 403 323 365 324 361 391 355 337 370 335 358 325 325 354 320 356 383 341 330 322 341 337 325 329 293 306 334 289 272 335 323 296 311 289 330 306 309 303 298 268 346 325 255 304 303 301 303 270 326 273 327 332 300 283 250 291 262 304 295 318 262 277 259 305 282 289 290 286 265 275 304 259 269 257 270 258 279 239 271 235 271 229 236 260 250 260 250 259 241 271 237 297 237 255 222 311 233 207 267 243 262 222 241 255 232 237 259 256 230 252 202 221 271 242 245 236 255 265 245 283 274 239 269 279 218 282 257 214 227 248 241 260 224 261 227 226 210 230 263 214 229 209 204 203 206 190 216 237 216 211 217 202 193 218 188 201 226 223 190 191 221 185 192 195 230 188 177 188 174 187 176 177 190 197 182 184 210 188 181 177 170 178 168 170 182 178 153 170 149 149 183 183 162 172 172 156 156 172 143 170 159 173 170 141 155 160 152 149 152 151 168 165 167 160 185 155 180 157 152 169 155 173 135 173 158 158 174 151 157 176 162 178 149 156 126 149 124 174 127 168 159 164 186 135 156 152 127 151 156 141 154 171 170 175 146 162 161 136 134 153 167 147 139 129 155 147 126 136 155 111 130 145 112 150 121 122 111 115 111 129 153 108 121 140 135 118 136 156 124 144 132 141 132 127 111 104 122 141 111 125 125 147 111 128 117 129 139 105 150 122 132 121 117 94 113 104 121 126 128 108 96 109 121 110 130 122 83 94 130 126 112 111 114 107 108 111 112 117 122 124 109 108 120 129 128 112 96 99 103 139 109 116 73 85 96 92 77 91 79 82 101 90 90 83 105 93 94 87 94 59 101 81 100 103 98 78 81 77 106 103 85 92 81 75 78 103 104 105 87 94 76 79 95 98 92 88 71 78 86 90 93 65 74 80 83 90 95 107 78 71 57 81 79 85 87 76 57 77 86 94 63 85 80 72 80 82 66 69 67 81 66 53 81 64 68 74 70 70 62 47 65 51 78 83 54 60 80 69 63 45 74 72 66 73 65 75 71 60 85 63 59 63 65 81 69 71 86 81 63 84 52 66 73 80 56 75 80 55 86 69 61 70 96 69 81 67 62 77 78 70 71 62 71 82 70 77 57 48 70 67 59 75 66 73 64 56 58 63 73 60 75 62 43 45 59 58 41 46 52 54 74 55 56 53 60 61 41 56 53 54 62 84 51 65 58 44 39 55 55 53 46 47 42 46 48 46 52 52 51 67 47 47 47 46 54 59 36 34 55 46 53 49 52 36 51 43 56 61 44 53 50 46 63 51 53 46 52 56 36 59 50 40 59 42 58 51 52 49 52 70 57 48 75 32 69 48 40 43 50 65 54 43 49 51 40 52 36 48 37 42 41 46 38 38 50 47 40 49 45 43 56 44 35 46 48 38 51 41 41 30 42 42 36 37 28 29 37 31 27 40 31 38 38 37 33 27 37 43 37 25 41 32 34 34 50 43 33 39 32 23 53 47 27 35 31 37 44 33 21 34 36 38 37 26 29 38 29 29 36 32 29 22 33 33 33 36 24 26 33 28 29 25 40 33 40 41 41 31 26 35 23 30 22 39 25 32 25 29 25 26 29 25 35 42 35 31 33 29 33 31 40 36 52 24 35 37 36 46 26 34 43 53 41 42 31 49 40 33 37 25 41 41 40 41 44 34 36 33 37 36 35 42 29 30 32 28 34 33 36 41 30 34 30 32 44 31 28 36 29 35 31 35 31 27 38 33 17 15 23 19 30 27 21 24 18 31 26 34 29 36 38 21 25 19 34 16 26 18 26 29 23 16 17 23 23 16 33 26 29 29 22 29 23 28 24 17 15 29 28 31 17 23 29 35 29 29 19 23 19 23 19 21 34 29 11 22 26 20 21 20 25 28 37 20 15 20 29 27 32 15 28 14 18 37 21 23 41 22 26 16 25 29 31 18 24 23 9 34 20 35 22 26 37 15 29 19 24 21 25 18 24 25 27 34 17 14 31 26 27 29 23 13 25 26 26 20 15 34 23 18 25 25 25 22 24 24 30 25 26 19 23 21 18 24 38 41 28 25 28 18 19 15 20 24 25 18 26 29 21 34 12 25 34 14 22 26 22 18 28 14 9 24 21 21 19 23 25 8 21 25 12 25 26 23 26 17 18 18 23 21 23 19 18 20 14 15 16 21 12 12 19 15 18 9 12 18 20 13 12 19 31 16 14 32 18 9 19 18 8 15 14 9 18 20 21 21 20 30 20 24 17 25 19 22 14 28 18 16 14 19 21 9 14 11 15 13 24 21 17 11 23 18 14 17 17 16 17 12 17 15 21 23 27 13 22 20 16 22 19 23 21 16 9 17 25 20 17 33 31 23 24 26 18 18 23 16 26 28 28 22 20 17 15 20 35 19 26 27 32 32 32 23 24 33 21 35 28 27 29 29 28 17 31 31 21 22 19 10 17 13 21 18 9 17 23 17 13 19 18 15 6 10 15 16 15 8 23 12 11 15 15 20 30 12 15 24 14 11 17 20 12 13 12 16 19 11 7 20 13 11 11 12 18 21 17 19 12 13 17 10 12 23 21 14 13 15 9 25 19 25 18 18 15 13 14 14 18 15 10 9 12 7 18 13 13 11 10 11 22 12 11 10 11 7 10 8 12 11 16 13 12 17 7 7 11 12 5 18 12 18 8 10 9 11 10 6 13 14 5 8 9 14 6 12 12 10 15 9 14 13 11 16 6 22 14 12 13 4 6 10 20 11 13 16 7 11 9 9 5 18 11 15 11 8 6 9 8 15 14 8 9 10 13 10 5 13 13 5 14 11 12 9 3 6 15 11 10 4 10 11 3 14 7 11 9 11 15 11 3 16 8 15 9 9 14 7 14 14 9 12 9 5 6 6 9 10 8 6 7 9 5 6 6 24 12 10 10 11 5 10 10 14 3 7 9 4 7 14 6 7 7 17 4 6 3 9 6 6 11 6 3 2 5 0 1 6 6 7 5 3 2 5 2 5 2 4 9 3 4 5 6 1 9 6 4 4 9 10 9 4 4 6 8 14 7 6 4 6 4 9 6 3 6 2 3 4 4 2 6 6 9 9 6 4 5 1 7 6 7 8 8 3 2 8 4 5 4 
];
B = [
0 0 0
 49520 41099 8421
 48473 41597 6876
 62238 54253 7985
 56758 49695 7063
 53305 46980 6325
 56230 49664 6566
 70277 62119 8158
 55870 49694 6176
 77869 68767 9102
 85215 75652 9563
 66397 60832 5565
 157863 140525 17338
 69297 64622 4675
 67049 63116 3933
 51167 45512 5655
 22763 20694 2069
 35178 31803 3375
 25066 23123 1943
 25069 22971 2098
 26760 24770 1990
 30001 27426 2575
 30384 27912 2472
 39621 35590 4031
 31169 28336 2833
 52518 48406 4112
 40930 37967 2963
 102497 94753 7744
 42636 40378 2258
 127217 114429 12788
 50714 47772 2942
 38050 35618 2432
 65276 61512 3764
 84645 80678 3967
 52779 50778 2001
 74326 70312 4014
 30418 29289 1129
 33269 31880 1389
 44535 42056 2479
 58698 55900 2798
 30425 29405 1020
 49691 46878 2813
 44321 43089 1232
 27909 26845 1064
 103893 97450 6443
 37970 36636 1334
 41348 39984 1364
 68238 65256 2982
 73748 69603 4145
 78740 76129 2611
 52443 50527 1916
 41617 40501 1116
 74032 71541 2491
 49808 48100 1708
 110437 106001 4436
 61738 59248 2490
 43792 42108 1684
 57730 56502 1228
 78669 74370 4299
 118320 114513 3807
 57048023 55937975 1110048
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
6 62 0 0
0 9 0 0
4 18 0 2
4 24 1 1
11 19 0 1
10 24 0 2
542 44 5 4
16421 48 100 30
624451 42 325 107
3263192 57 490 220
5589958 81 560 289
7768219 131 708 494
8464422 275 1014 833
7832300 464 1707 1545
5218962 820 2983 2714
3536302 1403 4822 4676
1813053 2442 6905 6834
633736 3694 9390 9491
146215 5882 12008 12336
35608 9096 15185 15086
20634 12418 17606 17926
21880 16753 21341 21173
25832 21928 25143 25139
30303 27490 29592 29892
35900 33468 35257 35070
42273 39635 41118 40938
49249 46858 47600 47847
56218 54217 54973 55187
63468 62409 62639 62032
71040 69570 70101 69935
79691 77438 77318 77215
86743 83856 84343 84574
92850 90511 90440 90345
97487 96611 95549 96414
101064 100920 101087 100948
105601 105981 105598 105549
108141 108948 109004 108522
111239 111272 111211 111566
113162 113308 112461 113425
115534 115943 116905 116022
117494 117895 118233 117802
119719 120541 119239 120030
120482 121179 120706 120720
120008 122103 121373 121057
119469 120652 119254 120326
118436 119205 118457 118629
115347 115903 116081 115265
108243 109001 109151 109307
102481 102751 102079 102030
94767 93976 94516 94779
86090 86245 85713 86525
77881 78288 77610 77778
70083 69944 70136 69969
63604 63548 63712 63638
58561 58545 58240 58341
53849 53671 54039 54387
51546 50520 51183 51331
47979 48297 48071 48440
47421 47194 46885 47146
46884 46547 46677 46553
47733 47440 47253 48377
49032 49013 48431 48466
47926 48448 47950 48466
46499 46378 46365 46972
42704 43064 43014 42993
37401 37789 37189 37570
30791 30948 30851 30919
23998 24412 24632 24262
17728 17905 17462 17703
10960 11230 11066 10894
4451 4729 4628 4583
840 880 619 653
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
