A = [
143873 142324 677303 140156 135341 131831 133523 134658 137785 136580 148002 161335 177209 200609 226626 244130 258536 265174 267610 262465 254509 252156 248347 248383 248140 290072 289710 286647 321893 276888 277539 272663 230156 234427 229560 230373 227939 220854 223168 218677 221986 221513 221282 223388 220769 219680 218623 217469 216624 216035 215276 213509 215060 213198 213162 212719 211258 210440 209363 207297 207389 207144 206445 206329 205710 205108 203515 203346 201808 200735 198990 198999 197957 196676 197814 196243 195342 194191 193206 191492 189791 188053 187621 186696 187125 186352 185233 183665 182227 181748 180450 178853 179180 178273 177553 176067 175439 176085 174703 173871 174151 174500 173775 171700 171993 170298 170396 170838 170045 167067 165815 165118 164885 163003 162055 160530 160333 159105 158645 157264 156672 155207 155159 153017 152289 152228 150829 150505 148393 148443 147836 146975 144875 144228 143218 142916 142416 140447 141039 139693 137978 137818 135958 135662 134499 133493 133064 132126 131609 130668 130060 129089 128100 126438 127128 125931 124474 123534 122430 121540 121003 119949 119580 118221 118276 117027 115603 114513 114788 114144 112558 111566 111939 110967 108644 108247 107121 107195 105091 105006 104857 104343 102506 101093 101347 100274 100490 99274 98517 99203 97584 97240 96673 95184 93530 92553 91448 90026 89642 89178 88084 86829 86917 85643 85273 84345 83582 82561 81510 81720 80486 78868 79074 78609 77826 76821 75672 75333 74294 73381 72200 72767 71699 71044 70691 70297 68535 68002 67037 66774 65841 64720 64503 64159 62560 61977 61301 60664 60121 59473 58514 57697 56607 56791 55575 55375 54301 53440 52773 52404 51994 50814 50142 49943 48939 48220 47506 48012 47299 46083 45092 43931 44088 43618 42965 42795 41752 41252 40686 39608 39513 38333 37706 37575 36521 36121 35682 35179 34946 34016 33542 33037 32557 31785 31202 30434 30772 30006 28950 29339 28248 27911 27520 26715 26586 26088 25465 25446 24403 24701 23831 23255 23069 22334 22269 22013 21414 20671 20391 20297 19783 19575 18960 18793 18391 18303 17395 17267 17023 16796 16518 15833 15848 15125 14974 14989 14859 14496 13959 13996 13693 13317 12834 12915 12582 12220 11830 11492 11356 11091 10961 10814 10544 10283 10101 10032 9776 9602 9361 9216 9112 8880 8611 8706 8304 8335 7982 7640 7807 7803 7401 7257 7228 6993 6770 6759 6736 6388 6254 6201 6240 5954 6130 5729 5650 5628 5580 5564 5169 5279 5034 4939 4902 4957 4953 4722 4524 4552 4536 4421 4258 4353 4366 4281 4384 4515 4308 4193 3921 4117 3862 4029 3660 3565 3446 3284 3072 3232 3141 2967 3044 2998 2965 2881 2863 2773 2849 2651 2752 2633 2709 2565 2452 2428 2401 2430 2259 2323 2379 2269 2375 2323 2208 2126 2149 2207 2155 2082 2132 1991 2002 2006 1922 1919 1970 1941 1905 1871 1825 1847 1834 1728 1678 1675 1645 1667 1695 1650 1564 1658 1611 1644 1701 1587 1630 1613 1681 1636 1586 1537 1580 1448 1450 1503 1574 1477 1433 1548 1364 1411 1467 1357 1299 1394 1354 1300 1304 1308 1227 1333 1281 1312 1188 1308 1262 1264 1229 1241 1233 1137 1184 1157 1193 1184 1208 1142 1124 1145 1135 1150 1165 1128 1108 1087 1141 1118 1005 1075 1122 1050 1065 1012 933 1103 1019 1010 978 1060 994 993 893 927 912 949 905 948 952 892 963 917 925 922 863 914 873 918 842 872 858 843 785 877 853 824 840 823 826 805 893 843 836 777 776 848 746 839 814 785 783 856 783 788 778 756 828 790 783 711 717 797 730 730 797 677 682 674 695 729 623 770 756 673 734 735 725 723 724 686 687 623 634 609 674 715 607 636 577 669 586 544 621 648 548 585 636 579 573 633 649 591 605 548 555 634 574 587 562 645 578 573 543 575 590 582 557 570 603 628 607 591 516 636 548 584 555 543 547 515 538 568 589 605 627 564 516 523 582 507 503 526 513 544 522 532 444 489 468 470 480 529 529 456 515 505 466 517 478 453 474 469 512 524 427 445 425 446 507 446 440 416 415 397 407 440 403 358 403 422 430 380 405 424 372 412 415 397 375 368 365 421 381 380 357 404 367 338 374 361 363 391 359 402 367 414 365 362 372 364 324 389 334 363 315 372 367 364 360 298 336 398 338 347 398 346 306 296 323 325 324 317 308 346 314 310 311 323 314 313 381 299 319 295 322 286 298 290 338 302 266 300 290 279 318 294 326 302 338 294 327 301 249 263 290 282 293 275 260 255 325 312 319 317 306 295 295 275 306 282 329 312 363 408 359 349 336 348 346 325 422 654 1035 861 823 738 883 543 612 227 224 226 231 263 235 266 265 281 276 257 260 258 253 256 241 243 273 259 239 250 260 250 246 206 250 200 199 215 261 255 222 219 188 203 198 222 200 192 219 183 228 244 259 247 219 209 179 248 196 227 195 227 230 202 160 188 201 164 206 185 206 520 665 832 566 584 565 674 421 194 225 230 191 223 198 227 236 212 236 160 211 266 187 219 220 206 205 202 203 209 187 208 223 200 176 209 199 193 225 249 189 219 251 195 192 197 176 200 215 212 244 224 261 265 245 220 222 242 263 236 215 193 174 202 147 159 157 201 174 161 149 142 168 193 179 119 167 171 136 205 136 189 142 155 172 169 142 154 131 136 169 122 137 129 151 137 139 162 138 142 135 127 144 147 122 153 156 127 128 136 167 146 150 172 138 149 133 145 153 161 151 128 146 167 167 153 149 128 162 160 140 138 135 112 131 151 137 134 152 140 137 146 153 162 155 144 173 195 210 172 183 185 200 221 209 208 208 162 215 192 203 180 242 134 169 187 214 201 289 203 211 123 195 224 203 213 190 200 212 157 149 136 147 140 165 129 126 140 115 146 116 145 109 106 114 130 119 96 72 66 119 120 95 99 105 85 71 80 86 85 74 71 93 66 65 63 56 80 61 71 70 58 72 54 68 53 65 61 56 87 52 70 71 70 69 72 56 63 65 65 55 75 96 69 77 73 72 85 59 56 66 79 71 68 66 67 76 61 53 79 63 53 73 68 67 69 55 48 73 38 65 58 61 55 41 51 68 56 62 46 51 56 65 60 61 41 64 25 54 48 64 47 48 48 43 37 49 51 44 50 41 66 52 33 41 48 44 55 60 35 37 57 48 51 41 27 46 65 40 64 47 55 37 50 36 37 49 35 51 35 30 44 40 30 38 49 40 47 36 61 39 38 29 38 32 29 30 44 30 24 38 33 41 22 40 52 54 42 29 31 26 46 38 35 48 38 30 37 38 33 39 40 35 34 26 31 21 52 37 45 37 39 51 36 38 37 46 42 21 41 23 48 32 24 26 40 27 32 36 31 43 26 28 38 39 30 42 28 22 30 31 38 34 24 32 26 26 26 37 29 28 28 25 15 29 29 30 29 28 27 19 28 36 44 37 20 31 32 24 30 35 28 23 30 19 29 29 33 17 18 26 40 19 22 25 28 28 13 25 16 22 22 28 18 19 31 19 24 18 18 23 25 28 25 19 17 22 26 38 16 19 12 30 37 8 22 18 23 33 18 15 21 25 12 25 28 22 25 18 14 18 19 10 16 27 15 19 17 18 18 17 22 26 19 23 27 14 29 23 14 23 24 19 17 19 28 18 15 24 13 25 17 14 11 11 19 12 17 20 17 23 11 21 9 5 18 15 11 12 16 13 11 22 18 12 18 12 13 14 12 26 19 12 14 18 20 14 24 10 9 12 29 15 17 17 12 9 21 17 19 9 11 20 20 25 10 23 13 15 9 18 11 23 13 11 11 14 13 7 14 4 8 10 10 21 4 21 11 12 9 12 12 20 15 19 17 12 14 13 14 16 13 15 14 13 14 21 16 14 11 16 13 15 16 12 9 21 17 11 11 9 15 7 12 15 5 15 12 6 17 13 20 9 18 5 4 12 12 16 10 8 16 10 10 8 6 6 11 16 8 3 11 6 11 14 7 7 11 4 13 14 13 3 6 9 8 15 7 10 4 8 8 11 10 13 8 12 12 5 11 3 7 9 5 4 6 6 9 6 12 6 12 14 13 3 8 6 8 11 6 19 10 5 9 5 9 9 5 16 12 4 11 6 2 8 9 3 11 10 17 10 9 12 5 1 17 13 10 4 7 12 6 8 15 4 7 12 5 6 14 1 8 7 8 3 8 7 4 4 10 13 12 11 3 3 6 6 6 10 8 2 12 5 6 3 5 10 5 15 1 4 12 3 4 6 6 8 4 6 7 5 3 4 6 4 3 8 4 6 4 9 4 2 10 3 4 2 7 2 5 6 5 1 6 3 8 3 8 1 4 3 5 3 4 3 4 1 2 4 4 4 4 8 3 2 2 3 2 6 3 7 2 10 6 3 7 3 2 4 5 3 6 1 3 3 5 0 6 4 2 0 5 7 2 3 9 11 7 8 4 5 6 3 2 6 4 2 3 3 8 0 6 7 7 1 5 5 3 1 8 2 0 4 2 6 5 2 5 3 1 7 6 0 2 5 2 2 2 0 3 2 2 0 4 8 2 4 8 2 6 1 2 1 3 4 1 2 6 1 3 2 3 3 2 0 3 1 6 1 5 0 8 0 3 1 0 6 4 5 1 5 7 2 0 6 2 2 2 4 0 2 0 0 1 3 3 5 0 1 3 9 3 2 2 2 5 3 1 13 2 2 3 4 0 0 0 1 3 2 1 2 2 2 2 0 4 4 0 0 4 7 3 3 0 0 2 2 2 1 3 1 2 4 0 5 0 4 4 6 5 1 1 2 0 1 3 5 8 5 3 2 3 2 2 5 0 0 1 3 3 0 2 4 5 4 1 5 0 3 1 3 0 3 2 3 0 3 2 0 2 2 5 1 2 0 4 2 1 1 4 2 2 0 3 1 2 1 0 2 3 2 3 2 0 0 0 2 1 3 1 3 2 2 6 4 0 1 2 3 2 1 0 2 0 0 1 2 1 0 4 1 0 
];
B = [
0 0 0
 131870 70788 61082
 101518 56785 44733
 159101 97422 61679
 128168 80031 48137
 83924 51664 32260
 146533 108286 38247
 69334 49101 20233
 66509 50373 16136
 55126 40481 14645
 62103 46913 15190
 77956 58802 19154
 53908 39795 14113
 47378 35846 11532
 61442 48600 12842
 49272 38283 10989
 67087 53633 13454
 77071 61675 15396
 135610 112460 23150
 66715 53608 13107
 77981 64324 13657
 57805 47430 10375
 90648 75651 14997
 82152 68734 13418
 56188 46435 9753
 83427 69850 13577
 60780 50697 10083
 114799 97253 17546
 68330 57235 11095
 89583 75643 13940
 67643 56993 10650
 91240 77342 13898
 92365 78432 13933
 74967 63216 11751
 102279 86894 15385
 76441 64749 11692
 112852 95745 17107
 165129 139128 26001
 99134 84226 14908
 99343 84384 14959
 172206 145969 26237
 119436 101962 17474
 146826 124381 22445
 104867 89674 15193
 101825 86746 15079
 180326 153627 26699
 106124 90929 15195
 173400 147845 25555
 114311 97696 16615
 176047 150034 26013
 135393 116163 19230
 164221 140077 24144
 146484 126163 20321
 168312 143893 24419
 145655 125478 20177
 179033 153569 25464
 200365 172135 28230
 118349 102267 16082
 199994 172061 27933
 123628 106266 17362
 14486973 12557294 1929679
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
2 2 0 0
0 4 0 0
4 6 0 0
1 6 0 0
1 8 2 0
5 7 0 0
3 13 2 1
8 26 30 3
150 18 40 15
1078 27 131 26
3300 34 145 64
10399 58 258 131
30322 72 501 327
83540 123 766 555
203456 208 1221 938
513066 440 1894 1662
1107600 868 2896 2804
1304111 1632 4624 4510
622039 2719 7219 7165
123682 4325 9619 9973
28694 6241 12438 12520
21474 8962 15658 15840
22480 13224 19285 19352
26267 18370 23362 23888
30687 23766 29837 29664
36108 30293 33150 33312
41451 36384 39055 39242
46527 42192 46732 47122
51731 48217 50568 49259
57255 54004 54047 54835
60517 57399 58622 58962
62345 59792 60708 60482
65752 61292 61762 62278
64287 62787 63024 63279
64112 63590 63891 64095
65352 63636 64126 63614
64709 64948 64380 64267
65456 64709 64675 65617
66387 65643 66027 65990
67503 67432 67024 66979
68799 68648 68702 68486
70464 70135 70401 70390
72884 72659 72645 72806
75381 75939 75849 75430
78152 78941 78315 78189
81317 81765 81460 81555
85022 83523 83741 83835
86507 86135 85794 87127
88350 88232 87717 87785
88084 87663 88450 87710
87911 86793 87365 87929
85358 85823 85711 86043
82008 82512 82571 82991
78131 78467 77695 78615
73649 74105 73236 74019
68714 68130 67978 68605
62777 62339 62257 62951
57763 57620 57304 57970
52198 51984 52545 52034
48052 47571 47693 47862
43100 43892 43016 43586
40419 40400 41084 40501
38506 38424 38728 38884
36880 36622 36669 36846
36987 36875 36916 37357
39023 39126 39039 39118
41294 41557 41111 41723
44246 44353 43856 45208
50047 49852 50472 49924
55815 55486 55636 55981
64176 63754 63412 63110
68205 68274 67868 67700
72913 72245 71728 72579
74650 74967 74924 75561
73549 73627 73968 74144
66573 66375 66612 66796
55130 56073 55287 55740
38203 38033 38166 38143
19609 19389 19799 19308
6934 6810 6926 6977
1067 1044 1020 1094
9 1 6 5
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
