A = [
2259026 2103388 30423201 1548265 1537638 1463755 1380731 1516879 1330487 1245976 1265324 1127144 1140462 1142313 1138420 1144853 1153620 1171192 1174440 1158452 1145964 1153486 1142767 1127419 1138291 1508838 1509100 1528519 1888691 1783124 1804517 1804636 1704358 1729270 1726547 1719367 1713591 1694693 1685722 1673884 1664499 1667870 1655990 1648817 1656860 1637123 1618380 1642957 1620177 1610209 1609645 1570056 1575693 1566644 1541799 1518240 1519603 1529639 1496638 1481560 1488840 1474298 1463829 1445655 1434198 1431492 1411574 1396012 1388514 1370304 1358610 1353437 1339064 1329790 1325108 1312172 1295381 1285212 1264570 1250592 1238117 1229069 1210145 1197141 1192197 1170934 1150363 1124629 1104732 1095406 1082167 1065130 1057721 1044352 1032148 1022208 1010301 1000973 988935 977024 967376 958478 944395 933481 925225 914010 902193 892288 885545 874361 863262 856857 850295 839416 831089 822629 835924 831243 820267 835536 833131 825164 818877 813240 806200 796715 788378 780084 768856 761486 751060 742149 732444 724763 716479 707619 699332 690104 681810 672579 666660 658222 649705 641011 634110 625178 618666 609481 602754 594833 584585 579766 571776 563111 555613 549584 541176 533951 527648 519598 513424 505232 498261 492545 486164 478146 472312 466480 461300 454096 446872 441641 435845 430556 426177 419509 411210 407437 401934 396836 390845 385389 379663 376218 370046 365430 359206 355905 351591 346941 341579 336024 331624 326986 321890 318623 313753 309778 303543 300314 297166 291738 287955 285002 279293 276529 272536 268919 263934 260044 256372 252002 248611 245433 242480 238380 234431 231314 228136 225134 222557 218691 215679 212520 209376 205505 201950 198434 195293 192134 187985 185465 183233 179508 176968 173394 171332 169025 166120 163470 161650 158216 156823 153755 151847 149638 147012 144442 142481 139747 138133 136265 134081 131252 129290 127464 125731 123697 121898 119730 116865 115503 114381 112220 111263 108744 106539 104445 103712 101644 100438 98494 97002 95791 93849 92095 91071 89297 87878 86675 85284 84171 83211 81409 80018 78863 77434 76349 74987 73323 72400 70720 70872 68642 68217 66858 65329 64961 64137 62383 61647 60782 59719 58779 57460 56597 55961 55098 54067 53327 52680 51559 50500 49434 48935 48104 47419 46931 45881 45001 44708 43769 43106 42387 41545 40951 40318 39539 38915 38310 37584 37569 36415 36026 35078 34455 34169 33299 32623 32700 32412 31475 30866 30500 29900 29476 28869 28490 27749 27485 27121 26416 25660 25729 25375 24708 24651 23864 23769 23341 22825 22658 22091 21901 21053 21160 20752 20495 19892 19611 19335 19057 18628 18555 18076 17883 17451 17281 16913 16407 16619 16055 15956 15471 15233 15040 14977 14693 14181 14105 13917 13561 13170 13293 13112 12671 12764 12400 12215 11943 11891 11591 11423 11400 11096 10983 10653 10273 10449 10233 9866 9909 9657 9366 9401 9079 8999 8892 8775 8562 8581 8435 8196 8092 7888 7814 7765 7666 7398 7314 7245 6889 7034 6781 6693 6601 6454 6392 6204 6132 5994 5996 5842 5869 5708 5705 5523 5463 5473 5203 5068 5065 5011 4951 4854 4752 4707 4544 4567 4397 4436 4370 4215 4146 4165 4008 4097 4001 3844 3801 3712 3643 3660 3662 3521 3549 3444 3448 3310 3310 3207 3193 3157 3206 2956 3020 2926 2881 2782 2865 2817 2704 2752 2703 2670 2595 2552 2515 2509 2466 2443 2320 2321 2301 2291 2246 2143 2113 2095 2129 2061 1977 2031 2013 1890 1942 1995 1827 1781 1841 1729 1785 1726 1736 1733 1628 1681 1615 1537 1651 1608 1609 1484 1460 1523 1458 1415 1475 1425 1446 1331 1321 1324 1253 1256 1307 1290 1271 1239 1235 1176 1172 1196 1118 1165 1140 1109 1112 1059 1074 986 1027 1050 994 922 995 991 994 996 941 935 890 862 906 902 919 877 902 842 890 864 809 820 835 759 819 757 800 737 724 701 710 698 727 717 707 764 719 723 678 706 652 676 674 660 663 653 634 637 588 593 617 556 604 594 590 582 572 559 544 546 565 544 559 571 546 496 500 520 493 465 532 500 527 502 486 499 470 469 443 484 466 460 490 472 410 489 471 468 461 481 430 407 460 427 407 451 444 422 385 420 413 390 386 424 382 438 401 357 369 409 354 376 385 388 363 354 357 362 352 334 375 366 305 369 336 331 318 325 334 368 346 355 331 321 319 297 321 300 303 279 291 307 280 315 291 322 283 287 270 254 288 308 298 292 289 265 280 265 280 243 273 276 271 261 254 293 254 264 283 254 249 254 262 258 234 275 251 261 244 266 243 232 259 251 262 250 240 246 263 247 254 218 252 257 223 265 240 226 210 237 196 236 255 218 230 211 205 222 214 214 211 212 202 208 215 176 223 186 207 200 196 197 212 208 202 203 176 196 203 168 216 197 195 197 204 192 178 192 206 187 183 171 174 186 193 200 175 164 159 165 175 173 180 175 181 157 163 180 138 161 178 174 164 159 180 183 156 170 180 178 170 120 142 174 145 158 143 140 148 122 156 147 148 137 115 134 145 146 151 148 141 137 167 126 144 152 122 129 120 130 138 120 139 119 131 120 123 118 120 139 133 117 117 135 101 122 115 137 123 134 137 131 109 124 114 125 124 123 112 124 109 123 89 103 106 119 114 117 101 118 100 110 120 113 105 126 101 96 117 115 121 107 94 101 99 97 97 132 91 96 112 98 83 100 118 123 103 117 97 84 104 90 96 105 106 102 105 96 94 91 87 94 105 93 85 103 113 85 102 79 120 89 89 98 95 89 84 98 101 82 88 107 95 79 105 88 65 87 64 91 80 79 104 77 88 79 107 98 89 91 69 70 80 74 78 75 93 79 83 74 66 69 73 78 75 75 81 77 59 83 58 75 72 70 76 88 56 60 72 68 84 83 43 74 72 57 82 58 65 57 64 68 76 75 71 72 73 55 74 71 67 70 72 81 49 59 72 63 60 62 68 66 67 70 68 57 83 55 63 61 59 73 114 107 151 142 172 122 147 192 205 189 182 214 147 124 100 113 115 100 107 93 87 84 102 81 94 89 93 84 88 87 104 99 99 103 94 101 92 84 94 93 95 86 98 83 97 81 83 89 89 94 101 102 124 121 113 111 114 92 98 108 121 86 248 144 102 103 102 82 98 84 85 71 78 62 64 73 69 69 53 61 60 75 54 72 56 65 58 48 61 47 62 43 52 55 61 61 51 54 61 51 70 71 75 104 117 113 192 196 187 182 175 196 143 180 143 120 114 113 126 116 120 71 93 87 88 66 43 40 48 56 64 195 32 32 49 35 38 52 38 37 43 22 35 24 29 52 35 34 33 33 33 41 46 34 30 33 35 36 43 24 38 20 47 40 56 37 39 45 33 29 44 33 36 44 34 41 38 31 25 34 43 65 38 40 40 47 44 50 42 47 46 45 50 39 47 58 37 32 40 40 45 48 63 51 44 41 42 45 43 45 44 36 53 33 36 51 39 40 54 50 51 50 43 47 43 73 55 51 51 41 56 49 61 53 54 40 50 46 58 44 43 49 35 56 63 52 42 43 62 48 50 48 51 55 47 56 58 52 67 63 63 56 57 47 43 36 47 39 60 65 42 44 41 42 33 18 40 43 29 25 31 40 50 30 54 69 47 43 35 15 19 22 23 27 22 37 19 29 26 27 21 25 17 27 16 41 33 40 32 36 15 24 24 30 28 34 36 32 30 26 25 35 26 32 30 25 25 24 46 28 31 20 23 23 26 23 22 20 31 30 33 31 21 37 24 36 34 39 38 44 32 56 50 38 44 48 28 21 19 23 12 17 21 22 19 50 27 17 23 17 19 20 13 16 21 16 19 14 15 19 12 16 20 13 18 9 21 13 16 14 18 18 24 16 17 14 15 26 10 11 21 9 9 15 12 19 12 19 19 12 9 15 13 10 10 7 18 15 16 13 11 16 16 15 7 12 19 11 9 13 12 17 13 28 19 19 25 37 19 22 14 15 11 14 15 19 18 15 22 10 8 8 10 7 9 12 11 9 6 11 6 12 17 11 8 14 15 12 9 11 12 12 10 10 20 5 11 10 7 5 12 11 13 11 9 14 10 10 11 17 13 7 9 12 10 10 16 11 9 6 11 10 14 13 11 16 11 13 7 11 6 12 10 8 10 7 10 13 8 11 8 12 11 15 15 11 10 8 19 18 12 17 17 7 12 11 12 16 13 17 9 14 12 14 7 11 8 10 19 17 7 12 15 8 16 7 13 23 11 13 10 6 9 13 10 8 14 13 9 12 12 12 11 12 7 8 8 6 11 10 13 14 13 15 10 11 9 16 12 16 8 8 9 8 5 11 5 8 4 5 7 4 10 6 5 8 5 8 2 9 6 7 3 6 6 10 2 1 3 7 6 6 4 11 9 8 8 8 6 7 3 5 5 7 4 3 7 6 6 7 5 6 7 0 0 3 7 4 5 6 4 3 5 6 6 1 6 3 5 3 9 3 4 5 4 3 5 2 5 2 3 7 2 4 6 6 3 3 7 7 4 5 2 2 2 7 5 5 6 3 6 4 5 7 2 4 4 3 6 5 6 9 6 3 3 6 4 7 2 5 6 5 3 6 4 2 7 3 4 4 6 5 5 4 4 4 8 4 2 4 5 6 1 5 2 1 4 9 6 5 3 3 4 3 2 1 0 6 4 5 3 5 4 4 3 5 5 6 4 3 4 2 1 1 5 2 3 1 2 3 2 4 2 1 1 3 4 3 4 3 3 3 3 1 4 1 8 4 4 4 3 3 4 4 6 2 4 6 5 6 2 5 6 6 6 4 5 7 2 2 4 2 4 4 2 5 4 1 4 5 4 3 6 4 4 2 4 7 4 2 2 5 6 7 4 2 6 4 5 6 1 5 5 1 7 4 6 5 3 5 2 3 4 7 1 5 3 3 1 2 4 5 1 4 6 1 4 4 3 8 4 8 3 8 7 6 3 5 11 6 4 6 2 3 3 2 2 2 3 5 4 5 4 3 0 4 2 4 10 8 5 1 4 1 2 2 3 3 1 0 1 2 1 1 1 1 3 2 5 5 3 0 1 7 3 1 2 2 1 2 2 2 2 2 6 3 3 3 6 4 3 1 0 0 2 2 4 
];
B = [
0 0 0
 1156077 867659 288418
 811919 620785 191134
 1300739 1014498 286241
 1141536 884816 256720
 660230 508438 151792
 1413966 1128788 285178
 765097 599967 165130
 1132942 912971 219971
 1308373 1052334 256039
 742633 606541 136092
 1860749 1512879 347870
 1045331 851469 193862
 427847 346106 81741
 1030582 853622 176960
 751345 624326 127019
 311054 254690 56364
 1123333 935632 187701
 468303 389068 79235
 211488 171942 39546
 216101 181121 34980
 164063 134537 29526
 157285 129148 28137
 1677564 1396670 280894
 691571 574970 116601
 326107 271645 54462
 1702426 1421571 280855
 795490 664963 130527
 289612 240543 49069
 2406919 2009008 397911
 968855 813438 155417
 412447 348881 63566
 1858750 1569163 289587
 944479 804534 139945
 2197253 1865236 332017
 849930 736461 113469
 1271968 1092659 179309
 3804281 3267452 536829
 1118642 972742 145900
 2205615 1915700 289915
 3800401 3272963 527438
 1411891 1229511 182380
 2597634 2255573 342061
 2958339 2553184 405155
 1030447 896268 134179
 2847136 2482753 364383
 3385794 2934369 451425
 1203301 1037135 166166
 3014905 2658457 356448
 6428172 5617789 810383
 330756 283218 47538
 5689554 5040775 648779
 9438092 8324457 1113635
 733999 631088 102911
 161709 136351 25358
 15218281 13515680 1702601
 217488 180723 36765
 154521 131111 23410
 220485 182902 37583
 130096 111699 18397
 29826746 27557796 2268950
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
193 376 2 1
18 45 0 0
41 102 1 0
44 90 1 3
36 71 5 0
61 93 819 43
653 126 2301 196
9363 142 2784 484
65373 181 3506 685
314967 210 4751 1239
739481 271 5393 1877
1697486 432 7041 2628
3447711 619 8601 3926
6400876 1139 11611 6143
9488412 2101 12944 8522
11471148 3653 15889 12692
10668179 6049 20495 18557
7957578 9035 27862 26795
4689625 13936 37851 37357
2013585 20174 49344 49637
611542 29649 60967 61190
173596 41917 74154 74316
99040 59065 88350 88166
105916 79858 104072 104451
122897 104183 121500 122054
141465 129919 141278 142646
161809 157135 163198 162902
183585 182516 185090 186490
205901 208875 208943 208930
228185 232883 230617 230693
248114 254419 250526 251735
264651 272140 267720 268261
277730 286967 282326 282623
286764 296874 292408 291766
294256 302979 297561 298408
298096 305420 300452 300855
296559 304875 300741 301123
298496 303220 299075 300562
297008 302381 298553 299497
298500 301523 299342 300000
301783 304482 301695 303775
306901 309790 307361 308821
316128 317893 316919 318282
327751 329583 327073 330150
343711 344868 343790 344451
360937 362665 361830 362859
379997 380840 380794 380001
395917 398255 397726 397863
409995 412838 410713 413627
421687 422412 422257 421521
424797 426531 425991 425444
420490 423372 422056 423254
409061 411725 411040 412547
394565 396023 395459 395333
370990 373731 372599 374164
345402 346298 344999 346339
313282 314667 315554 314754
283104 284505 283427 283541
252089 253839 253139 253072
225213 226498 226439 226643
202932 204188 202854 203247
180368 181136 181379 181664
166031 166263 166298 166602
156442 157450 157484 157514
150905 151864 151023 151080
148750 148776 148792 149366
154898 155642 154905 155392
180674 179101 179514 179624
165183 165559 165976 165558
173306 173416 172664 173533
163202 164188 162918 163827
146261 145940 145888 146596
153306 154089 154141 153934
104453 104660 104723 104543
87088 87184 87863 87304
70404 70607 69768 70619
57077 57087 57105 56946
49012 48877 49088 48605
41137 41599 40732 41012
32246 32943 32983 32978
20998 21025 20846 20856
10620 10584 10675 10648
558 530 546 576
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
