A = [
324003 334989 1300927 357079 350268 333530 330739 332465 336205 328337 346097 378463 415459 465178 536462 587845 636021 701105 718451 721966 741054 731262 725504 729852 736809 798947 785665 768631 810025 679071 676061 653439 508853 514891 506308 500310 495295 480142 479953 471887 470156 466545 470376 470910 469009 473752 466265 464654 460438 452309 449665 450469 449832 448514 447340 444985 443786 442692 439115 437634 434263 432397 431770 429509 429036 424886 424391 422066 420603 417795 414114 411414 407615 405611 402446 401681 398825 396272 390931 388577 383919 381163 380325 375147 372207 369961 368129 364339 360126 357183 355049 351834 350049 344768 343716 341533 337049 333662 332023 329514 324597 320032 317555 315669 313709 311727 309890 306520 303216 300769 297278 294863 293019 289933 285404 284112 282356 279955 277436 274507 272621 270004 263995 263339 259373 257735 254889 254297 249765 246309 244653 241996 239585 236011 233909 230703 228785 226229 224123 221630 219027 216237 214745 214510 211668 209563 206671 205207 201432 200791 197653 195588 193352 191955 187221 185609 184646 180329 178914 176514 174478 173309 171241 168679 166473 164587 163265 161208 158249 157709 154536 153311 152430 149253 146656 144008 141898 140244 137277 136873 134201 132297 131038 127925 128083 125839 123641 123805 123585 120434 120148 116946 114662 113283 112433 110314 110175 109693 108863 105806 104223 100837 98976 98157 96419 95004 94597 91750 91187 90206 89548 87528 85788 83802 83218 82670 80943 80363 78835 77846 76732 75714 75722 73627 72442 70665 69455 69510 67270 66099 65117 64182 63940 62696 61041 60702 59344 59105 59492 57250 56561 55933 55077 54402 54433 52981 52555 51878 50714 50173 49329 49209 48801 47271 46428 45487 44574 44167 42928 42747 42432 41596 41250 40844 40484 39164 38929 38932 38027 37314 37477 37039 36654 36554 35186 34572 34701 33303 32659 32477 31568 31183 30733 30511 30435 29898 28741 28688 29140 27985 28790 27756 27076 26880 25964 26143 25012 24742 24675 24436 23537 23054 22802 22737 22466 22184 22102 21779 20987 20366 20251 20390 20359 19998 19817 19568 19372 18216 17473 17360 17233 16858 16619 16593 16775 16224 16265 15577 15578 15370 15133 15796 15719 15515 15131 14434 14668 14511 14081 14163 13957 13710 14130 13794 14434 14584 12950 12622 12623 12775 12489 12691 12165 11312 10881 10691 12798 10785 10812 10463 10476 10428 10308 11736 11292 10242 10520 10013 9854 9505 9501 9117 9043 8942 8815 9173 9022 8513 8392 8312 8163 7912 7936 7729 8238 7701 7377 7395 7660 7718 7564 7528 7494 7204 7124 7023 6180 6275 6327 6311 5989 6163 6009 5885 6008 5870 5853 5881 6206 6214 6138 6184 6142 6152 6190 5920 5911 5863 6028 5472 5321 5101 5105 4785 4813 4867 4694 4869 5165 4902 4626 4423 4440 4541 4312 4198 4420 4281 4420 4134 3870 4079 3912 3952 3747 3805 3664 3838 3656 3714 3745 3810 3945 3780 4012 4060 4025 3862 3690 3595 3879 3613 3599 3812 3542 3702 3815 3503 3460 3633 3607 3427 3411 3379 3323 3239 3033 2968 3115 2973 3088 3196 3044 3217 3110 3195 3069 3040 3016 3085 3175 3000 3007 2923 3214 2907 2939 2918 2954 2997 3056 2996 3118 2995 2962 2879 2800 2745 2722 2784 2694 2782 2772 2743 2844 3286 3306 3354 2817 3750 3763 3115 3267 3264 2971 3216 3318 3219 3229 2834 3010 3399 3053 2976 3204 3139 3041 2830 2800 3650 3014 2731 2798 3027 2944 4124 3547 5292 6314 4100 2980 2626 2698 2587 2374 2394 2225 2299 2240 2226 2162 2356 2292 2205 2154 2347 2024 2092 1976 2083 2128 2184 2030 1924 1985 2004 1930 1925 1906 1840 1848 1896 1970 2000 1944 1876 1992 1791 1777 1835 1915 1918 1934 2005 1872 1925 1909 2005 2078 1964 1994 2090 1930 1886 1909 1915 2054 2109 1911 1901 1909 1811 1826 1789 1797 2330 2412 1865 1778 1807 1644 1677 1768 1739 2035 1706 1550 1539 1558 1585 1606 1591 1592 1466 1504 1514 1538 1535 1410 1420 1501 1422 1391 1456 1414 1428 1570 1538 1576 1346 1344 1301 1201 1264 1349 1240 1272 1177 1228 1127 1173 1099 1125 1146 1066 1221 1248 1211 1253 1229 1106 1137 1125 1155 1159 1222 1243 1204 1162 1075 1201 1192 1346 1150 1438 1287 1250 1205 1174 1171 1176 1189 1231 1220 1177 1339 1292 1194 1058 1172 1217 1114 1209 1227 1133 1132 1165 1146 1242 1163 1490 1370 1487 1359 1432 1372 1417 1691 1725 1390 1413 1462 1249 1228 1332 1594 1452 1304 1298 1342 1253 1337 1208 1652 1448 1383 1724 1701 1690 1392 1205 1321 1157 1273 1226 1406 1379 1196 1128 1156 1206 989 1088 1140 1196 1133 1069 1147 1021 924 998 990 1001 1213 1302 1199 1210 1160 1129 1183 1122 1171 1232 1303 1305 1189 1722 1663 1422 1339 1138 1138 1109 1431 1252 1463 1768 1726 1264 959 1151 1204 1356 962 1157 1047 1194 1059 1020 1052 1065 1087 999 976 1027 967 1044 1070 1475 1400 1026 998 986 958 963 1044 1134 1100 1050 957 866 934 809 877 817 840 829 769 857 894 808 895 789 760 871 1131 1064 985 992 972 1028 1136 961 966 1119 1139 907 910 871 972 992 904 1144 1331 807 792 586 603 620 564 578 551 593 591 527 523 557 517 577 555 598 574 548 544 516 576 609 522 502 516 547 536 465 485 442 453 563 488 511 495 509 455 464 522 486 443 481 490 467 453 401 442 481 487 457 431 442 479 434 445 498 593 425 451 408 460 420 420 457 536 522 460 458 460 435 389 421 385 384 410 395 386 367 423 422 354 397 345 359 395 421 459 389 394 381 357 393 377 508 431 386 368 405 452 473 467 478 387 370 392 408 447 482 428 395 443 545 435 410 407 375 394 401 380 407 389 404 399 518 469 433 452 572 520 491 455 435 361 426 420 379 399 400 502 488 461 403 414 450 487 410 399 401 364 379 396 440 393 361 393 408 351 308 293 334 344 305 330 334 334 319 269 298 309 304 327 292 271 259 323 301 275 282 302 311 269 256 371 378 379 377 391 369 324 310 335 385 375 387 354 372 354 353 333 383 398 346 384 374 327 326 369 353 369 317 334 342 328 279 380 316 318 373 384 316 329 343 330 286 334 331 354 348 290 276 318 296 348 329 295 341 343 332 296 359 340 303 265 283 305 288 290 330 289 321 350 354 307 309 277 333 323 284 310 321 325 337 278 329 388 284 274 237 274 292 226 264 251 252 239 252 270 334 280 370 276 264 258 237 218 222 220 237 311 247 262 240 199 279 259 253 217 251 252 228 198 178 234 216 222 236 231 206 222 305 248 263 255 227 248 263 261 253 299 320 224 313 289 293 267 271 294 296 279 274 279 302 312 343 301 262 273 266 263 269 248 238 259 259 269 238 235 222 250 231 196 179 236 214 213 240 219 292 195 241 237 219 222 217 192 197 180 220 184 189 213 232 199 242 209 227 205 200 203 187 186 158 155 140 152 180 142 162 169 179 153 109 153 156 157 164 179 155 204 169 162 161 158 168 181 202 136 169 177 167 155 171 160 141 168 189 220 207 241 212 244 199 228 222 264 222 166 156 134 152 165 147 126 145 160 132 137 166 131 170 180 166 145 162 179 156 159 168 163 174 135 129 133 156 167 139 159 135 134 120 143 114 115 103 136 122 145 118 120 137 120 104 112 140 129 101 117 102 96 103 100 71 106 108 84 95 105 104 87 101 84 126 103 87 114 125 110 129 124 117 116 127 105 113 86 107 92 72 102 103 89 108 83 90 93 87 75 75 80 95 130 132 156 137 125 103 111 129 133 109 121 112 115 124 124 131 128 126 134 125 128 140 152 147 111 134 106 142 113 136 115 113 113 106 116 169 104 133 123 140 136 155 114 157 144 134 172 143 131 119 103 107 117 96 113 86 98 94 125 100 118 105 107 87 76 97 63 64 77 86 72 69 55 59 57 71 63 71 75 70 73 67 63 75 54 56 66 78 72 76 56 64 63 44 79 62 64 73 84 73 78 74 78 72 74 69 59 64 59 56 57 65 72 54 75 60 53 57 55 54 57 56 68 73 64 63 54 52 47 50 42 52 63 38 62 55 60 52 49 56 45 44 40 47 56 43 46 72 51 57 58 71 56 58 51 68 58 54 43 55 66 57 63 49 55 39 49 50 53 52 63 56 45 57 61 57 57 85 93 79 89 76 51 68 89 91 79 68 63 76 87 107 82 97 104 79 85 87 81 46 68 61 62 63 65 67 73 71 58 58 69 76 77 62 76 65 67 70 87 84 85 82 108 79 67 76 97 88 78 68 72 50 60 61 81 83 56 80 70 78 91 104 73 65 61 77 78 69 75 70 78 111 105 61 80 83 102 111 93 123 126 102 135 107 143 190 207 169 174 158 178 119 128 169 153 186 141 167 154 182 192 191 201 177 177 181 146 134 133 199 136 128 118 218 174 295 175 155 164 137 142 226 181 442 226 130 84 81 56 69 69 41 60 40 38 55 46 70 46 65 79 53 54 50 58 48 54 53 59 48 49 74 45 55 57 64 61 90 77 103 70 76 68 53 82 61 62 62 72 60 69 62 56 64 61 39 73 78 62 55 52 50 45 46 66 59 60 77 72 90 53 58 40 48 78 61 67 56 45 52 26 35 39 35 47 43 40 34 32 51 35 37 41 23 41 30 26 40 38 29 36 32 42 27 41 35 30 25 33 28 26 26 24 13 29 26 22 54 36 19 17 32 45 30 28 26 31 35 31 16 30 29 22 35 35 31 22 31 19 31 35 28 23 25 29 27 31 26 28 32 30 29 27 34 32 37 23 33 24 39 24 22 22 28 29 31 21 21 20 28 30 29 17 23 25 24 32 22 44 28 25 32 32 22 30 19 29 33 28 35 28 34 25 16 32 26 30 33 23 26 33 25 28 26 19 27 29 34 25 36 33 21 22 23 25 24 24 31 23 15 31 36 23 31 36 27 37 36 39 39 26 29 36 30 27 25 32 19 29 17 34 32 35 24 35 25 29 22 23 32 29 21 31 20 27 31 27 27 17 15 36 33 23 27 28 29 19 20 24 42 26 23 15 27 34 24 23 35 30 23 26 31 25 28 18 41 29 32 31 24 30 21 32 16 21 28 19 29 32 25 24 25 26 24 27 29 24 22 22 23 16 38 40 31 35 23 33 26 31 16 26 30 32 21 29 
];
B = [
0 0 0
 287569 126094 161475
 315796 145184 170612
 323823 137124 186699
 493985 209322 284663
 289820 124202 165618
 1102469 490890 611579
 490168 218019 272149
 336935 170337 166598
 334385 165998 168387
 164515 81177 83338
 123764 58201 65563
 87479 42843 44636
 72909 38829 34080
 147763 75241 72522
 128886 62095 66791
 108850 48769 60081
 313073 141580 171493
 212210 90363 121847
 196098 89995 106103
 152547 73790 78757
 172567 83780 88787
 168883 83022 85861
 126733 61967 64766
 160121 77568 82553
 120347 57731 62616
 232229 108676 123553
 188766 87757 101009
 141044 66448 74596
 181223 85930 95293
 139420 66622 72798
 185816 90655 95161
 178587 88850 89737
 159649 78359 81290
 215780 105147 110633
 184199 92276 91923
 219780 111321 108459
 408891 180978 227913
 205994 103556 102438
 232058 115638 116420
 388309 169991 218318
 229323 114435 114888
 381692 172439 209253
 218327 110719 107608
 243325 124013 119312
 383921 171629 212292
 255690 129112 126578
 382048 173147 208901
 255961 130220 125741
 407915 189493 218422
 242276 123426 118850
 447338 207382 239956
 238213 124913 113300
 436714 202884 233830
 222213 115901 106312
 470611 222269 248342
 460015 219025 240990
 242452 130381 112071
 462111 220864 241247
 207440 116117 91323
 22438435 12114825 10323610
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
55 38 1 1
14 11 0 0
49 23 0 2
95 32 1 5
92 34 1 6
164 42 0 8
458 78 7 15
1852 107 19 24
13491 168 55 31
123078 248 80 42
402826 306 79 46
839763 476 110 89
1288449 694 191 116
1833721 1185 415 210
2274313 2331 966 360
2524158 4624 1825 653
2276266 8462 2444 1370
1579129 13137 2754 2387
761029 17962 3403 3173
229999 23512 3131 3433
46789 28152 4539 3627
15099 33715 5924 4432
11124 36739 5459 4353
9229 32175 7615 6840
8393 29952 7676 14705
9577 29637 5768 9430
16402 14564 4861 4740
10254 10713 4604 4449
6623 12750 4703 4722
5521 7659 6855 5151
5684 7458 5075 5267
9207 9580 5283 5528
6794 7026 5307 5283
14171 15181 5836 5760
7922 7689 6231 6809
8032 7403 6688 6709
8471 8363 7225 7293
9138 8631 8239 7941
9170 9347 8981 9605
9764 9661 9486 9317
10924 11195 10820 10302
12325 12099 11922 11972
13159 13356 14206 13345
15239 15581 15231 15442
17103 19133 16741 17605
21002 21530 21080 25407
23089 22602 26778 22694
26185 26648 24498 24750
27418 27272 28715 27733
32243 30398 30495 29669
34630 33530 34394 33977
35746 36550 37296 36348
42654 49257 38453 45510
42190 41227 42769 42769
49289 47421 54767 51259
47319 51854 50324 46726
47623 51439 57098 48254
59231 57767 56233 52571
58486 52069 53481 51635
60866 54520 55207 61193
72480 70870 60324 68181
64467 58071 58606 60193
62409 58170 58550 60424
56919 54353 47188 52170
42896 43984 49630 36625
29331 36568 24370 34921
38084 40893 23364 30197
29017 42607 35421 37608
32179 29915 30898 24806
17961 18256 30784 14484
14019 12929 14303 17079
17681 14498 12864 11184
664 644 1143 500
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
