A = [
598651 515657 2386085 594174 532979 524355 511138 520475 512482 489972 490782 493531 490081 487070 486034 484634 481715 481349 476139 472365 474338 472121 470434 492418 517460 678466 693764 716897 871098 872110 870082 874680 881704 876866 875760 869665 854831 846089 837250 825807 820754 817889 809565 806360 807106 792091 786644 781543 764257 755823 753645 746023 739437 740917 729591 727459 720502 707906 699643 694578 684316 676974 677537 666803 664083 658747 649941 645628 641728 633192 625210 621024 613382 607770 601568 596011 593627 584973 579313 571522 568878 557017 554848 549210 543364 539292 535493 530835 524694 519856 510201 506957 501023 495632 491172 488021 480306 474517 474127 466473 461809 453679 448723 444928 441213 435484 430671 428686 422001 417940 411455 404704 401747 396664 392687 388187 384934 380377 377537 374039 366737 363277 357760 352696 348591 344786 342036 336680 333215 330805 324474 320414 316532 312835 310454 305431 299481 299390 294448 291408 286421 281856 279152 275910 271306 268474 264328 262202 257490 255148 252753 249058 245444 240422 238243 234653 230375 230088 226352 222258 220372 216078 213984 211107 207451 203310 202112 198872 197620 193647 191661 188482 185248 182651 179652 178669 175012 171984 169998 167717 164234 162558 159615 158376 156035 153994 151024 148910 147398 144459 143314 140767 138469 136337 135549 132650 130863 128713 127519 125451 122901 123013 120712 118440 114818 114281 112837 109989 109761 108397 105060 104502 103227 100498 99739 99252 97174 94225 94179 92056 91593 89982 89441 88273 85795 84067 83188 82329 81459 79321 78681 77288 76100 75175 73563 72958 72534 70929 70256 68595 67159 66461 66206 64770 63674 62693 62062 60510 59595 58023 57645 56950 56124 55306 54650 53685 53361 52367 50691 50343 48847 49065 47544 47389 46422 46384 45334 44309 43465 43193 42601 41722 40733 39874 39429 38696 38612 37925 37288 36743 36322 34910 35067 33941 33475 33323 32912 32096 32188 31152 30569 29854 29937 29565 28408 28677 27793 27876 26960 26617 26078 25596 25623 25050 24655 23694 23933 22677 22776 22341 22507 22398 21801 21078 21034 20641 20146 19473 19462 19176 18883 18324 18377 18106 17925 17267 17186 16758 16622 16507 16151 16037 15806 15489 15211 14374 14717 14408 14582 13889 13963 13163 13246 13001 13066 12570 12040 12236 12024 11769 11719 11633 11331 10559 10809 10844 10954 10342 10187 9884 9797 9520 9107 9190 8851 8949 8895 8641 8513 8427 8126 8143 8038 7804 7393 7561 7222 7223 7033 6996 6947 6716 6445 6584 6372 6365 6240 6100 6025 6019 5866 5819 5612 5347 5615 5681 5239 5161 5054 5104 4918 4985 4832 4795 4515 4552 4415 4406 4445 4416 4200 4405 4134 4072 3833 3782 3890 3952 3554 3817 3560 3568 3614 3576 3245 3416 3219 3060 3000 3361 3181 2999 2999 2829 2849 2861 2913 2892 2736 2762 2648 2522 2475 2726 2458 2446 2361 2393 2348 2245 2107 2180 2237 2137 2180 2213 2104 1924 1924 1979 2019 1877 1788 1811 1819 1789 1713 1654 1670 1747 1635 1642 1534 1634 1552 1598 1477 1531 1355 1456 1428 1238 1304 1399 1319 1342 1311 1251 1315 1248 1119 1129 1142 1153 1157 1091 1100 1052 1074 982 930 964 998 938 964 873 892 923 836 817 864 844 871 891 821 778 762 857 739 779 749 783 749 679 693 763 644 733 663 628 663 661 671 640 585 546 569 651 516 562 486 536 531 553 538 597 546 515 584 544 546 448 482 582 446 531 567 517 490 530 487 505 381 401 436 449 457 450 409 460 470 420 414 348 395 375 370 370 302 354 406 349 364 320 366 367 252 327 369 279 238 324 276 326 299 291 299 285 292 355 309 324 310 401 316 319 338 354 267 341 320 347 363 366 359 357 263 317 299 311 398 313 334 282 300 273 306 331 320 325 233 261 220 325 329 280 296 267 252 227 322 310 246 265 228 211 181 163 229 190 232 217 179 208 208 195 222 197 212 157 156 213 180 175 228 233 167 174 248 179 167 152 185 214 209 179 181 234 192 169 146 190 178 182 231 194 165 193 185 182 178 157 194 211 232 192 142 195 228 187 213 173 152 170 185 163 132 164 142 102 126 117 161 149 154 166 158 166 163 179 148 102 114 129 124 170 161 153 113 174 195 134 136 93 144 84 153 141 106 111 101 89 124 87 128 73 107 101 125 122 83 88 105 88 79 102 86 87 90 103 79 78 60 102 118 86 86 121 111 83 116 74 89 118 107 95 107 82 91 93 102 76 111 143 81 84 57 88 118 105 72 124 111 136 124 92 106 106 121 96 90 112 136 105 151 125 89 123 99 93 104 94 86 101 115 114 100 139 88 90 138 144 98 94 121 103 73 83 80 92 114 100 99 77 92 80 81 83 65 83 111 109 93 91 96 64 80 125 73 107 90 119 107 94 71 94 105 106 115 112 133 99 99 85 107 117 75 125 143 110 94 119 108 108 129 102 104 98 109 123 103 112 89 80 100 94 113 112 105 125 76 88 103 84 80 61 92 81 65 84 77 111 91 103 96 111 123 79 132 97 102 78 105 93 90 105 116 73 97 115 79 69 59 70 71 67 100 87 80 73 67 72 82 72 81 45 88 61 82 84 94 53 56 40 43 63 65 51 40 51 54 45 48 33 33 54 66 21 32 41 26 44 32 47 43 28 27 41 22 26 32 51 59 41 53 42 23 29 42 33 35 29 46 47 24 48 44 26 28 19 26 27 28 26 26 8 7 32 9 42 19 25 15 21 20 36 21 40 33 20 33 20 23 13 27 28 28 25 17 14 40 23 7 39 31 23 23 18 20 28 28 18 32 15 34 31 21 25 19 12 19 27 18 52 40 23 35 26 19 9 41 20 27 25 34 29 39 39 35 23 19 22 18 25 18 20 24 18 15 15 31 21 28 25 14 8 8 16 21 12 19 5 18 27 27 25 12 18 22 14 19 22 21 45 16 28 10 1 22 17 13 10 29 26 8 11 22 21 35 23 14 28 18 27 36 15 30 25 22 29 20 18 10 42 43 13 22 22 37 20 16 8 11 12 11 11 10 13 7 26 22 21 19 27 12 28 21 24 11 11 12 25 16 14 7 28 18 21 16 17 9 12 31 11 21 19 8 21 17 14 10 7 17 22 27 4 3 21 15 28 6 7 9 13 20 6 8 10 13 21 4 23 2 12 3 10 8 7 17 10 17 7 6 20 9 7 5 7 5 2 10 14 7 2 0 7 4 5 8 8 6 9 18 5 8 11 6 14 22 10 20 5 15 9 5 5 30 9 8 10 15 8 14 5 6 10 5 13 10 7 14 24 13 11 11 8 7 7 12 7 9 11 8 8 22 1 24 6 13 8 15 34 22 18 18 19 11 11 12 21 4 6 14 11 8 10 6 0 6 6 4 5 10 6 8 7 23 7 2 3 17 7 19 12 4 4 7 13 7 16 16 11 8 6 14 6 6 3 8 9 14 5 6 5 6 15 1 10 8 9 4 9 17 6 20 12 4 6 1 9 16 5 7 19 7 25 4 25 13 10 6 8 17 7 5 5 9 6 11 10 12 6 10 11 6 17 3 3 8 10 7 9 5 16 11 9 7 5 16 15 11 7 11 8 4 8 18 21 9 5 15 7 3 17 10 2 10 9 16 4 4 4 7 9 2 2 2 2 4 5 8 9 1 24 7 7 3 1 2 3 2 1 4 3 3 9 6 10 6 12 3 11 2 7 3 2 4 10 10 6 9 2 0 1 1 3 12 2 8 5 8 8 4 1 5 0 4 6 8 11 6 4 3 3 8 4 2 5 5 6 2 1 1 8 0 3 6 3 0 8 3 4 1 3 0 0 1 4 0 4 3 2 5 3 1 0 2 0 2 3 1 3 4 0 2 1 9 1 7 1 2 9 8 1 0 3 0 2 7 2 4 8 6 4 0 1 3 1 0 5 0 5 3 0 0 4 2 0 5 1 0 0 2 2 1 1 2 2 8 0 10 8 0 8 7 5 6 2 5 3 0 19 0 12 2 5 3 4 5 4 4 1 6 0 9 1 0 7 3 6 0 2 1 2 0 5 8 1 6 9 6 2 7 4 3 2 7 9 2 1 3 3 4 6 1 1 1 6 1 1 0 7 0 1 1 0 0 2 0 1 4 3 8 1 3 1 1 1 1 6 0 1 2 3 1 5 5 5 11 5 6 4 2 0 0 0 6 4 1 6 2 3 0 1 2 1 1 1 0 2 0 2 2 0 1 4 0 0 0 4 2 2 0 0 0 0 4 3 4 4 2 3 0 3 0 7 7 0 2 1 3 1 0 0 0 0 0 0 0 1 0 2 0 2 0 2 1 0 3 0 1 0 1 0 3 1 0 2 0 0 1 5 2 3 0 4 5 4 4 4 0 0 0 4 6 0 15 7 1 2 0 2 0 3 3 0 1 1 1 5 9 0 1 0 4 0 1 2 3 4 1 1 1 0 0 4 1 0 0 2 1 0 7 0 0 1 0 0 5 6 1 3 6 5 0 0 0 5 0 6 3 2 2 2 0 1 8 0 0 0 7 8 3 2 3 0 0 3 1 3 0 3 4 2 0 1 0 1 0 1 0 2 0 0 1 1 0 0 0 0 4 0 1 7 0 5 0 4 2 0 1 0 2 5 3 3 2 0 0 0 1 1 2 2 0 0 0 0 0 0 2 0 0 2 0 2 0 0 0 0 2 2 0 6 2 4 0 1 0 0 2 1 3 0 0 11 1 0 2 1 0 0 0 1 0 0 0 0 1 5 0 0 0 1 4 4 1 1 3 4 3 0 6 0 1 1 0 0 0 0 5 0 0 0 9 0 2 0 1 3 0 4 0 1 0 0 4 0 1 0 0 0 6 3 0 2 3 2 0 1 0 1 0 0 0 0 2 4 1 0 0 0 0 0 0 0 0 0 0 3 0 1 0 3 0 1 2 0 0 0 0 0 2 0 1 0 6 0 0 1 0 0 7 0 0 0 0 1 2 0 
];
B = [
0 0 0
 205968 49808 156160
 89104 20534 68570
 298768 77234 221534
 113385 26974 86411
 109534 26565 82969
 143818 34833 108985
 202876 51134 151742
 94804 21886 72918
 302146 79359 222787
 108051 26161 81890
 110034 25997 84037
 142775 35113 107662
 233265 58246 175019
 102249 23945 78304
 356826 94186 262640
 158001 37151 120850
 182729 41867 140862
 216783 51539 165244
 361628 85705 275923
 303672 69049 234623
 466412 119300 347112
 454523 105442 349081
 359814 85260 274554
 572275 135004 437271
 920282 225002 695280
 50260 11843 38417
 2000401 509814 1490587
 42267 11295 30972
 47601 11886 35715
 64958 17151 47807
 132829 35607 97222
 23926 6002 17924
 444524 121845 322679
 32507 8418 24089
 37407 9347 28060
 52508 13834 38674
 110729 30011 80718
 3903 831 3072
 495892 138651 357241
 8 5 3
 132 45 87
 1094 231 863
 11385 2364 9021
 1290 283 1007
 1372 265 1107
 3247 632 2615
 7094 1562 5532
 785785 216238 569547
 136 40 96
 1608 403 1205
 1409 320 1089
 2736 646 2090
 8737 1998 6739
 802397 222500 579897
 2388 604 1784
 2484 617 1867
 837 306 531
 39578 9352 30226
 29828 7245 22583
 39078734 13512583 25566151
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
17 188 9 136
13 49 1 21
54 54 1 32
262 46 4 15
219 68 14 18
447 97 235 27
959 114 659 98
1402 144 887 269
2882 230 1295 568
4276 365 2012 1046
12178 518 2637 1602
42692 698 4036 2687
129566 1012 5860 4089
342610 1841 8468 6640
663939 2966 11684 9945
1008368 4504 16588 14789
1148136 7119 22061 21106
1069831 10529 29358 28374
845551 15651 38282 37720
475566 22682 49231 48543
221405 31947 58849 59712
103614 43613 71475 72894
96096 58500 84040 84352
109818 75602 97177 98550
124748 93547 110698 111025
137620 112546 126293 126670
151887 130477 140386 139986
164808 144865 154500 155001
174264 155875 163560 163617
177426 162612 170589 170282
174023 163009 167795 169435
167872 159185 162715 163513
157164 151130 153816 154540
144846 140185 142613 141828
132792 130371 130747 131093
119503 117711 117674 117807
106059 104003 105425 105421
92123 91125 91906 91006
78948 76499 77348 78547
63955 64823 64392 64225
50949 51095 51352 51111
38073 38252 38877 38530
27155 26667 27475 27658
17836 18254 18103 18288
10624 11283 11215 10797
6124 5838 5859 5994
2978 2773 2689 2995
1126 1080 996 1095
397 386 358 455
57 90 85 104
7 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
