A = [
1466397 1575959 25229575 749833 442380 450009 372289 275630 257653 199420 190854 184258 181341 177710 173562 173512 170567 171255 171891 168127 168148 168684 166483 165046 165957 193445 194140 198580 224608 225550 232070 233609 232659 234931 236272 236469 234372 234396 233278 231091 228971 232451 229853 229261 230460 227207 225209 229439 226583 224254 226276 222806 223953 223143 220770 219482 218669 219740 216542 215398 218147 215828 215424 215894 213987 215348 214443 212560 210997 209220 208943 208357 207135 206052 204329 203197 201833 201297 199789 197466 197147 196447 194732 192750 192469 190822 189108 186323 184833 183441 181994 180934 181058 178502 177804 177107 174943 175190 172698 172743 172248 171217 169933 169340 168100 167811 166313 164736 163884 162197 161571 160236 159709 159725 157751 157219 155579 155788 154745 153509 152078 151950 151006 149999 149282 148003 146743 146581 144597 143647 142339 141145 141091 140290 139103 138441 137282 136367 136127 134049 133158 133990 132403 131578 130137 128988 128077 127853 125714 125551 124075 123095 121808 121059 120256 119329 118522 116526 116231 115387 114298 113518 112001 111840 110983 109463 109141 108046 107494 105616 105202 104046 102854 102394 100605 99893 99234 98708 97799 96205 96006 94611 93740 93133 92767 91754 91180 90301 88769 89714 87249 86216 85710 84878 84659 83834 82072 80561 80308 80065 78921 78658 77873 76699 75573 75450 73841 74533 73130 71756 71293 70818 70361 69081 68628 67313 66498 65728 65318 64784 63223 63078 61876 61484 60013 59373 58632 58612 57966 56960 56235 55935 55843 54868 53844 53438 52615 52121 52111 51272 51109 50229 50042 48789 48388 47545 46567 45868 45973 44953 44208 43577 43199 41951 41960 41453 40841 40060 39342 39017 38614 37571 37183 36920 36595 35923 35453 34918 34646 33785 33362 32919 32443 32413 31929 30932 31077 30218 30205 29845 29609 28823 28587 27804 27572 27025 26773 26165 26202 25503 25066 25268 24559 24200 23448 23299 22641 22542 21894 21304 21521 20763 20364 19884 19867 19010 18963 18582 18454 18316 17902 17606 17544 17329 16924 16419 16172 15713 15618 15462 15237 14899 14654 14461 14220 13917 13796 13701 13451 13078 12810 12671 12712 12639 12529 12442 12155 11683 11592 11590 11340 11071 11130 10901 10704 10539 10286 10565 9935 9972 9787 9698 9304 9283 9044 8822 8799 8563 8314 8382 8034 8040 7932 7694 7590 7462 7362 7138 7117 6814 6905 6812 6724 6668 6401 6509 6264 6163 6015 5849 5879 5638 5640 5536 5333 5137 5269 5061 5101 4963 4650 4870 4735 4674 4456 4317 4387 4094 4196 4207 4232 4054 4001 3778 3830 3573 3399 3571 3426 3278 3347 3293 3161 3121 3079 2910 3034 2906 2884 2763 2758 2846 2563 2665 2584 2636 2536 2370 2387 2310 2288 2294 2292 2105 2154 1975 1976 1957 2076 1937 1891 1829 1822 1903 1809 1783 1667 1641 1668 1685 1622 1597 1723 1694 1717 1605 1524 1557 1553 1443 1502 1330 1372 1383 1422 1313 1394 1307 1261 1235 1171 1229 1137 1163 1133 1167 1138 1158 1162 1077 972 1084 992 953 1017 952 1011 940 865 901 882 891 901 842 786 854 792 782 812 793 689 712 677 707 663 671 666 641 669 684 695 599 612 602 585 629 564 568 530 562 582 549 569 557 510 541 501 465 488 479 474 528 466 444 439 468 445 467 442 449 459 470 413 415 381 398 386 419 376 366 410 329 355 451 365 380 375 346 321 348 375 357 393 326 310 340 324 352 340 320 286 273 279 306 306 257 324 313 286 337 280 272 300 276 254 291 274 227 248 268 244 225 247 245 251 216 254 204 224 203 213 193 225 242 205 223 241 231 210 207 210 186 229 220 190 258 182 211 206 216 188 201 206 200 158 190 232 212 226 176 200 203 206 174 185 167 187 165 210 187 157 177 151 166 164 190 183 152 174 195 151 170 202 152 175 164 173 144 142 174 156 142 145 179 149 146 168 151 137 127 148 156 147 144 262 170 143 134 139 139 124 134 139 130 119 127 159 143 139 115 142 114 131 121 131 116 127 100 122 135 141 115 129 131 120 120 115 138 115 149 131 125 120 112 116 111 106 114 117 117 97 115 97 115 104 113 105 113 114 120 108 113 92 107 106 117 88 115 112 109 107 103 84 94 109 110 97 108 107 112 121 86 104 115 94 88 100 75 82 88 124 82 91 99 81 87 78 71 80 86 79 86 69 99 98 121 81 78 99 88 84 88 78 85 83 104 92 101 81 85 78 89 80 97 112 81 91 50 76 100 84 95 73 68 64 80 89 81 83 93 83 63 87 103 84 80 68 79 78 91 90 81 77 106 81 89 75 72 82 87 68 77 77 51 88 61 53 91 67 66 71 58 63 68 48 51 64 56 48 34 69 74 59 81 59 84 77 62 61 65 36 53 53 82 67 40 52 66 68 59 57 57 63 44 54 60 55 66 45 56 58 54 41 46 66 67 55 65 45 55 51 57 60 50 41 53 53 57 48 42 49 39 38 63 63 54 74 47 49 39 44 60 67 61 52 52 49 45 50 38 40 43 51 51 52 48 50 50 46 46 42 36 47 52 70 67 57 48 54 46 38 64 41 48 44 51 41 43 43 40 52 58 61 44 62 41 56 74 54 45 46 56 47 35 44 47 57 43 31 39 31 41 34 38 55 38 38 40 44 51 59 52 33 45 47 38 40 42 39 42 44 36 32 33 34 30 41 28 41 41 34 27 40 41 43 32 41 41 26 33 33 28 39 29 24 31 35 20 33 41 24 29 24 30 30 35 29 47 29 26 45 20 29 32 43 25 29 27 30 39 32 22 36 36 30 32 28 35 24 20 14 23 24 28 21 27 22 30 30 19 18 38 40 30 26 41 21 22 25 15 22 25 15 24 10 21 19 33 18 20 25 35 29 28 23 23 31 37 37 18 24 30 27 29 16 25 19 27 28 19 26 25 24 24 8 11 15 26 18 15 18 23 23 19 26 12 22 13 13 32 11 17 16 24 20 16 23 26 22 21 17 22 19 12 19 15 23 16 19 34 19 17 24 22 12 13 14 25 13 12 16 13 15 24 23 22 14 10 18 19 13 17 23 14 12 12 16 10 14 26 27 17 30 22 18 30 20 8 26 13 11 26 15 14 13 21 15 13 13 13 18 9 17 9 22 13 18 18 19 11 21 19 14 14 14 16 17 19 18 21 14 13 13 15 6 15 23 9 13 18 7 10 10 14 17 8 16 11 21 12 17 19 16 13 10 7 16 27 12 10 20 14 22 6 13 14 11 11 11 11 15 12 15 17 6 18 7 10 17 13 4 12 12 11 11 12 20 10 15 16 10 11 6 18 12 6 10 8 21 10 11 21 17 11 8 11 4 9 7 20 11 16 8 14 10 13 9 16 24 12 17 7 6 12 9 10 4 20 10 6 4 9 12 7 6 17 6 8 14 12 11 9 7 9 8 9 6 7 8 11 8 8 11 11 6 12 8 8 6 10 9 12 10 3 5 5 6 13 7 3 12 7 5 12 6 9 3 6 10 7 6 7 8 13 4 5 14 4 6 14 7 4 6 4 1 7 9 8 9 12 5 7 7 9 7 5 5 7 2 5 10 2 3 5 9 4 5 6 6 4 8 5 5 8 13 10 9 11 9 4 5 5 9 9 2 6 6 2 1 2 8 7 2 8 9 4 5 4 7 5 2 5 3 3 8 3 7 1 8 6 4 4 1 4 1 7 5 7 4 9 2 8 3 4 2 5 8 1 7 5 7 9 7 2 11 4 3 6 5 2 3 5 4 2 11 3 4 2 3 7 1 3 5 2 5 3 1 2 4 2 6 5 8 5 3 4 1 5 2 4 5 2 5 5 4 2 3 6 5 5 8 4 4 8 4 0 4 3 7 4 5 5 3 5 1 7 11 2 5 1 4 5 7 5 4 8 3 8 5 5 1 4 4 8 4 0 4 4 5 8 2 3 1 0 4 2 1 3 4 4 1 1 3 4 5 2 11 0 3 1 1 3 2 2 1 1 3 6 3 1 1 2 7 3 3 2 0 4 0 4 3 1 1 2 4 3 5 1 2 2 0 4 3 1 1 5 2 2 0 2 1 1 4 5 3 1 4 2 3 3 6 1 2 3 2 5 4 2 2 0 1 1 3 2 7 7 2 3 2 5 4 2 4 5 3 2 6 0 8 3 2 2 1 1 1 4 1 2 8 0 3 6 2 3 3 4 4 2 4 6 0 2 5 3 1 2 5 3 7 0 2 3 1 4 2 5 0 1 1 0 1 4 8 1 0 4 1 4 1 0 1 2 2 6 3 0 0 1 1 2 1 1 0 0 1 0 1 1 2 10 1 2 0 1 6 1 2 4 3 0 1 2 1 2 0 4 2 3 2 3 1 0 0 0 2 7 0 2 1 0 0 2 2 2 2 6 2 5 3 0 4 2 2 2 4 0 0 0 6 0 3 2 1 3 4 2 2 1 2 1 0 6 0 0 0 0 0 0 0 5 0 3 2 0 3 0 0 1 3 0 0 2 2 5 0 3 0 1 0 1 0 2 1 0 0 1 3 0 0 5 3 2 3 2 0 0 1 0 2 0 3 3 0 1 1 1 1 2 1 2 0 1 4 1 1 5 1 0 1 2 1 1 1 0 2 2 4 1 1 3 5 1 2 2 3 0 1 2 0 1 4 0 0 1 3 3 3 2 1 1 1 5 2 0 3 0 0 1 0 10 5 0 3 0 3 8 4 3 2 0 1 1 2 4 1 3 0 1 2 2 1 0 0 1 1 0 1 1 3 1 0 2 1 1 1 2 2 0 1 2 3 1 4 0 3 5 0 1 1 1 2 0 2 0 1 2 1 2 0 0 1 2 0 0 0 0 1 0 0 0 2 3 1 1 0 2 0 4 0 1 2 0 0 1 0 3 2 1 5 0 0 1 4 3 0 0 0 1 0 1 0 5 4 0 0 0 0 2 0 0 
];
B = [
0 0 0
 313676 282005 31671
 182991 163537 19454
 361960 328604 33356
 324777 293492 31285
 210269 190627 19642
 382877 349471 33406
 374659 343553 31106
 195528 178879 16649
 510204 457313 52891
 458344 420679 37665
 80460 73565 6895
 960533 887641 72892
 213171 197439 15732
 48080 44076 4004
 465838 434792 31046
 145819 132930 12889
 18814 16813 2001
 514346 481794 32552
 17901 16310 1591
 18828 16773 2055
 3914 3519 395
 62 58 4
 4868 4625 243
 821933 768641 53292
 23968 22161 1807
 33680 31461 2219
 865417 811383 54034
 29511 27992 1519
 59086 55629 3457
 1165502 1088865 76637
 57452 54509 2943
 96361 92280 4081
 965649 912838 52811
 173998 166271 7727
 263990 254504 9486
 1293084 1228788 64296
 411823 388811 23012
 248304 238801 9503
 1635346 1561037 74309
 254297 238561 15736
 55502 52625 2877
 2341344 2241493 99851
 30334 28750 1584
 45858 43094 2764
 4201989 4041903 160086
 56208 53372 2836
 200940 189422 11518
 7113953 6863945 250008
 185243 175393 9850
 1 1 0
 12498633 12047024 451609
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
44 139 0 1
10 16 0 0
23 14 0 0
24 25 0 0
19 38 0 0
24 51 185 15
499 76 569 69
9326 43 712 158
54415 49 919 168
222062 65 1271 309
538216 72 1520 491
1207286 97 1962 640
2233418 202 2099 930
3768905 262 2572 1305
5151174 400 2822 1657
6377007 715 3224 2281
6261449 1013 3559 2888
4689589 1444 4006 3819
2452897 1984 5062 5176
785889 2789 6324 6417
137934 4030 7615 7777
17518 5343 9092 9326
11285 7322 10465 10502
12396 9610 12345 12304
14117 12307 14119 14268
16090 14914 15962 16590
17887 17744 18476 18807
20210 20704 20932 21040
22597 23552 23038 23709
24905 25701 25220 26142
26890 28270 27535 27668
28618 29994 28996 29386
30099 31079 30422 30817
31105 32434 31323 31794
31211 33370 31978 32066
31603 33561 32042 32058
30586 41985 31867 33634
30781 31740 31166 31165
29913 31047 30747 30953
30067 30161 30082 29919
29934 30732 30279 29699
29932 29739 30547 30252
30345 30976 30780 30598
31238 31667 31726 31484
32479 32556 32412 32857
33549 33632 33376 33781
34571 34355 34447 34445
34814 35265 34931 34956
35776 35892 35669 35799
35184 35729 35137 35533
34344 34784 34447 34741
33146 33729 33067 33461
31063 32111 31649 31700
29158 29691 29675 29796
27350 27345 27363 27472
24153 24946 24739 24482
21987 22928 22368 22588
20029 20484 20238 19905
18353 18483 18221 18242
16474 16519 16496 16709
15115 15749 15373 15404
14111 14565 14544 14413
13629 13288 13399 13514
12530 12838 12625 12642
12112 12049 12064 12133
11769 11838 11952 12030
11877 11673 11651 11711
15085 13663 12376 12033
12029 11785 11784 11808
11553 11553 11559 11581
11211 11190 11105 11160
10746 10581 10684 10718
10368 10339 10147 10370
9746 9547 9899 9571
8535 8578 8721 8642
7751 7749 7694 7580
6395 6403 6269 6344
4864 4648 4606 4829
3790 3710 3832 3885
2797 2828 2760 2891
1611 1629 1664 1605
997 1032 1030 951
41 63 37 63
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
