A = [
495367 488786 2576354 407315 393659 368757 351529 347442 338335 319527 313965 308468 302730 297844 293326 288683 284298 281551 278991 276658 274340 271168 269143 268578 273561 369118 367374 372022 467622 468756 475272 479644 480769 487471 490050 486020 481197 476216 471846 466797 465835 462814 461121 460586 461028 455797 451781 446956 441963 439869 435874 433791 432563 432270 429390 427249 423735 419666 417346 411341 408988 406046 404329 403860 400251 398692 396754 393341 390046 386367 382869 380717 378255 374757 371399 370362 367586 363959 360027 357622 354576 352232 350581 347858 345228 342462 338830 337336 334610 331286 328381 324954 322862 320600 318252 317252 313775 311589 310308 306057 303106 300877 296365 296141 295536 292369 290602 289640 285227 283261 280976 277993 274060 273308 270672 267655 265358 263518 261829 259383 257363 254406 251824 248221 246393 245244 243221 241068 239346 236854 234488 233611 231591 229198 226502 224324 222846 220120 218931 216721 214701 212287 211745 210242 207930 205954 203654 202291 199506 198457 196972 194716 192390 191650 189096 186840 186551 184488 182061 181641 178532 176910 173418 172567 170701 169300 167680 166275 164506 162447 161479 160049 157354 155790 155003 153552 151321 149777 148810 147011 146332 143644 142059 141168 140279 138320 137908 134965 134197 132466 131902 130977 128221 127117 125991 124996 123478 121498 121254 119742 118474 116737 115534 113899 112632 111473 110017 108511 107705 106386 105384 104452 103409 101446 100248 99663 98837 97153 96105 95209 93736 92716 92259 90338 88858 88286 86942 86513 84919 83527 83557 82358 81301 79753 78449 78413 76854 75660 74970 73217 73340 72091 70999 70709 69769 69417 68381 67550 66977 65996 64930 64206 63416 62548 61887 60703 60281 59164 58332 58077 57271 55986 55766 55129 54253 53296 52788 51435 51325 50281 49779 49311 48326 48176 47827 46596 46445 45520 44794 44439 43606 43000 42467 42790 41826 41294 40453 40142 39940 39076 38498 38084 37057 36831 36398 36177 35566 34755 34443 34430 33275 32882 32830 33073 32405 31486 31434 30594 30486 29768 29536 28997 28676 28137 28161 27502 26944 26610 26128 25653 25889 24497 23917 23896 23463 23419 22905 21995 21699 21704 21319 21029 20771 20261 20263 19788 19524 19454 19325 19074 19100 18660 18475 18436 17960 17369 17103 17100 16678 16462 16245 17713 15987 15598 15796 15442 17134 14811 14735 14421 14391 14200 14002 13611 13255 13510 12899 12636 12320 12403 12342 12101 11874 11563 11359 11429 11373 10971 10896 10752 10636 10456 10301 10177 10454 10083 10003 9850 9958 9576 9592 9253 9576 9248 9253 8993 8457 8271 8219 8052 7945 7944 7690 7762 7591 7710 7532 7269 6997 6994 6922 6735 6716 6681 6556 6447 6340 6335 6126 5874 5978 5704 5819 5684 5563 5475 5641 5340 5432 5376 5146 5120 5135 4999 5025 4911 4692 4573 4734 4452 4341 4290 4348 4189 4147 4157 4060 4054 4030 3980 3744 3892 3725 3812 3664 3632 3621 3515 3496 3382 3358 3246 3316 3322 3268 3166 3086 3241 3036 3095 3101 3017 2999 2919 2846 2816 2762 2780 2653 2672 2576 2578 2579 2584 2441 2606 2500 2453 2410 2314 2410 2369 2370 2316 2225 2287 2220 2110 2148 2109 2086 2143 2086 2095 2064 2090 2040 2003 1984 1911 1844 1856 1826 1891 1848 1795 1799 1808 1680 1680 1692 1650 1635 1667 1658 1607 1616 1577 1622 1646 1614 1628 1489 1515 1574 1463 1521 1554 1501 1622 1512 1444 1502 1504 1500 1598 1482 1594 1493 1406 1501 1393 1361 1388 1327 1304 1373 1411 1404 1326 1268 1298 1264 1352 1295 1109 1190 1102 1156 1080 1169 1089 1189 1282 1275 1269 1321 1171 1119 1145 1110 1105 1011 1153 1092 981 1016 1030 1058 979 985 1019 1002 1106 1031 981 1002 991 1024 1027 834 885 872 889 852 851 833 867 875 838 812 799 791 797 764 758 759 762 752 748 739 704 775 738 735 684 690 734 725 697 694 676 731 688 634 673 664 700 644 703 654 653 653 677 611 599 606 633 548 600 579 597 585 621 592 627 623 588 539 538 564 530 536 576 602 591 560 574 575 558 549 510 523 494 521 502 528 484 482 446 469 475 465 501 482 468 466 496 478 453 498 530 470 477 437 476 461 498 436 436 442 494 435 450 508 464 463 495 460 484 460 428 446 444 391 406 449 450 496 471 444 473 464 484 465 454 402 461 447 460 459 514 496 519 573 698 650 614 611 672 495 550 563 645 521 495 670 542 528 494 512 607 518 446 413 473 440 460 393 355 364 370 347 338 368 350 369 393 363 400 415 459 383 449 411 412 411 377 380 363 328 385 392 381 368 369 360 424 321 329 337 354 306 296 284 309 368 316 358 317 350 328 311 338 364 307 261 286 381 297 303 292 300 307 281 277 294 288 319 291 293 310 305 256 229 331 277 305 294 301 318 291 292 309 284 292 314 306 281 282 309 304 304 270 281 273 267 319 260 253 268 263 264 255 220 262 263 225 219 202 261 196 217 204 203 190 220 220 239 222 236 218 214 248 227 230 262 264 237 274 254 265 252 240 259 230 213 206 202 212 207 204 235 198 190 207 228 173 207 210 176 204 166 178 189 189 191 198 211 183 163 173 188 165 176 236 175 193 209 226 433 226 185 190 178 164 175 205 169 177 182 188 138 175 199 160 180 150 155 144 137 137 142 144 150 119 132 164 166 152 135 154 143 125 175 126 147 153 150 162 137 141 107 127 150 124 128 113 133 125 104 105 117 122 119 125 110 117 123 126 150 152 123 118 135 136 115 125 138 147 107 118 117 147 125 134 139 121 131 149 129 160 111 134 117 118 113 118 127 138 88 98 119 109 111 100 91 92 117 95 106 103 117 100 82 100 121 87 93 100 130 106 89 89 91 100 104 90 88 90 98 94 78 71 83 99 114 118 129 110 115 137 104 88 92 104 111 134 121 127 95 110 119 106 96 119 91 92 99 100 104 88 94 102 96 103 112 108 82 98 85 96 91 85 83 92 84 93 88 89 91 94 90 95 93 105 92 100 67 84 98 88 100 81 70 82 99 70 64 87 78 84 61 63 79 90 83 64 74 86 89 94 79 78 92 92 73 95 67 83 66 84 79 93 85 85 74 76 80 83 63 67 73 69 61 68 66 73 59 72 56 51 67 70 72 83 71 85 78 81 78 85 81 68 96 63 104 96 79 91 78 82 80 60 84 86 81 72 78 75 78 72 91 89 78 85 81 82 79 84 64 75 69 76 62 70 71 63 64 64 64 59 78 56 43 50 56 46 47 53 38 54 57 58 48 37 46 48 45 51 39 58 49 45 44 40 46 36 31 37 39 55 42 38 24 42 40 42 37 41 39 48 39 47 43 55 52 53 44 50 44 36 41 41 39 48 31 40 32 56 44 47 41 52 45 28 39 30 47 36 50 32 41 41 42 52 39 37 35 51 54 40 46 51 44 40 49 36 32 38 34 49 43 40 45 41 41 38 37 35 53 44 36 36 41 32 26 43 44 36 39 43 30 23 21 31 45 33 40 36 40 41 34 31 28 26 33 21 31 27 29 15 19 16 24 35 33 23 17 27 38 35 30 28 27 35 29 27 24 22 30 22 28 29 37 24 23 26 30 22 31 26 22 29 41 24 23 35 22 20 23 15 20 21 22 27 27 20 19 10 23 28 20 22 23 23 23 20 42 23 25 33 23 25 29 39 33 30 39 18 25 34 29 27 30 30 32 33 39 34 51 30 39 48 50 49 50 40 48 52 34 31 36 44 32 41 32 37 32 33 30 34 33 39 40 34 36 47 38 33 26 48 45 35 34 37 24 30 40 36 25 28 35 30 37 19 28 21 24 26 24 20 11 30 27 25 31 15 23 19 34 28 25 24 17 16 12 17 23 23 24 19 16 15 9 15 15 13 13 24 14 21 8 22 23 22 16 15 16 13 17 15 19 31 21 25 16 16 20 26 23 23 15 25 23 11 17 12 14 19 14 30 8 14 26 29 15 15 17 14 15 20 20 25 15 20 18 25 30 22 20 14 10 18 11 15 16 19 18 17 11 13 7 17 17 15 12 15 16 11 17 12 13 14 15 14 24 20 14 24 13 9 12 15 7 19 13 14 11 11 13 16 10 9 11 10 15 9 12 14 12 18 12 18 20 21 19 13 23 10 18 20 20 22 17 19 18 13 24 15 17 19 13 25 15 19 22 15 21 23 33 19 10 11 9 17 20 12 22 23 23 20 27 35 33 30 28 23 32 23 23 24 29 6 9 14 13 8 15 14 16 10 14 8 18 14 26 14 5 8 20 15 18 15 13 13 19 10 12 13 11 10 12 26 7 14 18 94 120 116 118 124 86 88 110 33 16 13 11 7 8 16 10 11 7 9 10 14 5 13 16 11 10 11 12 8 22 12 15 15 16 11 28 15 29 15 24 23 15 19 13 11 12 9 14 12 7 8 10 14 15 19 18 9 14 11 13 13 8 10 9 14 9 11 21 14 10 10 12 8 12 10 13 7 4 9 13 12 8 10 13 5 6 13 8 10 5 6 9 9 10 7 8 10 5 8 9 8 10 9 9 9 7 9 10 5 6 7 8 8 12 5 12 5 7 7 4 3 5 10 4 5 9 8 8 6 4 7 7 9 8 6 10 9 10 3 5 5 7 8 6 5 7 4 9 6 8 10 6 9 5 9 7 10 6 8 7 7 9 13 9 7 7 3 9 8 15 15 7 9 12 9 17 9 16 7 5 10 7 7 8 11 11 10 13 7 12 13 19 17 6 11 10 11 7 6 11 11 7 10 8 11 5 8 11 13 11 12 13 6 7 5 14 7 9 9 11 13 8 9 8 11 9 11 7 14 10 9 7 8 11 9 6 5 12 11 10 6 7 8 6 4 6 12 11 8 15 7 13 11 8 6 6 8 6 4 5 3 5 4 10 5 10 7 6 8 5 2 8 10 7 6 11 8 7 4 6 6 7 8 6 7 6 4 3 14 7 10 16 7 10 11 9 4 6 9 11 7 7 7 5 5 3 2 7 4 3 4 7 7 10 6 9 10 11 9 5 7 4 7 
];
B = [
0 0 0
 201692 42253 159439
 95937 20763 75174
 330356 78503 251853
 215543 47223 168320
 129488 28031 101457
 326053 80150 245903
 265351 61142 204209
 151196 33683 117513
 452426 110025 342401
 475933 109148 366785
 87166 19262 67904
 1361905 329201 1032704
 183272 44491 138781
 58901 14155 44746
 306828 88550 218278
 100198 28099 72099
 31377 8175 23202
 340411 98522 241889
 28653 7278 21375
 30068 8071 21997
 7246 1999 5247
 166 38 128
 6943 1975 4968
 507893 153478 354415
 34007 9064 24943
 44638 12767 31871
 527351 162277 365074
 31386 9240 22146
 66822 19778 47044
 838929 245188 593741
 62584 19068 43516
 111713 34036 77677
 593664 191253 402411
 399368 128380 270988
 660334 213466 446868
 1213312 393452 819860
 1017552 321951 695601
 614894 195826 419068
 1413557 469700 943857
 578595 183699 394896
 39854 12692 27162
 1299663 434415 865248
 21471 6968 14503
 37501 12040 25461
 1762842 600321 1162521
 38903 12670 26233
 459599 147214 312385
 2359755 838327 1521428
 454763 147087 307676
 17 10 7
 15804757 5760902 10043855
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
32 78 0 2
15 8 0 0
36 12 0 0
58 17 0 0
45 13 0 1
51 22 27 2
101 31 51 3
311 39 73 15
1172 43 85 32
3817 67 125 56
8684 81 163 92
18526 127 214 122
38185 164 295 201
81575 236 416 325
164216 351 585 492
327617 661 835 855
539574 1332 1288 1260
631253 2682 1870 1858
527882 4400 2659 2595
322460 6179 3348 3392
141366 7422 4073 4159
36364 7858 4614 4743
9292 6831 4930 4938
7381 6318 5127 5157
6910 6445 5446 5421
6961 6745 5470 5717
7123 5961 5756 5685
7042 6121 6144 6052
7634 6529 6663 6655
7651 7064 7033 7252
8289 7383 7618 7824
8838 8089 8145 8299
9390 8901 8819 8886
10484 9876 9821 9833
11258 10978 10882 10881
12483 12113 12494 12154
13853 13478 13803 13475
15639 15350 15421 15457
17445 17248 17627 17240
19798 19588 19771 19717
22389 22321 22635 22220
25949 25817 25506 25729
29262 29283 29209 29309
33170 33296 33111 33391
37813 37948 37824 37533
43061 43290 42905 43497
48512 48704 48599 47964
53854 54131 53900 53943
59629 59786 60538 60618
66413 66288 66380 65913
72241 72155 72471 72286
77347 77524 77661 77355
83318 82607 82780 82323
88222 87576 88411 87842
93628 93316 94634 93517
98989 98687 98650 98456
106086 106728 106122 105908
113183 113361 112235 113128
120109 120108 121141 120000
126789 126664 127201 126322
133808 134073 133529 132592
135281 134443 134896 135047
130005 129406 130246 128763
112653 112771 113063 112276
83525 83989 83500 83023
45613 45974 45746 45459
19026 19770 19923 18705
10556 10427 10995 9947
8343 8250 8148 7867
7344 7479 8501 6896
5226 5228 5087 5487
3508 3075 3103 3586
266 243 208 219
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
