A = [
7016461 5318807 56510101 2273775 2463689 2209594 1984601 2081849 1882601 1784306 1740126 1655468 1648115 1597962 1541808 1516873 1488253 1488300 1482423 1431518 1414664 1430168 1400072 1373269 1363561 1439384 1432860 1421257 1473309 1322331 1326160 1313189 1164475 1174188 1169879 1170866 1166792 1151675 1150846 1161510 1146896 1161121 1160478 1152749 1176604 1149356 1141646 1190413 1161821 1159160 1169904 1122203 1134590 1130898 1099779 1077151 1089123 1107221 1065626 1048841 1069223 1053088 1038734 1023369 1011478 1015652 991906 977624 974711 956530 951047 950969 942549 936855 940230 929856 922900 918001 902102 887413 883082 882141 864025 853160 857571 833112 815718 787120 769174 766867 755070 744982 743397 736087 725722 721791 715788 709839 702266 695044 691019 687267 679131 673028 667780 665897 659748 652683 649241 646173 638021 637177 634284 631846 627677 625147 663414 666657 666017 706531 718197 720447 720913 723502 723015 718566 714052 709320 702531 699518 693374 686128 683194 676965 672695 666685 661167 656296 649344 644805 640234 633315 627862 623999 617606 612846 607685 601259 595709 590601 582339 577306 571534 565063 560305 556033 549758 543561 537996 532601 527604 523038 516978 511005 507371 501434 496103 491043 486408 479797 475243 471218 466041 462989 458505 452869 449395 443197 439660 434714 428639 425171 423604 417175 413291 409356 403777 401051 396367 393239 388608 383423 378566 375405 370574 366845 362904 358837 354290 350728 347889 344443 340473 335677 332513 328218 324647 321137 317516 313553 308276 304618 301602 298564 294585 290375 288394 285015 281838 278542 274613 272313 267821 264748 261084 258444 253180 249712 245472 241751 238480 235543 231195 228271 224482 221653 218965 216117 213272 210351 207269 204533 201746 198397 196674 193705 190877 189083 186993 183163 180929 178564 176964 174102 173118 168796 167157 164689 162491 160726 159234 155986 153769 152520 149706 147978 146021 143513 142299 139949 138313 136436 134213 131785 130735 128345 126806 125256 123122 121597 120218 118943 116456 115125 113309 111677 110069 109331 107557 105725 104386 102166 101655 100355 98486 97091 96172 94988 92616 91914 89898 89378 87524 87152 85525 84072 82456 81816 81075 78730 78050 77448 75938 74828 73480 72258 71866 70596 69153 68626 68040 66541 65496 64593 63859 62590 61899 60724 60632 59024 58630 57430 56505 55522 54692 54165 52762 52234 51652 50801 50275 49074 48523 47791 47112 46735 45649 44891 44231 43742 42875 42902 41999 40976 40640 39864 39183 38925 38271 37405 37135 36561 35385 35142 34366 34137 33613 33202 32835 32094 31705 31133 30483 30593 29698 29239 28866 28413 28378 27364 27162 26446 26322 26079 25196 25099 24876 24401 23806 23426 23134 22554 22362 21980 21782 21468 21103 20443 20165 20079 19581 19340 19223 18963 18491 18248 18036 17642 17592 17059 16807 16799 16440 16012 15862 15414 15503 15056 14765 14770 14488 14201 14036 13774 13686 13317 13221 12913 12760 12329 12598 12339 12092 11718 11759 11370 11145 11112 10921 10624 10487 10353 10176 10042 9972 9703 9526 9414 9293 9237 9095 8768 8638 8407 8497 8296 8096 8023 7933 7817 7622 7521 7476 7351 7195 7151 6923 6836 6829 6571 6552 6445 6181 6313 6161 6111 5869 5988 5730 5733 5653 5500 5504 5418 5160 5268 5004 5023 4977 4810 4834 4801 4650 4626 4567 4506 4345 4404 4262 4322 4149 4041 3975 4047 3930 3769 3756 3756 3684 3589 3527 3575 3501 3325 3471 3318 3236 3241 3242 3197 3019 3127 3008 3023 2858 2851 2873 2757 2643 2750 2509 2558 2545 2515 2469 2510 2433 2355 2383 2263 2310 2196 2234 2113 2134 2102 2081 2144 1998 2003 1947 1985 1883 1866 1869 1862 1826 1865 1814 1747 1778 1758 1678 1671 1608 1689 1679 1592 1578 1544 1453 1507 1455 1493 1425 1395 1358 1439 1423 1340 1341 1289 1345 1281 1307 1209 1269 1251 1243 1179 1122 1186 1195 1249 1216 1132 1139 1166 1110 1121 1045 1040 1035 1055 989 978 968 1019 928 1012 937 942 911 952 913 858 905 939 880 849 897 876 835 790 831 853 766 759 750 790 749 789 736 749 716 759 708 803 708 685 683 734 755 651 729 624 688 711 675 674 601 642 629 640 672 652 591 636 594 592 637 553 607 553 578 603 588 557 534 568 536 533 516 574 551 515 533 506 472 519 507 469 501 505 495 491 486 513 491 497 479 451 467 456 449 471 443 447 453 408 454 435 449 456 453 421 419 420 439 410 396 402 424 383 396 406 389 405 384 414 404 399 375 369 380 376 399 358 340 385 393 372 339 371 356 377 367 381 364 395 372 374 331 351 364 355 317 363 305 321 325 361 320 337 319 350 345 303 319 326 296 291 290 336 302 280 279 320 328 331 273 302 312 300 265 303 274 291 322 290 266 304 282 297 245 261 283 269 254 265 253 275 264 268 283 263 258 249 299 251 240 238 233 267 263 284 317 274 254 249 262 287 236 264 270 250 261 236 198 222 234 220 266 273 233 275 258 232 224 223 204 201 197 216 225 225 211 228 231 232 214 193 226 229 221 192 210 204 221 212 205 202 221 197 208 218 197 197 201 221 208 198 200 177 212 197 185 198 180 209 181 175 178 175 179 183 177 163 171 190 180 171 193 187 181 185 158 180 181 177 188 182 179 178 180 190 190 161 166 162 147 161 172 150 170 154 146 153 176 181 139 163 188 164 177 141 142 150 138 134 136 136 169 167 130 153 113 175 137 156 159 164 129 144 151 140 122 127 124 127 148 152 136 141 167 148 142 117 136 145 127 132 139 143 137 143 136 142 109 125 130 119 121 142 118 126 118 125 143 123 128 141 112 124 142 104 117 111 107 115 107 97 142 136 123 91 120 122 128 126 104 105 125 167 118 115 124 108 129 135 118 130 135 125 126 125 110 114 105 113 113 117 118 115 101 115 118 120 141 121 124 105 96 147 103 111 119 124 120 99 109 97 98 100 119 100 102 102 130 119 101 73 121 100 103 101 105 122 113 133 129 187 208 260 416 384 481 482 459 483 548 488 525 508 555 412 301 380 377 367 358 331 368 327 313 320 311 311 365 307 326 312 331 303 320 297 308 368 304 357 342 305 349 322 313 316 347 325 295 309 357 393 348 357 389 495 433 419 441 448 443 436 448 429 431 1109 450 439 381 368 294 308 317 250 216 267 220 194 225 190 185 176 173 170 168 174 159 152 174 143 156 135 156 135 169 142 146 147 155 151 125 149 134 148 180 174 176 547 245 833 660 663 464 396 382 370 349 321 217 176 171 138 176 148 153 141 140 142 139 131 95 104 122 248 1000 104 89 92 86 90 85 102 77 91 86 79 64 93 77 97 76 91 69 73 93 85 176 72 56 78 88 155 74 89 81 81 192 82 90 83 100 108 96 78 97 108 98 85 75 110 103 217 113 93 95 94 120 109 103 129 108 159 111 122 123 116 128 114 130 136 122 135 144 159 166 151 136 143 161 133 152 170 130 170 178 166 149 153 144 148 166 162 138 140 138 140 188 160 167 174 154 182 170 206 209 197 204 192 175 183 179 197 188 206 185 202 179 175 215 213 190 209 205 214 216 218 239 238 203 223 234 241 203 213 214 239 227 187 223 208 369 220 198 183 179 361 150 113 129 92 410 94 112 136 105 332 120 199 362 121 152 102 96 74 75 83 82 61 81 93 92 90 58 91 78 85 71 68 82 75 93 96 105 79 63 70 91 106 107 100 98 118 129 141 87 119 118 79 94 141 109 111 96 95 85 84 95 96 75 95 95 98 93 99 97 97 84 98 114 96 101 113 100 97 106 125 84 100 101 93 83 67 75 80 108 87 57 78 266 72 79 81 60 76 56 55 53 49 57 65 47 51 38 54 41 39 48 34 43 61 48 40 41 46 36 53 30 37 35 25 29 31 39 22 39 25 41 36 24 24 29 33 38 26 32 27 24 42 23 24 32 31 25 34 26 30 21 20 37 33 32 19 30 37 28 34 28 36 27 27 40 31 28 18 27 23 21 33 24 26 20 20 31 14 21 17 19 28 23 17 18 18 25 25 20 19 26 22 29 31 25 29 27 33 19 17 20 40 24 38 29 36 17 28 22 35 18 29 24 38 25 49 24 41 38 36 33 41 33 55 38 28 45 43 51 55 52 38 54 56 39 51 33 47 69 50 47 47 38 41 45 43 48 45 59 64 48 49 55 60 62 43 53 46 48 48 47 48 55 47 54 37 47 46 38 58 47 39 55 55 41 42 35 44 45 63 58 44 46 44 58 40 41 42 49 52 45 36 39 41 31 32 41 39 48 49 42 43 43 46 46 47 30 46 37 51 44 43 48 67 33 25 36 29 28 24 25 22 26 12 15 18 28 18 12 16 17 15 15 19 16 15 11 19 13 15 16 23 19 18 11 10 13 7 20 15 8 13 13 13 14 17 14 12 9 12 12 13 13 11 15 10 15 16 21 11 21 8 14 12 21 21 9 15 15 28 13 22 12 13 14 29 13 16 11 14 23 14 16 15 10 9 17 15 13 21 23 14 19 14 23 17 14 16 16 15 17 11 11 15 30 15 17 12 6 20 14 19 12 10 18 10 7 20 14 9 11 8 12 12 9 15 9 9 11 15 13 7 17 4 17 11 8 13 14 11 10 17 12 7 8 11 11 14 13 10 3 12 31 34 18 12 14 6 10 18 6 16 10 8 19 10 6 5 7 12 7 8 6 9 9 9 10 8 7 7 2 8 5 8 9 15 8 9 12 7 3 13 19 11 10 13 12 12 6 5 9 9 8 5 8 12 6 13 5 13 3 11 8 5 18 6 7 11 8 13 12 6 12 6 10 8 13 8 9 11 7 14 16 10 14 9 7 10 17 13 5 6 16 18 12 9 11 9 12 17 10 8 12 15 11 13 12 13 10 12 9 14 12 19 18 10 10 7 15 7 6 5 11 8 10 13 8 9 8 9 17 8 11 7 16 9 12 9 18 9 9 15 10 11 10 14 14 8 10 7 12 8 11 6 4 7 13 8 9 17 5 6 7 9 10 13 10 17 7 12 6 8 4 6 10 4 17 7 5 7 10 14 9 11 5 8 13 8 11 8 11 5 5 4 9 6 5 4 4 10 8 8 6 7 8 11 18 12 13 4 6 10 10 8 
];
B = [
0 0 0
 383389 245882 137507
 1160186 941521 218665
 463383 328142 135241
 396590 281304 115286
 299893 203944 95949
 230356 157926 72430
 208387 143259 65128
 262653 200504 62149
 271883 208345 63538
 929013 819152 109861
 370237 296819 73418
 342953 274490 68463
 329319 264146 65173
 315022 253004 62018
 634986 558141 76845
 389311 322411 66900
 373330 308235 65095
 343082 284601 58481
 355896 293553 62343
 556274 485102 71172
 408017 340097 67920
 398757 334109 64648
 396886 331138 65748
 381830 318091 63739
 525204 452923 72281
 400009 335250 64759
 429297 358427 70870
 401428 337100 64328
 410337 343253 67084
 491713 421585 70128
 428532 363361 65171
 428792 363783 65009
 413663 353600 60063
 454761 383886 70875
 469969 407903 62066
 434717 372170 62547
 685806 565668 120138
 421172 362406 58766
 467551 397446 70105
 666757 559084 107673
 462324 395556 66768
 610425 511005 99420
 426343 369850 56493
 452983 388271 64712
 644154 543265 100889
 466638 401675 64963
 618265 520703 97562
 462779 400789 61990
 595402 501777 93625
 476280 414311 61969
 594555 502349 92206
 485674 420736 64938
 591647 500331 91316
 459318 398660 60658
 625414 529403 96011
 571149 485006 86143
 449938 394152 55786
 579728 493204 86524
 408002 361516 46486
 118423359 113203005 5220354
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
98 307 2 4
25 40 0 0
37 136 0 0
40 76 2 1
52 78 0 0
41 63 6 0
76 130 13 4
297 121 10 6
97960 129 18 5
735304 205 56 14
1555427 248 95 23
3160899 268 220 100
5698496 359 1697 494
10100580 550 6959 2580
15752861 860 7114 3715
20631918 1974 7477 4881
20505256 4244 10815 9398
16639983 8055 16178 15831
10494147 12581 23450 23504
4668719 18023 30581 30775
1368433 24097 37456 37930
262434 32532 44801 45492
71178 42875 52477 53553
63713 54170 61066 61989
71392 66669 70420 71649
81275 78634 81011 81779
91658 91116 91921 92640
102189 104413 103659 104949
113491 116722 115061 117083
125395 128950 126408 128636
136444 140249 137478 138830
145200 149931 145702 147708
151778 157249 153174 156572
155874 161927 158634 159944
159397 165171 161808 161890
160668 166187 160293 162938
157878 163220 159451 161806
155510 159323 156422 157511
153385 156257 154294 155044
151170 152740 151854 153574
151022 152036 150543 151445
151045 151949 150772 151588
152730 153155 152738 154579
156521 156031 155943 157774
160790 161304 160371 161885
166242 166508 165163 166328
169260 170294 169016 170533
172408 171758 171739 173292
172018 172398 172108 174153
171462 171292 170590 171406
165970 166578 165461 166608
157714 159727 157469 159143
148530 150077 148161 149757
136914 139040 138490 139448
125217 127231 125257 126326
112749 114899 113168 114633
101463 103191 102479 103884
92004 92634 91799 92841
82683 84302 83585 84298
74901 76458 76278 76493
69961 70869 69864 70716
67290 67643 67707 67728
61934 62315 62269 62373
58161 58597 58373 59093
55406 55926 55844 56648
55146 55529 55396 55502
54483 54327 54008 54821
56542 56732 56154 55520
54221 54097 53976 54480
53034 52360 52461 53352
51459 51088 51072 51673
49809 50025 51059 51498
47990 48232 47693 48239
45004 44713 44564 45149
39880 39752 39581 40582
35465 35686 35533 35887
30577 30096 30095 30354
22250 22285 22160 22459
17885 17809 18152 18101
13661 13658 13541 13736
8276 8140 8073 8230
5195 5410 5443 5438
311 307 301 350
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
