A = [
256730 252866 1208919 248893 240428 232693 236708 236962 240362 237829 256285 279589 306192 348240 390551 424076 448005 459988 463073 455223 441630 437284 431718 430345 431399 505771 505945 501237 564266 486705 488645 480534 408752 415196 404820 406343 400447 391489 392559 387143 390761 389878 389044 392383 388623 386361 385678 382221 379977 377711 377319 374557 376701 374618 374189 374530 372720 369785 368388 364746 363786 362903 361534 362074 360415 360018 358390 355716 354002 351446 349150 348329 346828 345155 345174 343825 341145 340479 336766 334881 332935 330093 328741 328222 326932 326296 323919 321709 320526 318079 316273 314351 313328 312168 310487 309476 307893 308892 306845 306849 305411 304285 303648 301019 300744 299151 298716 297146 295850 291680 289607 289408 287465 285095 283191 281577 280294 279675 277831 275606 275237 273280 270753 269043 267542 266624 264479 263243 261625 260429 258687 257711 254182 253339 251475 250312 249043 247993 247353 245281 243376 241343 238357 237266 236191 234875 233223 232001 231150 229161 228359 226476 225594 224135 222808 220288 219647 218122 216524 214863 213193 212530 210623 208725 207862 206037 204452 202909 201994 201220 199955 198032 196292 195055 193583 192295 190130 189403 187422 186108 185408 183489 182304 181100 180403 178767 178041 176266 173878 174025 172682 171609 169833 168986 166064 165335 163282 161917 160873 159685 158356 156570 156203 155074 153830 152364 150709 149880 148383 147006 145799 143733 143426 142115 141228 140136 137709 137377 135776 133873 132732 132024 131409 129696 128452 127744 126270 124601 123631 122238 120883 118974 118924 117671 116312 115020 113748 112632 111108 110489 108908 107443 105864 105517 103966 103680 101992 100840 99906 97604 97428 95465 94964 93643 91827 91154 89882 89041 88290 86706 85433 83595 83313 82272 81164 80210 79650 77706 76734 75949 74971 73930 72338 72072 70411 69620 68648 68059 67099 66137 64987 64433 63428 62418 61558 60359 60384 58610 57381 57282 55836 55051 54386 53597 52687 51867 50802 50526 49360 48704 47449 46805 46650 45188 44579 44072 43070 42457 41359 41291 40477 39500 39095 38478 37656 37217 35991 35758 35076 34603 34182 33202 32805 32154 31688 31000 30609 29896 29666 28989 28547 27726 27339 26945 26583 26177 25459 24717 24384 23996 23704 23275 22983 22185 22014 21650 21342 20512 20382 20034 19491 19272 18954 18476 18251 18087 17500 17198 17185 16969 16213 15915 15636 15319 14945 14832 14608 14194 13950 13597 13589 13324 13101 12922 12569 12340 12078 11960 11525 11545 11055 10930 10799 10583 10654 10278 10164 10116 9722 9722 9435 9207 9184 9189 9058 8764 8510 8447 8303 8208 8053 7891 7657 7562 7349 7214 7099 7003 6888 6787 6735 6582 6469 6457 6386 6186 6142 5948 6047 5929 5746 5623 5467 5395 5348 5341 5122 5194 5129 5109 5097 5078 4858 4755 4753 4671 4594 4586 4536 4443 4454 4412 4258 4245 4237 4042 4035 4004 3944 3991 3883 3903 3759 3726 3675 3639 3573 3551 3551 3594 3465 3384 3402 3317 3299 3347 3310 3195 3228 3144 3104 3042 2990 3121 3003 3041 2898 3048 2900 2934 2897 2872 2828 2864 2719 2690 2722 2687 2609 2569 2622 2609 2535 2573 2568 2526 2506 2497 2581 2381 2441 2245 2359 2454 2453 2330 2271 2251 2300 2271 2268 2229 2232 2173 2206 2153 2111 2112 2203 2084 2104 1984 2035 2087 2016 2031 2006 1993 1995 1994 1834 1905 1886 1926 1875 1848 1861 1832 1878 1839 1794 1876 1731 1827 1748 1727 1737 1722 1704 1684 1691 1709 1697 1704 1646 1645 1619 1651 1643 1588 1652 1616 1581 1624 1538 1547 1604 1531 1544 1565 1554 1545 1527 1498 1493 1426 1438 1387 1391 1469 1435 1423 1461 1365 1339 1381 1366 1369 1337 1458 1376 1369 1396 1386 1400 1384 1294 1271 1300 1217 1266 1222 1255 1336 1226 1262 1244 1259 1216 1096 1124 1250 1167 1171 1202 1161 1183 1179 1200 1140 1170 1135 1110 1175 1123 1115 1092 1152 1091 1097 1133 1073 1106 1102 1068 1081 1084 1097 1123 1051 966 1090 1028 1048 1091 1031 1024 1016 1008 1073 1013 1060 1037 1007 1032 973 1001 959 940 1013 1021 982 904 936 875 870 933 856 918 906 934 862 901 914 830 911 866 841 855 820 853 886 839 831 821 804 804 869 807 788 799 805 738 832 767 783 716 774 777 746 745 799 744 758 733 699 756 718 681 779 725 745 709 713 759 692 688 720 690 744 709 769 680 710 687 705 649 635 643 718 679 672 636 641 656 680 678 606 631 640 627 631 681 634 600 604 631 650 583 607 600 625 597 651 571 613 584 584 600 567 586 576 567 566 586 581 605 582 546 545 527 541 552 520 530 553 573 495 513 507 506 543 565 515 558 520 485 493 507 536 516 546 483 534 495 500 499 488 528 485 546 512 509 522 470 519 532 490 519 556 631 576 637 553 596 554 524 474 437 447 416 410 433 415 490 427 487 469 430 407 448 427 394 409 432 418 409 399 419 424 401 376 393 403 408 402 433 432 417 380 371 341 371 348 401 374 382 384 388 373 364 335 391 376 350 341 362 370 382 358 361 347 336 337 343 323 334 346 347 395 441 506 471 454 427 424 388 369 348 375 370 381 338 378 353 318 361 301 339 357 334 348 348 337 323 334 326 318 307 342 363 335 307 308 304 302 286 326 306 305 316 302 282 298 297 278 329 322 304 318 320 291 300 268 281 306 309 313 286 277 253 285 251 255 274 273 263 253 261 288 281 281 276 232 227 264 221 263 213 245 262 261 236 262 257 243 225 255 249 235 237 218 236 250 250 258 232 241 256 221 252 242 222 225 246 251 224 237 252 233 253 250 229 252 236 236 250 248 242 221 241 253 237 266 231 226 237 239 240 237 222 245 224 279 238 238 221 224 219 226 224 206 240 240 256 257 237 258 218 225 243 245 270 242 259 254 272 238 265 208 236 239 256 247 269 273 291 248 246 201 253 235 256 249 235 233 239 206 239 212 198 188 220 186 185 203 189 203 178 192 195 187 191 182 183 168 134 140 175 186 182 159 159 150 146 135 124 130 131 138 151 122 113 122 105 132 132 110 116 125 117 111 144 102 123 117 105 139 105 133 119 107 137 119 117 118 110 120 102 118 135 125 113 120 120 119 124 111 101 98 111 95 105 114 115 114 108 122 108 109 116 102 123 118 95 119 115 101 111 77 97 93 93 85 85 105 103 86 85 92 103 105 104 89 89 79 85 104 82 101 73 109 85 85 80 93 85 80 89 104 103 71 82 70 78 101 90 87 83 86 91 90 86 61 99 93 76 87 72 94 87 90 73 71 86 67 80 70 68 77 70 68 80 89 79 88 85 80 79 84 67 60 63 69 67 76 61 63 77 65 68 48 79 79 75 64 66 61 60 68 65 67 72 59 61 75 61 68 61 75 63 64 55 61 60 80 61 70 64 62 68 58 69 61 61 53 47 73 59 66 56 63 57 65 66 81 56 50 64 49 57 70 58 53 62 54 53 68 60 64 45 51 50 53 42 52 55 48 55 48 53 45 42 53 50 60 48 49 42 47 59 71 59 47 58 53 49 51 53 43 45 54 46 51 52 54 42 34 46 45 52 51 37 50 47 40 50 42 43 45 44 43 38 48 47 45 42 31 39 48 58 37 46 46 46 45 51 31 39 27 48 49 33 40 42 40 46 31 31 46 30 38 37 46 46 41 38 25 29 32 31 28 38 31 37 43 34 28 35 39 41 31 35 40 38 41 38 36 48 37 33 25 34 38 33 26 34 32 32 33 38 26 24 30 36 30 31 38 28 31 36 27 21 33 27 28 30 32 24 38 34 26 32 35 24 32 23 33 38 24 32 24 39 32 21 30 31 26 26 29 34 24 31 23 28 32 25 27 25 16 31 38 31 27 20 32 24 23 27 27 31 17 20 16 27 27 21 30 24 24 16 24 25 15 24 25 25 22 31 26 26 23 24 25 19 23 31 16 24 20 35 23 25 19 28 29 18 16 25 22 21 18 22 26 21 24 24 20 20 19 19 24 27 12 26 22 15 28 24 32 20 26 19 17 24 22 25 18 16 30 20 23 13 25 23 14 18 13 12 17 20 22 22 14 12 22 17 24 18 18 18 14 21 13 26 16 16 17 15 14 17 6 22 10 23 24 12 15 14 11 17 14 21 16 24 18 14 11 10 20 10 18 9 18 12 14 7 16 24 21 10 13 8 18 15 18 17 16 12 17 15 10 20 15 19 14 10 14 21 15 21 10 10 17 16 19 9 16 15 12 19 18 17 14 16 11 14 12 9 11 7 12 8 12 15 16 12 11 17 15 16 12 13 18 11 16 12 16 13 16 7 16 9 7 12 11 17 7 12 14 16 12 11 10 12 13 12 15 7 12 11 9 8 8 12 13 9 14 9 12 5 9 3 6 7 14 8 9 12 13 9 9 9 15 6 7 10 11 11 14 8 10 5 9 5 6 12 4 8 8 12 5 8 12 8 8 14 8 7 8 9 11 9 7 13 8 11 8 10 5 8 11 8 6 2 12 4 8 3 4 12 5 10 7 6 6 10 9 12 12 7 6 7 8 4 4 5 10 4 4 6 10 5 9 5 8 2 8 4 5 6 6 10 8 8 10 5 4 7 5 5 6 5 9 7 7 3 7 6 7 5 6 8 9 7 9 11 14 4 6 5 5 6 10 6 5 4 7 4 4 12 7 2 4 3 7 8 7 1 7 4 7 4 4 5 5 4 7 6 8 2 1 4 4 5 4 8 4 4 4 1 3 10 5 5 1 6 6 11 6 3 5 6 6 2 4 8 1 3 6 6 4 4 2 5 3 2 4 5 2 2 4 4 5 4 0 2 2 4 6 6 3 3 3 7 6 4 8 2 4 5 2 4 4 6 8 7 5 1 3 3 2 4 4 3 4 6 9 4 7 5 6 6 3 1 2 3 2 5 2 4 7 6 3 4 7 6 2 1 2 2 3 3 3 4 4 2 5 3 3 3 4 3 3 4 1 2 3 6 3 0 6 2 1 2 3 3 5 3 3 2 1 2 0 3 3 1 6 7 1 3 4 7 1 2 6 5 3 1 4 6 4 1 2 4 3 2 7 5 1 
];
B = [
0 0 0
 243679 133746 109933
 186619 106318 80301
 287499 179086 108413
 219552 141497 78055
 142888 90316 52572
 259364 189231 70133
 117739 81680 36059
 114086 84579 29507
 94189 67318 26871
 127971 94853 33118
 158613 117991 40622
 107311 78302 29009
 95247 71381 23866
 122106 95740 26366
 99720 76977 22743
 133920 105996 27924
 152586 121440 31146
 265604 218532 47072
 130729 104448 26281
 151992 124547 27445
 113906 93056 20850
 174954 145529 29425
 160641 133703 26938
 109367 90102 19265
 160750 134409 26341
 118087 98035 20052
 222039 187253 34786
 133120 111101 22019
 175284 147355 27929
 131347 109965 21382
 177239 149377 27862
 180211 152254 27957
 146223 122929 23294
 198254 167637 30617
 150156 126544 23612
 219647 186123 33524
 307892 259336 48556
 193662 164202 29460
 194087 164355 29732
 324701 274920 49781
 231414 196856 34558
 276194 234156 42038
 203584 173538 30046
 197311 167720 29591
 340394 289413 50981
 204278 174464 29814
 325537 277322 48215
 220772 188368 32404
 327502 279484 48018
 257571 220284 37287
 303820 259328 44492
 279953 240584 39369
 314489 269169 45320
 278006 238589 39417
 329330 282514 46816
 371824 319402 52422
 224979 193760 31219
 370733 319061 51672
 238331 204271 34060
 25069113 21623310 3445803
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
4 20 7 2
0 6 0 1
1 9 0 0
4 13 1 0
5 12 2 0
4 13 0 1
23 26 12 4
133 42 61 8
1773 36 112 32
8413 66 244 80
17985 75 303 151
34783 113 523 263
64193 174 926 550
128748 255 1474 1067
270998 456 2217 1774
683364 828 3489 3109
1593637 1614 5228 5143
2128131 2874 8359 8070
1205450 5105 12816 12683
287366 7938 17454 17485
67217 11487 22630 22787
43977 16591 28774 28390
42388 24000 34875 35380
47358 33036 42399 42956
55081 43420 50749 50835
64932 54561 60256 60546
74724 65736 70268 70374
84533 76601 80869 81531
94568 86938 90577 90396
102848 96182 98695 98914
109824 103281 105778 106255
114322 108185 110042 110189
119044 111157 112825 113471
117620 114165 114984 115432
117920 115949 116157 116529
118475 115926 116920 116746
118224 117301 117753 117690
119884 117466 118002 118841
120542 119668 120134 120206
122615 121446 122045 122221
125422 124106 124979 124408
128161 127791 128322 128443
133122 132827 132423 132542
138166 137691 137662 137727
143634 143301 142766 142960
148277 148214 148152 147970
154184 152926 153147 153120
156940 157062 157043 157932
159904 160481 159705 160254
160499 160000 159913 160296
159581 158801 158604 158922
155324 155859 156321 156177
150099 149986 150161 150411
142943 142946 142104 143315
134649 134694 133685 134810
124456 124349 123783 124540
114021 114523 113818 114851
105051 104813 104506 105171
94214 94695 95117 94833
86976 86948 86679 86751
79137 79699 79200 79720
74187 74249 74482 74261
70374 70560 70529 70415
67597 67469 67507 67143
67938 67518 67578 67990
71287 71002 71029 71308
75644 75876 75800 75633
81649 81926 81420 82073
90697 90926 91218 91248
101576 101919 101939 102127
116563 116805 116092 115809
124474 124075 123682 124517
132671 131635 131777 131659
136614 136993 135993 137068
134089 134440 134626 135032
121567 121835 121551 121451
100780 101898 100845 101423
69646 69630 69791 69676
35820 35760 35876 35614
12553 12611 12673 12623
1947 1904 1907 1950
12 10 13 13
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
