A = [
643266 631307 3825826 658015 656449 614521 611850 622211 635628 611793 650469 695810 750211 824096 937481 1020078 1045941 1093747 1113918 1064519 1023213 1000905 976621 967046 969983 1149772 1161727 1154270 1291263 1110540 1121387 1102078 924668 934771 930306 935277 920991 899394 898410 895023 899085 894996 890196 917857 915346 908054 910259 896259 911426 907917 899271 894145 909221 914688 904745 905064 885890 899238 890602 857444 855791 856991 857313 853794 850717 856999 845487 841661 839579 830543 845243 854017 861536 865265 871792 874058 868127 863710 846500 834129 826852 816826 810889 804771 803468 794315 783705 763327 752934 747791 738724 735556 733511 729135 728430 725204 718130 716320 713289 701721 696435 694383 687703 685786 683276 683491 680481 675653 670216 667740 660486 655905 653751 650627 646961 647430 646685 643922 639922 635081 630676 628182 622598 621390 618163 616792 613286 611184 606475 600982 598721 595154 589248 587687 584391 582673 578378 576218 573542 568424 566534 563071 559473 556947 551615 549933 547461 545177 542604 541068 537090 533597 530114 526377 524121 519571 517506 514887 512119 507901 506140 502625 497705 495702 492769 489229 486879 485818 481038 480906 476533 473587 470898 467047 464715 463518 461178 458024 455344 452435 450573 447602 445380 443051 440976 439788 435653 433393 432770 430778 428252 425487 423848 422988 420426 416698 416276 415090 411426 410100 406574 406022 403801 400947 399477 397021 395924 394064 391769 390500 386805 382221 380190 376060 374015 371480 367748 367634 365821 364410 362631 361614 358827 358708 354192 351683 347831 344540 342354 338248 335486 331291 328899 326590 324088 322102 319103 317023 314745 312881 310080 307722 304885 304567 300821 300063 295944 295142 292419 290619 288591 285493 284994 282688 281111 278375 275996 275260 272999 271394 267297 265847 264698 262569 260061 257952 256082 253257 251624 249639 247505 246571 244451 242395 241265 239702 236772 235405 233761 231378 229018 227403 226063 224410 222165 220613 218906 216515 215651 212334 211887 209549 207470 206347 204693 202401 200394 198774 196841 194203 192866 191251 189082 187246 185319 183983 181581 179911 177672 176847 175123 172211 170652 168813 167687 166199 164455 162847 160164 158521 156963 155490 153351 151381 149801 148159 146273 144617 143364 141258 140101 138186 136488 134969 132796 131329 129536 128238 126383 124850 123354 121016 118804 118470 116229 115058 113143 111887 110108 108584 107309 105767 103881 102600 101294 99742 98037 96550 96060 93211 92434 90829 89319 88176 86169 85058 83608 81917 80747 79493 78586 77064 75528 74520 72912 71618 70215 69296 67827 66568 65455 64472 62935 62311 61266 59941 57864 57356 56730 55592 54190 53021 52488 51004 50475 49441 48094 46993 46070 45172 44836 43307 43304 41991 41155 40261 39526 37827 37480 36625 36065 35242 34486 33527 33008 32204 31686 30893 30260 29410 29078 28064 27477 26990 26407 25752 25223 24571 23856 23450 23017 22447 21803 21253 20785 20462 20010 19622 19190 18681 18312 17522 17124 16925 16617 16124 15602 15416 15020 14898 14093 13823 13505 13151 12784 12539 12539 12138 11621 11261 11044 10795 10457 10307 10061 9812 9604 9542 9084 9003 8612 8592 8360 7977 7813 7607 7343 7342 7218 6783 6623 6618 6265 6224 6173 5800 5802 5676 5459 5346 5245 5140 5033 4744 4663 4668 4560 4469 4366 4202 3979 3983 3854 3767 3670 3721 3517 3427 3250 3336 3099 3051 2946 2933 2870 2807 2699 2735 2490 2528 2439 2453 2342 2237 2214 2121 2059 2121 1980 1972 1845 1865 1724 1765 1640 1669 1620 1619 1544 1525 1544 1457 1373 1351 1386 1372 1302 1246 1246 1164 1181 1068 1107 1113 1141 1062 997 942 1005 967 910 965 865 828 841 909 874 815 797 822 804 759 708 736 709 702 678 701 689 711 655 662 645 629 647 566 611 551 587 553 528 598 574 537 550 515 486 512 497 495 498 437 445 514 463 450 453 448 391 427 428 381 407 391 428 422 406 412 386 335 365 337 351 349 307 336 321 326 304 283 300 286 359 364 320 339 292 327 330 290 303 308 293 264 270 270 277 262 253 244 278 271 224 270 260 240 265 271 261 237 265 253 219 229 266 252 232 233 240 246 230 213 224 249 225 236 234 209 220 191 174 220 216 196 213 250 233 186 225 175 201 217 200 201 229 208 190 201 207 217 215 232 198 209 199 199 215 189 193 206 176 209 202 175 180 233 185 188 182 175 179 196 164 191 192 162 184 150 172 157 156 171 170 214 209 264 177 160 237 222 210 230 194 197 173 162 207 169 189 167 170 196 207 166 171 210 193 190 138 159 142 147 175 156 144 154 147 135 148 151 162 147 144 165 197 137 148 162 131 170 174 140 159 135 140 128 136 126 141 137 126 149 140 164 130 155 135 128 139 145 174 137 121 141 143 160 152 131 130 137 160 125 120 139 133 150 142 128 130 114 131 109 99 113 111 114 107 121 117 115 109 107 115 106 103 108 117 105 126 116 114 114 119 108 118 105 92 104 102 113 91 93 104 107 119 111 93 105 108 101 114 113 113 111 84 128 107 110 99 103 112 103 89 109 92 113 102 106 89 93 107 98 93 96 133 97 103 116 115 105 93 81 109 90 92 90 105 99 100 88 101 89 90 97 94 100 99 97 121 84 78 110 81 89 88 100 87 76 63 91 94 95 83 86 83 80 78 76 82 94 92 74 76 81 101 94 79 97 72 71 85 90 62 71 68 77 73 87 69 75 83 71 68 86 71 69 97 98 73 85 70 65 58 64 90 75 81 68 72 77 67 93 63 64 80 64 73 58 54 77 62 53 61 57 88 65 61 58 80 75 58 62 51 56 48 71 58 79 52 62 77 57 70 68 70 61 53 65 43 67 54 64 68 56 63 57 58 66 74 71 63 54 58 61 60 62 57 64 49 48 34 48 45 53 55 56 55 54 54 58 55 54 55 57 40 39 53 45 48 66 40 77 55 67 55 70 78 62 51 64 68 52 41 51 59 51 52 70 44 44 36 46 43 44 54 38 43 42 47 44 54 50 47 45 42 49 54 45 33 44 40 61 40 36 41 39 43 46 47 51 45 52 36 50 45 41 61 46 56 47 63 63 46 48 56 52 58 42 41 47 72 47 44 49 59 58 53 49 55 67 64 64 68 66 55 84 59 68 66 72 79 53 53 68 60 47 51 48 47 31 33 39 37 43 41 49 38 119 35 37 35 43 46 24 41 36 35 40 25 38 36 52 47 36 39 44 33 32 21 25 37 39 44 26 29 48 36 43 33 26 38 30 27 35 42 36 30 40 32 34 34 35 23 26 28 43 37 40 37 33 43 31 56 32 37 48 29 21 30 19 36 32 30 33 27 27 32 31 29 28 25 24 39 28 34 37 32 33 30 32 34 32 36 24 39 29 25 32 32 51 51 33 48 40 30 28 38 32 35 38 36 42 35 31 37 42 50 60 51 49 70 71 37 58 57 38 59 70 44 62 45 52 45 53 63 50 55 49 52 48 57 49 45 50 46 55 52 52 47 37 38 55 51 43 49 46 52 35 37 43 50 56 48 50 58 51 67 47 29 32 49 39 38 30 36 29 32 28 22 26 62 26 32 25 28 22 20 20 18 23 11 20 23 17 19 17 22 14 21 15 28 12 13 14 21 20 12 16 10 20 9 14 17 13 18 23 17 20 20 15 7 17 12 15 17 19 11 16 12 6 15 17 20 21 13 11 16 22 14 12 18 19 13 17 16 11 15 10 11 16 21 18 17 11 20 14 9 10 9 9 10 12 8 21 20 12 19 20 11 14 16 21 10 22 12 26 24 15 27 23 38 25 19 23 23 21 19 16 22 24 22 21 21 26 28 22 22 17 15 33 20 23 15 20 29 19 13 29 32 26 19 16 33 20 34 19 29 26 19 37 20 24 34 44 32 29 16 25 32 24 40 27 30 41 43 40 32 32 38 15 43 32 25 48 48 36 41 40 35 51 45 33 22 50 16 25 21 44 62 44 50 40 49 40 54 36 20 41 38 27 29 23 35 56 38 54 44 36 60 71 41 39 44 33 33 19 17 20 21 17 22 10 22 36 30 29 25 19 32 27 30 21 17 26 16 22 13 31 15 32 19 20 28 17 18 33 27 36 20 17 26 28 24 34 42 27 30 28 19 24 26 18 21 23 19 33 25 27 38 43 38 35 37 23 17 31 21 18 19 17 35 23 30 49 87 67 57 61 71 97 84 17 21 22 34 34 25 15 25 34 12 20 23 18 18 26 7 20 40 27 19 13 18 7 7 14 11 11 14 10 13 14 10 11 6 12 20 9 6 8 7 6 7 13 6 18 10 11 6 10 13 13 17 21 14 20 28 16 18 10 19 14 20 20 14 13 18 16 19 13 11 26 24 18 20 21 23 16 18 10 18 19 26 17 8 22 22 17 16 14 14 22 18 17 12 25 13 13 12 6 31 12 12 6 6 7 7 6 10 5 9 6 11 9 4 8 5 5 2 10 9 2 7 12 7 6 4 6 11 7 10 8 9 3 3 5 6 3 4 1 3 4 9 3 6 7 6 4 4 7 4 4 4 4 5 6 4 7 7 7 11 5 5 10 10 5 6 7 7 8 5 11 5 9 4 8 5 6 2 7 8 15 5 10 5 8 7 5 10 6 4 8 6 2 5 4 5 7 7 5 10 8 4 4 11 3 3 2 3 8 2 11 5 12 2 1 11 6 5 7 3 5 6 3 2 7 2 3 6 5 1 6 5 6 8 8 8 3 3 4 4 2 5 6 3 9 3 8 4 7 5 1 5 4 5 5 5 4 6 5 2 2 5 5 3 8 3 7 5 3 4 3 5 3 6 5 6 7 6 6 7 10 14 11 5 7 6 13 9 11 7 7 11 11 9 7 6 8 4 4 11 9 9 13 5 6 9 11 4 6 7 5 7 2 7 3 7 10 6 6 8 7 6 8 8 10 7 8 11 11 2 5 6 8 8 10 3 6 6 11 6 3 10 6 3 7 2 6 6 4 7 6 4 4 3 4 7 5 7 7 4 8 6 8 8 8 5 4 7 7 6 6 2 3 7 3 7 0 7 5 6 3 6 4 7 14 16 7 6 9 
];
B = [
0 0 0
 400804 263991 136813
 544509 373129 171380
 295341 198576 96765
 1137551 818805 318746
 405800 295394 110406
 266113 196519 69594
 327354 243955 83399
 204047 153279 50768
 157846 121023 36823
 130041 100132 29909
 253586 195495 58091
 252261 191316 60945
 177317 131746 45571
 1064100 825917 238183
 332503 255036 77467
 392704 307763 84941
 256044 201601 54443
 388855 305107 83748
 396533 313382 83151
 261086 205380 55706
 839763 666693 173070
 453124 359497 93627
 460081 365980 94101
 271008 217129 53879
 455508 364594 90914
 431801 346272 85529
 722665 580015 142650
 281665 225060 56605
 476964 381614 95350
 490171 394400 95771
 281008 227090 53918
 501371 404004 97367
 467798 374559 93239
 667255 538686 128569
 300455 243518 56937
 496184 399188 96996
 764253 625360 138893
 478005 385922 92083
 330353 269566 60787
 698432 571181 127251
 599160 485611 113549
 663565 543066 120499
 282316 230285 52031
 523366 426225 97141
 675544 552665 122879
 321355 264053 57302
 665823 545599 120224
 548155 445203 102952
 653826 535998 117828
 317724 261434 56290
 648730 532276 116454
 534726 435473 99253
 656161 537897 118264
 285250 235770 49480
 698662 574349 124313
 615768 505413 110355
 266073 219531 46542
 627773 514225 113548
 439412 356217 83195
 67313602 56858214 10455388
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
6 80 0 0
0 2 0 0
3 12 0 0
11 9 0 0
8 15 0 0
22 17 0 0
84 24 0 1
298 29 1 1
1100 28 3 0
3506 55 17 3
7393 69 574 78
14392 119 939 238
23540 200 1244 500
38867 337 1889 911
66606 737 2770 1718
152947 1466 4061 2940
580585 2902 6040 4937
2797131 5978 9189 8835
5585184 11336 16459 16613
2544594 16268 27958 28074
334096 23399 41528 41757
73320 33273 56093 55959
74450 45624 69021 69594
86044 63872 83670 83381
98370 84609 98701 98907
114440 107489 114392 115980
131805 130714 132309 133470
150397 152830 151793 152859
170130 174364 171810 172095
190173 195335 192178 192580
209304 214795 211126 211507
224988 232254 228046 228422
240671 247363 243458 244691
255241 261038 258597 258514
267936 275109 269633 271070
278652 285436 280333 281745
289917 294876 290158 292557
300066 304382 301527 301993
310467 314397 312259 311997
319970 325149 322850 322993
333226 336536 333577 334900
346612 350589 347912 348105
361545 363135 361375 364138
377672 381309 378324 378566
397027 397992 396049 398125
414978 416529 415372 416688
434882 436442 434324 434930
451646 453605 453388 453302
465480 467655 466171 468734
475960 478041 475086 479123
478948 479984 478797 479621
473990 475738 474159 476138
461143 463862 462591 464235
444669 447173 445881 446270
421423 423796 421915 423804
394189 395738 393982 394561
364291 364795 363901 365570
332209 334003 333025 334027
303381 304275 304377 304967
277957 278517 278292 278144
258634 260014 259617 259960
246752 247728 246333 247343
236519 237733 235909 236991
234144 235207 235016 235678
239199 240458 239863 239683
249827 250324 249385 250546
263893 264831 264238 264297
290698 292929 288965 288950
310160 309259 308664 310229
326947 326070 325656 327323
335440 336145 335284 335259
336238 337663 336629 337016
317383 316586 315716 318035
275905 275788 275474 276613
232338 232060 230540 232867
186459 186168 186256 186047
138834 138462 139229 140242
97029 96972 97331 96917
72016 71437 71353 71204
50270 49927 50146 50437
33308 33424 33340 33125
20474 20422 20503 20494
1715 1760 1741 1746
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
