A = [
568047 587470 1231210 608808 598427 593542 559989 571397 559432 552698 553249 546678 547578 546830 541019 535597 535991 531212 529973 527674 525200 521746 519451 514688 512885 509144 507614 502900 503009 499135 495809 494005 490425 487883 483903 481869 478155 476869 474403 470297 469402 466965 461156 459052 457415 454249 452992 450029 445470 442717 440712 436783 434559 432080 428244 426315 423075 419899 415933 414106 412276 407818 404129 401247 399806 394962 392323 388972 385451 382564 380602 376619 373331 370941 366105 364630 359995 357192 353523 351861 347910 343807 342098 338615 334612 331257 329707 324714 323254 319596 317593 312733 310650 307714 304990 301228 297886 295258 290508 287971 284542 281978 278389 275196 272892 269280 266788 263922 260783 257173 254651 251563 249013 246392 242996 239783 237776 235207 232083 229358 226409 222794 219550 217668 214029 210889 208822 206555 202907 200560 198630 195312 191712 189702 186909 184547 181895 179204 176246 174272 172247 168970 166805 163739 161975 158934 156808 155536 152830 150334 147831 146006 144612 141570 139870 137685 134317 133515 130635 129220 126835 124886 122468 120615 118576 116697 115522 112743 111135 109374 106665 105597 103763 101998 100084 98842 97188 95079 94286 91979 90505 88722 87488 85573 84252 82145 81246 79546 78204 76784 76038 74371 73028 71478 70177 69107 67618 66466 65334 63917 62793 61565 60342 59683 58113 57168 56250 55463 54152 52752 52170 50710 50242 49184 48482 47271 46351 45433 44542 43905 43050 42345 41304 40468 39597 38883 38555 37413 36849 36199 35150 34831 34076 33121 32725 31947 31360 30861 30311 29678 28665 28700 27967 27369 26892 26139 25499 25322 24983 24329 23638 23097 23085 22415 21641 21592 21048 20521 19977 19491 19319 18915 18519 18053 17678 17183 16856 16695 16424 15772 15587 15361 15172 14871 14630 14283 13930 13822 13125 13022 13091 12381 12107 12097 11701 11575 11182 10809 10662 10376 10230 10253 10126 9692 9467 9359 9175 8980 8708 8624 8299 8293 8141 7710 7829 7678 7268 7193 7091 7259 6832 6707 6558 6608 6324 6220 6119 5956 5807 5646 5587 5410 5293 5125 5119 4907 4909 4718 4702 4628 4607 4371 4324 4212 4092 4100 3979 3906 3790 3738 3477 3530 3550 3325 3413 3356 3316 3251 3090 3064 3019 3087 2888 2879 2648 2699 2571 2626 2690 2595 2467 2435 2399 2412 2326 2262 2209 2223 2116 2135 2043 2008 2091 1916 1865 1923 1908 1878 1769 1829 1700 1746 1675 1652 1686 1639 1597 1630 1483 1505 1498 1460 1512 1450 1359 1363 1315 1356 1295 1284 1208 1277 1293 1159 1100 1228 1168 1165 1056 1112 1094 1049 1091 1043 1092 1077 1093 1078 958 1034 1018 977 948 920 966 978 948 917 927 955 894 876 923 881 871 851 847 842 826 829 752 751 782 809 725 733 688 688 712 658 633 660 670 651 703 675 643 659 643 630 623 673 653 648 588 580 634 620 614 627 577 666 597 551 611 580 590 609 549 717 624 628 552 529 551 521 515 495 485 482 547 491 464 467 495 481 434 424 444 429 449 443 440 412 400 428 421 407 416 436 419 370 411 378 425 393 393 392 420 430 390 458 422 386 395 411 410 375 393 392 378 370 343 359 395 326 376 377 367 352 343 378 334 337 329 341 326 334 343 322 335 345 300 331 315 310 328 325 327 336 313 293 294 299 304 307 326 327 303 466 290 319 314 310 346 302 325 313 314 289 267 296 296 303 275 292 288 319 257 294 252 307 290 285 274 261 259 290 259 273 273 280 259 248 268 307 310 280 309 321 424 282 266 270 278 269 265 244 226 239 238 247 245 253 242 230 231 208 242 236 223 210 227 226 241 234 263 219 214 236 212 204 209 218 217 243 276 385 231 248 248 249 241 244 229 193 198 220 223 209 207 182 200 168 199 199 215 216 181 210 215 217 215 206 198 198 203 196 186 178 179 177 163 167 155 153 184 175 152 187 206 181 173 153 186 164 147 155 177 156 161 153 164 162 188 184 175 202 167 176 193 191 195 176 183 156 142 152 162 175 148 138 144 149 151 165 161 151 148 140 173 163 140 164 158 157 128 142 154 150 167 161 139 157 150 155 127 153 153 159 153 167 143 161 150 147 171 146 140 119 127 129 131 108 112 143 151 127 121 130 128 152 150 121 143 128 130 149 136 141 126 130 145 125 149 157 169 141 169 167 150 161 145 136 164 154 151 122 117 136 135 116 125 129 134 129 123 111 105 104 131 136 130 147 126 106 123 126 124 117 107 100 95 110 124 144 136 138 118 116 160 147 134 109 135 136 132 124 115 103 91 121 125 110 100 95 124 110 113 112 124 124 124 112 106 105 93 101 100 93 97 78 103 112 93 100 94 90 81 81 104 111 101 76 94 93 80 70 100 82 83 80 86 84 91 73 89 83 86 106 84 71 77 79 79 90 86 85 72 74 68 57 69 79 102 72 56 85 81 63 67 75 68 65 74 57 75 73 52 70 70 60 70 61 63 116 88 76 76 84 74 81 71 82 112 86 84 77 78 70 85 74 94 90 90 106 86 70 77 95 105 83 86 92 73 93 75 81 90 85 80 51 105 98 117 76 60 73 72 85 91 108 84 91 70 89 82 98 78 116 107 115 99 120 96 95 77 95 94 72 77 86 87 69 64 88 81 60 66 63 62 71 53 62 77 66 66 78 76 64 51 61 66 44 69 57 68 60 56 73 65 57 52 62 66 81 70 78 71 62 54 66 76 72 53 56 73 61 40 47 58 38 51 42 54 54 60 40 50 51 58 49 51 141 110 101 137 121 181 116 102 95 107 144 83 96 115 189 186 123 167 182 98 91 115 124 115 115 89 191 101 111 104 78 89 53 37 43 28 36 30 27 26 31 29 31 32 45 47 39 29 27 23 35 41 33 33 26 27 23 43 37 37 23 36 30 28 48 59 42 86 105 97 101 110 110 95 119 100 112 30 26 25 19 21 22 27 30 40 35 37 28 21 28 32 44 30 26 29 47 26 16 24 16 50 61 52 90 81 102 119 112 91 121 106 92 102 21 25 24 19 23 26 37 30 39 32 33 26 34 28 39 29 23 26 29 26 28 35 34 36 32 35 26 37 34 31 25 21 29 31 24 28 25 30 20 22 33 28 31 24 36 38 41 25 26 22 22 47 24 20 23 10 14 18 25 29 24 28 32 37 38 39 36 38 31 24 33 21 34 17 22 23 26 15 20 20 16 12 16 22 20 24 19 21 30 21 15 14 11 23 12 17 18 19 19 23 14 16 14 32 30 48 41 30 38 23 18 13 22 9 13 16 13 14 18 21 5 16 11 23 18 16 12 14 20 19 16 15 13 16 9 13 17 11 15 15 13 15 10 12 11 28 28 24 11 13 17 6 14 12 13 7 9 16 7 5 10 8 12 14 4 9 18 11 14 10 14 11 15 4 17 6 12 11 18 21 12 12 18 18 12 9 9 16 12 9 7 15 5 9 5 13 8 5 3 15 15 14 14 9 9 9 12 4 11 10 10 13 10 10 9 13 11 6 13 16 12 7 7 14 6 16 9 4 7 9 12 7 9 12 13 7 7 22 15 20 29 13 10 11 7 5 12 10 5 11 4 4 6 11 3 7 2 11 10 6 7 4 9 7 4 8 5 8 7 11 10 5 4 5 10 13 6 17 16 6 7 11 6 1 1 5 11 17 5 8 14 7 4 9 4 12 6 4 5 6 2 8 15 11 8 9 16 6 11 9 16 11 27 7 13 8 8 8 9 12 8 7 11 5 6 5 13 8 9 8 12 9 9 6 6 3 9 6 12 9 16 8 10 10 10 9 10 15 6 13 8 5 7 3 7 3 7 7 7 14 5 9 8 4 2 4 2 8 7 3 3 2 3 4 2 4 6 8 9 5 8 4 5 6 4 6 4 6 4 6 1 5 5 5 2 6 9 10 1 6 1 10 6 3 7 7 3 3 0 7 2 6 5 6 4 7 3 7 11 3 4 13 4 9 7 8 6 4 6 3 2 2 1 4 13 10 2 9 5 5 5 4 0 1 3 4 3 5 4 2 2 3 5 1 3 6 5 4 9 5 4 9 4 10 5 6 2 2 4 5 1 8 4 6 7 6 2 5 3 2 2 3 5 3 5 1 4 12 6 5 2 0 3 1 3 5 1 4 5 3 5 5 2 3 4 9 4 5 4 1 3 6 3 3 2 5 1 6 3 5 5 6 2 5 10 6 3 0 1 2 0 3 2 2 4 1 1 2 3 1 3 1 2 5 7 3 3 1 4 6 1 2 1 2 2 2 2 5 6 3 3 7 9 5 3 1 3 2 2 0 1 1 1 1 1 2 4 3 2 3 0 2 1 1 6 1 3 2 2 0 2 2 1 4 5 6 11 3 5 12 11 9 9 1 1 1 4 2 1 1 4 3 2 1 1 2 5 2 0 1 1 3 1 3 0 2 4 2 1 1 8 4 5 4 1 3 7 10 10 10 4 2 4 4 2 2 4 2 1 3 3 2 0 1 2 2 2 2 0 1 2 5 0 2 1 1 1 4 1 2 1 2 4 4 3 0 2 3 2 3 1 0 1 1 0 3 1 2 0 0 3 1 0 1 0 2 2 2 4 4 3 3 3 2 3 1 1 2 2 1 2 1 3 0 0 6 2 0 0 1 1 1 1 1 0 0 4 3 1 0 1 0 1 4 2 1 2 2 1 3 2 0 0 2 2 3 2 2 1 1 3 1 1 1 3 1 1 1 2 5 1 3 3 1 5 4 7 8 6 4 6 7 17 11 11 8 8 9 4 6 9 4 9 5 10 5 4 3 1 3 0 2 1 1 2 2 1 2 3 5 2 5 4 7 8 7 6 5 6 17 12 11 10 8 12 18 13 15 7 6 11 11 17 7 9 8 5 6 4 9 2 5 1 
];
B = [
0 0 0
 80378 53644 26734
 48330 31789 16541
 89581 69769 19812
 52071 35891 16180
 50811 35848 14963
 56364 41717 14647
 65785 51823 13962
 44865 33528 11337
 82856 70824 12032
 50753 40218 10535
 52035 41587 10448
 55178 46079 9099
 76726 66686 10040
 42606 35594 7012
 94084 86167 7917
 52945 46169 6776
 56795 50527 6268
 57299 51141 6158
 91710 84139 7571
 55785 51231 4554
 111568 104673 6895
 84301 78327 5974
 65032 60802 4230
 117649 110556 7093
 154852 148553 6299
 22708 21334 1374
 356991 345581 11410
 20286 19606 680
 38195 36713 1482
 31483 30545 938
 57020 55716 1304
 16321 15657 664
 159005 156198 2807
 13822 13361 461
 40691 39567 1124
 21744 21268 476
 49080 48121 959
 3095 2897 198
 202710 199832 2878
 338 323 15
 12145 11810 335
 3744 3527 217
 48760 47676 1084
 5760 5647 113
 4366 4230 136
 18805 18432 373
 9962 9570 392
 333914 329548 4366
 58372 57562 810
 5867 5772 95
 32335 32003 332
 13931 13690 241
 13129 12732 397
 435876 431218 4658
 8933 8815 118
 156898 155952 946
 20744 20575 169
 17515 17255 260
 21031 20464 567
 28089522 27991884 97638
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
13 9 0 0
6 3 0 0
19 2 0 0
29 6 0 0
18 3 1 0
37 7 10 2
2020 9 29 1
14628 15 26 8
62349 19 41 20
211832 23 63 22
539316 24 80 44
1291456 36 95 57
2615510 40 103 80
4619628 49 153 137
6281009 107 163 184
6685185 130 204 244
5166124 120 250 276
2845600 215 241 281
1034210 286 325 365
201355 310 390 431
19912 354 429 518
3100 458 496 570
1954 469 588 625
1804 467 602 660
1773 462 568 624
1464 479 514 537
1925 482 485 522
1171 469 485 499
1696 447 457 475
1518 745 388 359
1452 355 488 447
2139 349 297 283
3967 443 306 285
784 489 313 311
672 629 373 415
566 478 253 352
401 1169 263 331
824 826 198 179
776 813 221 212
749 785 235 257
872 930 259 305
1032 1047 366 394
809 846 408 363
1009 1123 484 468
840 825 444 433
1054 975 405 423
1051 1082 489 474
709 676 403 421
743 771 577 523
771 773 425 432
865 780 365 409
573 639 382 361
537 545 408 401
404 407 352 368
556 528 430 349
362 365 443 390
332 269 405 393
267 258 999 1008
297 288 264 259
373 399 271 246
225 250 348 356
349 452 389 406
256 249 241 247
252 271 266 258
274 314 336 358
412 359 460 470
353 339 357 316
331 381 340 349
435 398 450 433
428 474 629 517
587 521 576 527
543 557 627 630
605 620 945 953
674 684 634 610
658 650 689 655
636 609 547 583
580 581 565 615
480 502 517 550
284 335 316 347
161 152 128 156
33 30 44 38
0 0 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
