A = [
6936730 6331314 64869387 2733982 1731904 1597865 1457050 1209895 1125015 1027574 995553 941374 934339 911972 871497 852527 832228 829803 827389 795773 786489 792209 777474 764647 758437 782101 776041 767330 781287 714732 713606 704907 644034 635829 625190 626172 625224 620129 618280 628612 617737 626016 627735 627306 640521 626866 622801 646273 633835 624869 631513 605266 612866 607921 590986 578263 586006 592926 571712 563829 575535 566588 559150 550815 552868 559304 534842 549160 540505 515136 513711 548453 507509 506501 509252 505103 501777 502159 494487 488153 486256 486828 477400 472893 474990 462377 454185 438548 431770 431087 426343 421556 421172 418376 414129 412750 410425 408428 405993 402711 401503 399965 396647 394473 392566 392743 391436 389223 386987 385859 382143 383341 383198 382820 380881 380051 395867 397937 398532 413560 420369 422991 423314 425662 426400 425466 425393 423275 420768 419452 416041 414373 414034 413287 410798 409788 408806 406011 403761 403321 402163 398498 398097 396942 394446 391705 391087 388343 385005 383229 378677 376453 374177 371250 371174 369456 364520 362684 359435 358427 355720 352371 351703 350509 346839 344415 341772 339256 337069 334495 330799 330369 329010 328184 323815 321346 319518 315904 315444 311226 309718 306190 305477 300527 302811 298243 294840 293602 292060 291381 288067 283110 280442 279051 276237 273690 271330 268967 265715 262383 261666 259260 258300 254438 252305 251267 246394 244545 240985 237681 234511 231755 228555 227560 226103 222680 220754 217455 216760 214554 212343 209276 205530 203651 199089 195877 194567 191486 190172 184589 183155 181042 177911 173826 171005 169938 167334 166013 162511 160070 159708 155826 153624 152569 150471 147667 146013 143266 142596 140162 138710 137309 135828 131721 132076 128917 127008 125084 123636 121794 119833 118054 116294 114312 113962 111982 110139 108241 107698 105939 104331 101822 100825 98180 96839 95323 95384 93414 92148 91271 89158 88734 87259 85651 84832 84002 80975 80923 79893 77233 76201 74919 74084 73229 72314 71773 69900 68641 67793 66696 65436 64600 63485 62727 62015 60819 59362 58682 57735 56813 56000 55005 53826 53291 52646 51270 51149 49892 49319 48757 47690 46591 46691 45230 45291 43674 43233 42593 42600 41342 41001 39754 39222 39116 37633 36969 36784 35837 35398 34926 34106 33654 33408 32720 31930 32036 31582 30552 29918 29477 29012 29142 28449 27823 27438 26957 26540 25894 25656 24699 24437 24655 24088 23699 22884 22326 22314 21820 21745 20893 20652 20758 20053 20410 19846 19127 18641 18402 18313 17731 17545 17328 16933 16899 16259 15722 15580 15453 15407 14718 14817 14324 14223 14046 13368 13561 13232 12772 12517 12668 12050 12176 11904 11733 11472 11269 11085 10678 10806 10476 10452 10407 9754 9571 9922 9617 9521 9126 9159 8966 8963 8788 8567 8272 8411 8009 8036 7925 7872 7543 7736 7448 7248 7191 7040 6722 6796 6591 6519 6352 6362 6213 6038 6018 8020 5814 6023 5520 5514 5620 5391 5192 5247 4950 4953 4800 4804 4744 4527 4504 4515 4458 4424 4444 4208 4275 4137 3907 3991 3859 3643 3825 3666 3568 3625 3517 3388 3485 3421 3339 3241 3190 3220 3054 3142 3009 2948 2951 2804 2821 2739 2664 2680 2663 2446 2593 2514 2398 2551 2522 2288 2257 2193 2188 2222 2208 2054 2157 2053 2019 1927 1935 1919 1819 1841 1771 1880 1701 1766 1763 1699 1794 1705 1747 1583 1610 1589 1454 1525 1521 1440 1432 1419 1224 1322 1359 1367 1266 1377 1216 1274 1256 1291 1165 1143 1128 1139 1194 1056 1052 1025 959 932 986 1041 902 929 921 1008 960 937 889 870 908 876 839 815 842 821 810 719 745 756 856 692 667 710 705 707 660 666 661 737 1289 653 552 613 661 632 565 567 590 508 568 542 543 562 556 526 508 522 528 499 478 430 478 449 525 460 464 431 480 423 451 400 382 415 438 410 384 389 452 367 355 402 383 354 353 345 404 324 390 350 307 337 328 313 371 325 318 312 380 361 322 344 268 298 325 300 284 254 271 262 280 297 282 295 283 260 306 292 210 277 216 282 254 240 224 256 264 237 258 237 267 246 212 212 205 209 203 192 199 240 228 200 208 197 230 198 294 213 199 196 180 231 225 181 206 222 184 204 166 208 191 223 226 183 208 182 153 182 175 165 197 156 162 175 182 169 153 192 163 175 183 215 208 194 173 200 226 213 198 169 230 296 218 183 255 221 223 218 244 137 213 229 190 142 164 171 149 163 187 208 198 165 148 175 161 140 184 137 143 128 189 121 145 135 111 158 153 127 240 130 136 114 177 140 132 145 120 126 138 127 159 123 107 119 111 108 123 90 105 109 111 126 139 121 122 136 100 111 102 100 111 197 366 202 147 132 113 174 132 99 130 141 142 148 131 119 103 111 117 147 116 120 158 137 126 94 112 110 98 97 97 98 138 86 96 116 113 94 104 110 113 122 96 90 99 123 114 106 90 84 114 108 83 100 88 115 94 153 92 88 73 98 83 60 105 98 93 63 95 62 70 72 98 76 63 79 67 65 73 73 98 96 92 62 112 88 70 77 82 76 77 71 102 77 68 78 72 69 67 68 63 80 77 75 85 84 92 80 73 76 53 83 65 62 68 76 61 77 54 68 80 65 68 70 89 74 71 71 62 49 76 73 53 68 57 48 68 57 59 52 67 94 87 69 57 51 87 68 75 82 72 75 80 65 62 59 88 91 77 57 82 77 85 67 52 63 69 61 71 54 63 60 43 64 39 44 59 50 38 60 60 65 38 52 56 98 67 62 64 79 157 60 77 74 64 103 100 91 97 103 89 62 111 79 85 87 124 84 88 64 96 95 85 83 102 91 90 95 117 107 135 100 76 103 109 110 92 83 85 92 93 81 118 99 102 122 100 73 79 91 101 116 102 89 89 111 97 75 109 362 115 139 104 117 144 139 129 149 140 167 149 163 124 113 509 139 157 151 101 497 88 102 113 98 97 105 93 86 104 98 119 106 82 85 90 94 126 158 98 87 79 85 98 115 82 90 65 88 120 116 108 108 143 130 105 138 129 127 136 176 135 162 981 249 177 188 161 115 76 100 65 66 103 66 63 56 58 64 45 48 53 30 72 44 53 62 49 46 46 45 36 43 43 43 54 42 41 33 52 58 53 50 46 45 751 49 89 84 83 104 111 87 95 105 103 62 55 70 59 49 52 55 54 65 76 55 52 38 41 40 60 156 46 36 56 36 42 34 61 45 50 38 46 42 83 46 42 59 97 59 53 73 59 343 54 32 62 76 233 57 84 58 78 526 52 45 36 58 51 33 31 32 46 95 41 50 73 72 845 33 28 23 38 58 35 41 47 38 130 49 46 49 43 46 27 31 35 49 31 44 40 35 42 36 56 53 52 33 57 32 49 56 51 50 73 48 51 38 39 50 44 62 50 37 44 43 40 48 53 50 48 47 53 56 47 37 54 64 46 50 54 38 51 47 50 64 70 50 63 57 60 64 53 77 78 67 81 85 96 80 61 58 121 99 103 100 77 978 114 116 112 131 2158 130 110 114 89 2306 77 46 63 54 371 67 74 72 72 97 59 46 23 20 37 29 25 28 24 94 42 17 23 28 24 26 12 12 15 16 17 16 7 14 17 14 17 17 13 15 16 42 12 12 13 7 14 11 12 13 23 11 11 25 25 7 12 25 13 13 9 17 37 13 23 18 12 23 21 25 30 23 23 19 13 22 12 30 34 36 25 27 31 865 39 35 30 39 38 26 20 14 21 9 12 14 12 18 31 13 14 9 13 15 19 9 9 14 21 12 3 16 6 2 22 13 17 14 19 5 13 10 7 11 18 12 10 9 13 11 10 11 9 17 5 10 14 10 10 13 16 12 16 16 7 11 12 11 20 14 13 18 18 11 13 14 15 11 4 34 31 10 8 18 8 11 25 13 23 13 19 10 12 14 19 22 15 28 11 22 12 19 14 19 20 13 20 19 83 74 70 90 71 93 74 119 122 183 126 118 126 125 92 126 144 112 271 162 148 111 134 90 140 131 16 21 26 17 34 31 19 28 27 33 21 38 23 19 41 19 30 21 26 52 21 28 33 32 37 33 48 33 24 58 38 23 43 36 27 41 21 25 28 44 34 18 30 34 27 29 27 16 7 8 14 18 6 20 18 10 17 19 17 13 18 12 13 11 17 20 8 11 15 14 13 15 7 11 17 14 13 10 9 14 19 18 21 13 7 26 14 14 14 10 5 12 16 7 34 12 9 11 11 8 17 17 10 20 6 9 5 11 10 3 9 4 9 13 9 4 5 4 14 4 5 7 12 10 15 14 11 13 14 7 10 5 8 8 9 7 5 5 1 8 2 4 4 1 6 7 10 4 12 3 4 11 4 10 6 5 10 3 5 8 21 7 17 6 5 8 21 8 12 9 15 5 5 11 14 4 6 11 4 0 7 12 10 5 5 15 11 9 3 13 6 3 5 10 18 104 3 7 8 5 8 4 6 9 2 28 5 5 7 5 1 4 5 3 8 2 4 3 4 0 7 6 6 4 0 5 2 6 5 11 4 6 10 3 4 3 5 8 4 7 8 2 7 19 54 29 3 6 3 8 21 4 8 5 5 9 6 3 4 10 3 9 7 9 7 6 1 14 18 11 4 8 8 13 11 5 6 9 15 7 14 5 1 8 4 3 7 8 5 5 12 5 6 5 1 5 13 1 8 9 13 1 5 8 8 11 14 5 5 6 12 10 15 6 2 4 2 2 9 11 12 9 8 4 2 4 2 8 2 14 15 5 17 14 24 18 16 24 15 16 16 10 5 12 6 14 14 29 23 36 22 23 22 24 11 15 25 17 24 10 31 27 37 16 10 20 22 20 28 20 10 29 32 23 39 44 18 34 38 32 28 23 40 35 27 39 33 39 34 13 26 21 27 31 48 29 42 40 25 26 34 38 34 30 23 29 12 1 4 6 1 4 1 6 3 4 3 17 7 2 2 3 9 4 9 1 3 8 6 7 5 3 3 1 5 5 2 3 3 6 3 3 12 9 3 4 3 4 10 7 3 3 6 4 2 
];
B = [
0 0 0
 436494 298410 138084
 1332342 1132349 199993
 490500 379011 111489
 341843 275343 66500
 197951 154036 43915
 123530 94594 28936
 103684 79087 24597
 179242 150867 28375
 214867 179193 35674
 792657 736284 56373
 294188 252448 41740
 255433 223270 32163
 228754 202852 25902
 206217 182006 24211
 483306 453523 29783
 258653 233368 25285
 235170 210079 25091
 213418 191987 21431
 207154 184029 23125
 406773 379626 27147
 258760 232850 25910
 248467 223709 24758
 233791 208763 25028
 215128 191295 23833
 345987 318892 27095
 237606 213256 24350
 257922 231603 26319
 247724 223339 24385
 230666 205442 25224
 309430 282487 26943
 246446 221870 24576
 242511 217915 24596
 237901 215065 22836
 249391 222335 27056
 283503 259753 23750
 247295 223291 24004
 344183 298116 46067
 238993 216511 22482
 259727 232922 26805
 351775 310122 41653
 255367 229947 25420
 317862 279418 38444
 243616 221669 21947
 249100 224065 25035
 344134 304247 39887
 261217 235873 25344
 328299 289723 38576
 262805 238577 24228
 315825 279051 36774
 274701 250858 23843
 317598 280556 37042
 275504 250198 25306
 317866 281200 36666
 260557 236698 23859
 336709 297664 39045
 309496 274620 34876
 262080 240074 22006
 313850 278914 34936
 243567 225577 17990
 98173303 95916231 2257072
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
65 160 2 0
9 20 0 0
20 94 0 0
18 45 0 0
30 30 0 0
23 38 0 0
62 115 4 1
122 96 0 2
38202 107 3 1
395974 168 6 1
1018116 165 16 5
2309325 238 57 23
4834777 323 665 177
9620686 584 3093 1186
16657071 718 3227 1703
21262410 1670 3455 2063
19473504 1980 4726 3952
14028999 3533 6889 6745
7546789 5605 9980 10385
2911613 8210 13179 13537
738431 10744 16003 16445
114547 14611 19412 19715
28548 18732 22662 23614
27554 23589 26064 26782
30987 28776 30313 30890
35127 34001 34565 35112
40210 38502 39362 39471
44237 44355 44542 44647
49435 49925 49183 50322
54356 55850 53488 55191
59909 60747 58447 58977
62407 67506 62112 63533
65703 70011 65673 69900
68383 72649 68007 70485
77725 72514 68876 69590
72685 73384 68390 69512
68571 77085 69284 71627
66382 68209 67118 67972
66902 68347 67194 67395
66734 65409 65480 68631
70776 64936 66536 64236
66679 65922 65176 65029
67848 73201 66131 66134
68237 67025 68932 68658
70167 69342 70890 72348
81679 73205 71751 71588
72068 72162 71787 73416
73516 72772 72939 74188
72642 73179 73230 73452
72622 72547 76082 72549
69946 70713 70696 70350
66894 67251 66032 66987
62797 63260 62783 63017
57278 58728 58243 61910
52955 53745 52712 52801
47510 48382 48018 48142
42028 43238 43197 44273
38759 38570 38656 38992
34391 35263 34482 35234
31058 31763 33058 32188
29763 29439 29319 29605
27923 28442 28661 28051
26214 29846 26608 26332
24146 24593 24558 24871
23079 23441 23240 23449
22666 22820 23745 23442
22546 22671 22391 22658
30991 47772 30423 24749
22258 22678 22848 22468
22060 21911 21910 21925
21854 21438 21320 21914
20882 20571 21670 21913
19527 20117 19470 20080
18510 18403 18532 18795
16317 16226 16417 17099
14665 14822 14818 14848
12731 12513 12470 12616
9059 9117 9214 9194
7412 7325 7385 7467
5660 5603 5698 5631
3419 3345 3212 3331
2238 2153 2244 2296
146 135 129 156
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
