A = [
409499 411640 2482830 132918 131556 125134 123000 127027 134250 141597 182802 215288 234769 287152 325597 332875 329941 327765 322793 317355 310302 302409 295829 294844 307018 405852 419463 445621 540011 484337 496824 490303 441101 457453 448446 450851 445429 431999 429548 423125 422201 419280 419699 424570 422050 423382 411685 407170 399239 386737 381930 379843 382194 380794 380911 383058 380170 377966 377951 373147 369057 370609 369352 367360 367770 366113 363764 365256 360711 357101 355736 349860 347775 347281 344269 342212 342170 339352 335999 334810 331549 325481 325961 323848 319012 318701 317269 313514 312362 307894 304740 302292 297268 293891 294276 291506 287605 287211 282984 277801 276948 273345 269494 266446 264290 260952 259051 257318 254373 252986 248651 244904 242443 238647 235745 234083 230402 227999 226163 222949 222139 220731 215434 213412 210438 206588 206326 203098 200018 198494 196114 194298 191552 188598 184841 182522 181470 179856 177351 176144 173350 170693 169693 167347 164378 162862 160004 157295 156806 154287 152857 152063 149015 147512 145424 143128 141757 139532 138134 136117 135245 132860 131183 130237 128472 125577 124901 122949 121303 120430 118370 116595 115447 114299 112470 112102 108957 107962 105981 104320 102922 102265 101529 99597 98805 96912 95362 94296 92517 90976 90604 89297 87739 88397 85864 83879 83251 82432 81320 79749 79859 78205 77296 76428 74241 74255 72956 71072 71292 69599 68621 68570 66822 66228 65801 64548 63376 62032 61639 60686 59861 58912 58765 57696 56664 56228 55521 54095 52983 53260 51690 51601 50726 50487 50023 48755 48495 48109 47104 46464 45385 45198 44155 43700 43450 42652 42324 41936 40986 40194 40155 39271 38724 38264 37611 37462 36967 36100 35879 35047 34393 33749 33654 33601 32547 32389 31654 31402 31361 30540 29947 29411 29809 28675 28306 27887 27407 27352 27083 26298 26209 25987 25001 24884 24583 24312 23772 23397 23135 22856 22559 21911 21862 21418 21167 20713 20595 20182 19718 19732 19336 19178 18655 18390 18306 18134 17897 17503 17204 16886 17030 16619 16060 16075 15714 15656 15250 15283 14998 14885 14825 14426 14156 13825 13547 13195 13244 12973 13076 12901 12554 12346 12209 12293 12051 11680 11456 11380 11430 10966 10716 10665 10643 10637 10153 10227 10231 9693 9711 9819 9731 9535 9185 9056 8854 8952 8671 8490 8360 8093 7955 8099 8210 7945 7865 7510 7531 7450 7123 7416 7188 7291 6836 6824 6847 6703 6699 6492 6337 6287 6220 6230 6192 6066 5916 5788 5863 5645 5921 5628 5578 5403 5382 5387 5233 5278 5143 5293 5149 5202 4873 4766 4651 4744 4569 4444 4379 4429 4362 4483 4200 4236 4094 4047 4243 3991 3813 3824 3791 3813 3974 3754 3628 3597 3561 3478 3506 3436 3522 3385 3509 3354 3238 3253 3303 3148 3165 3178 3159 3067 3013 2969 3062 2990 2903 2815 2797 2765 2802 2697 2744 2726 2621 2721 2714 2631 2459 2492 2559 2588 2408 2406 2411 2405 2369 2477 2550 2330 2240 2271 2331 2389 2260 2241 2229 2234 2489 2083 2238 2182 2052 2033 2144 2140 2156 2016 1997 1972 1955 1889 1859 1925 1930 2002 1807 1908 1810 1951 1813 1842 1759 1820 1793 1797 1596 1665 1712 1807 1605 1613 1579 1601 1570 1599 1582 1613 1600 1667 1586 1505 1514 1619 1540 1497 1540 1432 1438 1420 1520 1445 1414 1437 1521 1488 1430 1380 1330 1365 1336 1326 1255 1347 1243 1216 1315 1285 1237 1325 1385 1294 1284 1272 1348 1284 1257 1233 1235 1219 1341 1236 1240 1221 1245 1252 1212 1120 1143 1178 1286 1166 1110 1152 1183 1211 1200 1194 1182 1194 1109 1150 1127 1122 1080 1185 1105 1152 1124 1130 1027 1069 1114 1202 1178 1086 1144 1038 1166 1079 1074 1146 1122 1102 1107 1053 1070 1108 1105 1109 1013 1047 1017 1010 1162 1050 994 941 956 1020 1008 985 969 912 957 908 948 951 939 881 917 980 898 854 993 917 915 885 803 892 842 867 869 829 819 847 818 947 839 809 805 801 748 803 770 721 812 716 785 809 786 690 739 740 766 816 781 686 805 736 755 709 687 728 785 700 719 710 727 662 714 783 793 712 671 741 769 735 660 739 686 695 673 808 697 699 713 753 680 723 733 725 692 690 723 729 636 674 669 649 687 738 697 680 696 697 655 753 668 687 633 700 724 651 683 709 696 686 729 681 656 749 683 639 685 680 667 644 894 658 618 689 616 646 708 636 700 670 700 660 631 653 667 661 638 681 637 757 669 628 681 656 672 673 647 697 672 665 680 606 661 652 621 601 574 613 630 616 615 649 547 539 567 550 539 543 535 517 541 683 516 568 638 611 519 565 531 609 542 494 550 634 519 550 570 544 537 559 564 535 545 511 510 503 519 545 516 571 608 544 544 496 560 534 471 471 502 501 496 468 487 464 503 505 480 481 524 572 578 582 548 501 458 472 492 531 541 476 521 496 471 500 520 493 686 493 471 465 494 501 495 476 503 469 487 610 479 517 522 473 455 499 461 498 483 460 483 474 446 441 439 455 524 410 410 508 425 448 429 474 461 413 439 431 430 445 425 419 628 423 437 473 444 400 438 466 428 415 455 403 459 425 415 418 442 430 458 457 496 436 438 423 457 481 451 484 482 454 499 462 453 463 511 463 469 407 470 448 450 437 423 421 479 445 439 459 417 445 431 404 415 498 540 428 433 495 443 412 431 396 416 405 393 471 448 469 426 419 469 424 418 464 450 437 458 394 377 443 408 406 472 452 351 403 391 430 426 425 370 422 385 368 369 403 397 374 374 370 404 373 381 392 411 402 364 368 388 364 381 609 438 358 387 346 324 321 305 291 293 328 308 344 270 260 286 343 361 276 292 284 308 295 239 249 290 247 261 239 253 252 272 228 259 262 269 269 244 226 284 281 251 261 231 256 250 265 228 253 265 456 263 311 235 231 277 276 264 247 243 247 264 260 240 265 280 298 287 284 244 261 262 242 279 289 271 267 288 395 426 257 302 367 315 355 305 375 178 310 324 308 300 317 346 270 304 300 288 271 289 299 309 276 288 286 287 285 314 271 278 280 239 230 261 212 225 257 235 251 200 223 244 211 254 239 236 231 230 237 219 234 249 229 222 210 153 168 149 147 126 143 163 150 158 144 136 172 158 148 149 122 133 162 144 159 159 179 142 166 169 164 162 139 144 176 135 141 135 143 136 153 167 146 133 152 136 140 149 135 136 157 134 155 125 139 179 147 120 157 113 139 117 114 117 116 119 152 131 129 128 134 125 118 124 134 139 128 131 124 106 115 122 122 109 120 126 97 111 120 123 141 117 112 122 147 122 115 108 86 104 127 120 94 107 112 92 111 109 100 103 112 118 104 96 210 110 113 126 108 159 122 128 101 127 109 120 106 116 89 105 128 114 99 112 118 115 98 107 115 122 130 122 108 99 104 113 130 114 121 108 120 130 122 119 97 117 141 130 137 136 139 144 144 129 137 138 145 135 152 129 122 131 129 117 141 125 130 110 103 132 116 127 147 123 131 111 116 90 107 116 115 126 95 106 127 98 89 83 177 77 79 76 81 98 93 82 79 94 73 71 77 71 86 95 100 62 90 93 87 88 89 74 113 98 87 73 86 92 92 96 128 100 102 92 100 97 66 89 93 103 84 84 98 80 103 48 83 82 78 81 56 89 76 81 65 87 75 95 106 90 89 83 78 83 86 105 68 76 73 51 62 63 77 68 72 49 72 50 46 53 60 55 59 68 66 57 62 67 55 50 69 52 53 60 54 57 42 94 58 61 73 33 34 61 50 51 56 51 56 51 58 52 66 72 46 55 39 45 45 49 35 58 53 53 43 49 69 60 41 46 39 53 52 50 48 40 56 50 47 47 35 52 57 46 46 43 54 58 51 56 55 50 40 42 47 49 40 43 60 46 52 42 49 52 34 42 44 32 32 41 34 42 30 37 36 33 50 33 30 43 36 33 35 30 36 25 24 16 24 33 30 37 76 35 43 40 28 33 31 32 41 25 37 22 28 26 27 31 35 29 32 34 34 25 41 30 47 34 36 48 43 47 24 48 47 21 57 26 35 37 31 35 28 18 33 24 30 45 30 38 25 23 23 30 28 29 20 30 42 29 27 36 33 35 36 34 31 25 33 27 31 39 35 36 24 28 27 25 33 17 31 34 34 28 31 36 24 29 38 38 42 41 41 47 32 50 43 32 31 40 44 35 94 34 42 42 31 27 30 25 30 35 31 24 23 19 26 29 24 29 22 19 20 25 25 16 21 23 30 12 20 27 21 24 27 23 27 31 22 28 21 34 27 28 30 31 30 27 38 25 26 34 39 28 27 29 31 44 44 47 40 41 48 51 50 47 49 44 36 45 57 42 60 60 55 52 50 44 57 56 62 56 66 72 61 57 54 66 70 41 65 53 46 45 40 45 47 36 53 56 43 36 25 35 27 37 36 41 32 31 40 44 28 37 28 25 45 35 27 36 42 44 45 26 27 33 18 21 18 24 18 30 19 25 24 29 15 16 20 18 17 19 17 26 17 30 23 15 14 13 39 31 22 22 24 21 17 22 38 36 26 23 22 28 23 32 22 23 34 21 26 23 32 30 33 30 27 27 27 28 17 28 25 11 14 24 23 21 15 17 32 24 24 14 22 19 14 25 21 14 8 15 23 26 27 18 30 19 20 17 8 16 15 15 14 14 15 17 19 22 14 12 14 7 19 16 16 12 14 12 11 11 12 10 12 11 12 8 2 4 11 9 8 13 21 13 10 8 11 14 7 7 14 9 14 15 11 11 7 9 9 11 16 11 15 8 15 9 9 17 24 15 31 18 17 15 20 25 21 28 14 21 22 32 31 16 32 22 19 17 23 21 23 25 18 22 22 17 22 12 23 18 12 15 13 19 13 14 14 15 14 3 9 13 6 11 7 7 7 8 9 15 5 12 7 7 13 9 8 8 7 8 7 12 6 11 5 6 6 3 4 3 2 10 7 8 2 6 8 6 10 6 1 7 6 13 5 14 4 4 4 7 10 15 7 12 9 12 8 9 12 5 9 
];
B = [
0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 57409 17958 39451
 57559 17135 40424
 50259 16605 33654
 58919 19959 38960
 44906 14507 30399
 50452 16990 33462
 47965 15261 32704
 39215 13223 25992
 60413 20333 40080
 50409 17473 32936
 44033 16172 27861
 63855 21261 42594
 41395 15711 25684
 102975 34818 68157
 55734 21548 34186
 37043 14800 22243
 51551 19271 32280
 56008 23527 32481
 59726 22483 37243
 65842 27592 38250
 44781 18026 26755
 47474 19204 28270
 72644 30564 42080
 45661 18576 27085
 91392 40982 50410
 66980 27194 39786
 93572 36911 56661
 51356 24951 26405
 72067 30028 42039
 142141 71091 71050
 28846611 17212036 11634575
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 35 1 0
0 9 0 0
2 16 1 0
8 16 1 0
4 18 3 0
6 23 4 1
7 26 17 5
73 31 78 12
540 45 362 68
9748 57 483 126
77566 98 535 239
282475 123 662 340
556305 204 915 537
825409 293 1127 881
955011 500 1593 1301
991010 789 2199 1953
870384 1215 2888 2719
639849 1808 3864 3678
358895 2701 5133 5137
122004 3699 6506 6557
23966 5044 8360 8349
11148 7124 10172 10260
12586 9750 12215 11959
14992 12203 14656 14513
17966 15297 17223 17097
20445 18870 20215 20337
24253 23283 23604 23940
28042 27559 27954 27894
32346 32097 31868 32037
37329 37151 37291 37556
41981 41735 42042 42341
47774 47380 47423 47334
53029 53153 53231 52994
59301 59531 59101 59310
64632 65435 65613 65001
70595 71177 70984 70954
76702 77427 76949 76868
82685 82510 82091 82433
87697 88329 88431 88484
93170 93787 93065 93716
97315 98173 97812 98031
101441 102013 101800 101159
105293 106474 105988 105551
108789 108984 109412 109141
112665 112956 112469 112996
116301 116285 116069 116281
118618 119230 119185 118738
120375 120822 121216 121230
118979 120074 119181 120238
118621 118117 117067 118450
114170 114549 114233 113901
111381 111473 111512 111223
108600 108005 108828 108731
105148 103827 103839 104223
100935 100430 99850 100425
94757 95229 95436 95454
89917 90112 89506 90012
80410 80571 80615 80599
70490 71226 70582 70702
59157 59392 59366 59650
49401 50438 49949 50306
33889 33514 33675 33808
14807 14896 14987 15201
3308 3193 3254 3281
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
