A = [
6006409 4540065 47999199 1959281 2110229 1902689 1707934 1794216 1633313 1547136 1510823 1446768 1442595 1405229 1361246 1338045 1317372 1322418 1315177 1272281 1262171 1275018 1252175 1228646 1220434 1284456 1279122 1266355 1305760 1164951 1164731 1153101 1011321 1019326 1017053 1014085 1011237 996880 995448 1006569 994032 1004755 1005697 998184 1017331 995847 988583 1033064 1005735 1006055 1012355 973377 984219 982212 950579 931496 943346 959209 921916 910084 925897 911065 900086 886333 877489 880541 859451 846809 844775 826621 822931 822719 813473 811823 814756 805921 798412 798250 782338 770412 765881 763660 747732 739982 742051 722694 706605 681681 664984 662198 653423 645702 643694 634519 629000 623621 618535 614753 607890 599918 597353 593854 586474 581072 577710 574167 569547 563953 559866 554936 551024 550350 546173 542738 539047 537338 571591 574361 573093 611618 617616 620331 619911 622074 618980 617816 613194 608213 604416 598962 591933 588767 583690 577911 572299 567079 563981 558007 552714 546963 541076 536212 531313 528567 522297 517023 512356 506908 502454 496108 490689 484742 480535 475702 471398 464795 459407 454462 450330 445866 440918 434782 429307 426108 421014 414628 411290 407045 402918 398319 393072 389349 385773 381170 378334 373119 370470 365248 361587 358057 353445 348269 346144 341180 338815 335306 330748 327402 324301 321529 316146 312855 309836 305983 301810 298459 295162 291828 289058 284680 282075 277881 275085 272084 269643 265864 262847 258724 256306 252329 248911 244871 242306 238397 237019 234048 231448 227927 225349 223185 220197 216410 214874 211786 208852 205395 202607 198430 194076 192829 189867 187268 184487 181169 178471 176293 172778 170709 168571 166114 164365 161734 158471 157439 155612 153786 150714 149070 147473 145005 143175 140343 139211 137041 135810 132892 130926 129363 127460 124874 123314 122606 120954 118685 116821 115273 113677 111840 110771 109119 107218 105869 104511 103131 101864 100625 98617 97015 95722 94469 93342 91364 90153 89242 87983 86496 84939 83272 82708 81467 80200 79311 77874 77060 75466 74919 73694 72487 71875 70279 69251 68227 66795 66269 65202 64460 62879 62639 61532 60569 59675 58238 57643 57611 55676 55075 54451 53372 52573 51787 50950 50459 49201 48857 48346 47211 46904 45618 45162 44256 44002 43357 42349 41813 41329 40512 39493 38643 38772 38028 37279 37393 36486 35685 35337 34251 33867 33295 33026 32711 32056 31516 31354 30626 30102 29860 29257 28581 28014 27902 27201 26892 26287 25754 25522 25391 25031 24338 23881 23569 23418 22743 22445 22335 22008 21610 21005 20557 20541 19697 19672 19472 19188 19046 18387 18352 17889 17662 17425 17002 16842 16395 16174 15929 15975 15614 15221 14774 14741 14747 14238 14003 13918 13710 13387 13147 12965 12746 12596 12366 12221 11961 11696 11615 11494 11222 11109 10857 10685 10588 10241 10193 10071 9800 9605 9566 9419 9100 8882 8957 8956 8568 8517 8301 8266 8059 8086 7866 7643 7494 7425 7243 7283 7037 7020 6731 6808 6598 6488 6225 6387 6204 6196 5999 5692 5789 5731 5593 5632 5497 5266 5307 5206 5071 4960 4957 4900 4673 4628 4669 4535 4409 4405 4287 4291 4190 4097 4054 4051 3999 3889 3654 3704 3655 3676 3609 3532 3494 3458 3332 3373 3407 3218 3180 3112 3091 2999 2955 2952 2880 2849 2862 2770 2668 2669 2582 2635 2536 2544 2363 2501 2457 2445 2360 2310 2256 2166 2216 2198 2132 2012 2038 1988 2117 2058 2029 1986 1967 1837 1823 1758 1852 1741 1736 1662 1637 1665 1650 1617 1538 1587 1499 1528 1562 1480 1491 1368 1441 1425 1305 1358 1434 1364 1254 1258 1219 1251 1163 1269 1207 1208 1142 1161 1229 1152 1098 1132 1145 1083 1056 981 1058 1030 1050 1005 1050 968 963 922 934 916 911 902 979 907 862 864 921 872 857 824 849 841 913 847 821 851 727 758 733 702 740 666 712 689 711 669 637 696 679 679 668 657 655 697 637 639 640 629 640 635 636 605 589 572 586 558 581 609 545 553 572 557 549 502 536 563 561 531 536 461 533 528 486 479 502 480 519 516 474 455 490 477 452 477 444 472 458 448 407 466 431 425 449 463 411 420 381 425 397 389 390 428 394 385 396 362 368 396 419 345 354 372 374 361 351 335 346 371 338 338 335 329 371 367 352 378 330 370 331 332 340 310 326 311 291 310 288 347 294 332 312 301 287 313 281 307 300 309 304 270 292 315 280 266 252 290 276 268 303 289 274 279 292 316 273 253 273 270 303 277 255 250 256 264 256 270 244 260 250 252 258 259 257 256 264 245 239 241 275 258 238 250 260 217 231 245 228 265 204 219 273 236 236 206 256 230 204 204 199 200 216 196 219 219 211 228 208 209 225 230 208 206 220 213 195 196 222 174 219 210 179 191 211 261 242 222 189 185 205 209 198 202 184 174 184 198 200 189 178 160 209 190 191 190 186 188 190 173 164 169 181 164 178 207 165 179 170 158 171 190 181 154 162 174 161 173 158 171 157 140 141 176 164 148 157 147 163 150 159 161 125 129 155 159 147 141 159 139 126 157 155 142 169 147 127 129 131 165 135 144 154 119 145 140 138 135 145 154 119 142 154 124 143 146 114 127 137 131 139 138 127 133 140 120 129 99 106 125 116 115 119 134 88 131 100 127 139 118 110 111 101 119 125 91 127 118 113 125 111 128 136 136 107 125 115 111 105 133 121 114 97 96 116 106 87 124 119 101 117 122 114 94 106 106 126 103 87 111 113 117 110 85 95 111 119 78 105 100 106 102 89 97 110 102 84 85 79 105 90 81 106 84 102 104 87 94 75 86 91 103 83 95 114 99 95 96 105 109 96 94 91 84 105 94 98 105 95 95 116 91 87 87 105 88 85 78 79 99 100 93 83 98 91 88 85 77 93 93 82 77 104 107 76 79 78 68 68 102 88 92 76 86 63 79 82 88 104 109 98 115 117 161 205 304 349 394 416 431 397 448 437 451 452 564 320 293 319 305 310 280 307 304 262 238 284 270 242 273 264 293 268 268 291 285 279 253 267 287 267 280 280 259 287 274 261 283 266 250 277 317 303 319 304 343 435 366 424 418 392 368 393 376 374 384 931 417 376 293 272 240 248 232 198 195 203 156 177 175 163 147 164 164 143 123 133 136 102 124 118 102 97 103 123 99 103 122 111 130 109 96 106 120 120 128 146 132 502 274 973 758 746 485 399 392 404 392 286 211 153 121 101 122 106 92 100 97 114 107 72 69 79 108 123 464 72 71 67 78 64 76 66 62 51 70 55 60 64 47 56 54 75 68 59 72 70 134 62 72 75 76 137 53 71 80 82 145 77 56 76 77 101 72 77 90 104 90 77 78 96 91 178 77 83 85 111 103 107 98 74 115 107 103 109 145 109 130 132 126 125 92 112 119 127 150 122 115 132 116 108 125 125 143 140 147 162 139 130 139 139 159 141 143 144 158 132 160 167 158 125 145 138 162 198 174 157 164 192 194 159 152 165 191 195 176 198 192 151 182 169 225 213 182 198 184 204 242 211 219 221 250 203 209 190 207 219 194 170 205 183 328 181 186 170 177 324 124 110 87 89 341 66 75 100 62 226 85 107 182 88 101 55 40 58 49 68 52 43 47 69 73 57 42 35 65 60 35 55 56 61 75 68 79 56 55 56 54 59 85 94 72 80 82 82 75 100 73 66 93 82 80 82 77 84 75 69 76 51 83 83 69 80 93 84 84 81 94 113 70 88 85 84 65 74 85 70 68 83 79 60 48 62 55 61 90 61 57 51 163 59 56 55 48 47 54 46 38 38 54 35 36 36 41 27 44 39 35 41 30 37 27 36 36 24 22 28 30 23 23 36 28 25 16 23 38 24 22 19 26 27 18 25 20 28 27 18 21 29 22 23 21 17 27 18 21 22 18 25 20 22 30 22 19 33 29 24 23 29 19 23 37 19 34 23 25 16 17 24 17 25 27 18 20 23 27 17 17 26 13 26 13 14 15 25 14 19 28 23 26 24 21 33 29 16 24 16 28 25 27 23 23 28 26 25 25 24 28 27 38 26 32 20 26 31 31 31 33 25 19 42 42 28 35 38 44 41 47 41 31 31 40 28 33 43 47 53 39 22 51 42 42 46 46 45 39 51 44 42 46 54 56 31 53 41 57 50 48 39 49 43 32 33 42 33 40 46 49 48 33 56 46 52 55 49 36 55 43 49 34 46 39 36 51 52 51 33 45 31 43 36 44 39 34 34 37 45 30 34 42 37 40 24 32 42 46 52 38 48 40 59 31 36 32 41 29 33 25 17 20 23 19 18 21 16 18 16 9 12 9 12 7 9 11 15 14 14 17 14 18 13 11 14 15 9 18 12 17 7 6 12 16 8 7 9 13 8 5 11 10 12 7 11 10 8 11 11 10 12 16 15 13 16 11 11 10 17 18 26 11 10 7 19 10 16 12 16 11 11 16 13 12 11 9 6 13 6 9 10 13 13 16 6 9 7 17 10 7 13 6 10 33 7 7 6 17 12 9 6 7 13 23 5 9 12 7 7 5 16 11 11 6 11 3 14 9 9 10 5 11 5 10 8 8 8 14 11 6 12 10 11 10 8 13 6 6 10 5 7 20 25 14 13 6 15 9 9 8 8 3 7 11 6 9 10 17 8 10 5 5 5 10 6 5 8 11 4 5 1 5 12 12 19 6 10 12 7 7 8 5 8 8 11 8 9 4 5 4 6 10 8 10 8 5 7 10 5 4 4 7 10 8 5 6 7 3 17 9 7 4 8 8 6 9 11 6 9 9 8 16 8 5 7 6 9 8 8 10 11 19 10 10 7 12 8 11 8 13 8 13 7 9 7 12 12 10 6 8 5 9 8 8 8 3 11 6 10 10 4 6 9 11 7 9 15 10 8 7 8 7 12 13 7 5 6 8 8 12 5 8 8 7 12 5 8 7 9 12 6 10 6 6 9 6 4 6 12 13 5 9 5 12 5 8 10 5 6 9 5 10 10 3 9 9 5 5 4 8 9 10 2 9 6 6 6 7 3 7 5 5 0 6 4 2 7 5 4 6 2 6 2 7 8 6 6 4 4 7 5 9 7 
];
B = [
0 0 0
 332624 217514 115110
 967512 790456 177056
 405381 293842 111539
 346395 250383 96012
 263044 183140 79904
 202280 142069 60211
 181913 127901 54012
 224335 173336 50999
 233753 180342 53411
 764050 675809 88241
 316705 255474 61231
 296387 238990 57397
 283723 229920 53803
 269077 217988 51089
 530273 467430 62843
 331873 276917 54956
 321899 268015 53884
 294257 245950 48307
 305511 254352 51159
 470696 412310 58386
 348964 293105 55859
 343298 289439 53859
 338873 284698 54175
 327603 274760 52843
 443401 384443 58958
 342114 289184 52930
 367035 307790 59245
 342490 289186 53304
 350942 296231 54711
 418014 360597 57417
 365424 311910 53514
 365254 311631 53623
 351003 301146 49857
 387699 328966 58733
 398807 347806 51001
 369787 318014 51773
 594032 491675 102357
 356693 309014 47679
 397378 340152 57226
 571780 481443 90337
 392315 337471 54844
 522720 438873 83847
 360642 314217 46425
 385241 331618 53623
 547595 463652 83943
 394320 341308 53012
 527409 445642 81767
 392208 341465 50743
 508359 429922 78437
 402547 352183 50364
 506679 430101 76578
 409935 356886 53049
 505637 429446 76191
 387313 337955 49358
 533734 453794 79940
 485973 414361 71612
 378872 333705 45167
 493442 421746 71696
 343919 306734 37185
 100424986 96337010 4087976
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
73 265 0 0
20 27 0 0
29 86 0 0
31 65 0 2
28 59 1 0
32 75 1 1
79 82 5 6
291 111 10 7
120276 130 16 7
888835 160 35 13
1818285 194 91 24
3537569 237 164 57
6009165 304 1331 362
9918714 430 5174 1960
14373179 706 5469 2772
17702591 1624 5756 4060
16779423 3496 8733 7678
13053275 6545 13403 12962
7830926 9988 19476 19142
3262013 14454 25396 25439
862667 19291 30710 31075
150197 25948 36641 36759
51269 34586 42533 43179
51174 43652 49607 50352
57291 53373 57214 58113
64917 63630 65093 66301
73306 73694 74568 74959
82678 83886 83377 84978
92313 94376 93570 94679
100450 103074 102106 103902
109418 113086 109727 112779
116407 120883 117862 119597
121750 127387 123432 125600
125144 130687 127686 128631
128010 132887 129111 131000
129187 133217 129716 130934
126852 132033 128575 129896
125919 128280 126117 126501
123527 125950 123650 125464
122073 123333 121621 123633
122516 122270 121436 122301
122589 122507 122015 122790
123563 124815 123580 125133
126215 126393 125934 127436
130559 130469 129656 131195
134042 133992 133635 134616
137368 137447 135797 138169
138067 138986 138325 139333
138328 139527 139165 140505
137246 138033 137405 138396
133143 133996 133427 134796
126459 127760 126978 128148
119267 120816 119219 120472
110398 112270 110763 112501
99933 101529 100895 101308
90262 92220 91231 91796
81292 82742 81409 83379
73184 74489 73547 74129
66190 67214 66493 67872
60306 61244 61367 61318
55787 56684 56366 56743
53945 54399 54586 54557
48947 49443 49695 50113
46901 47067 46634 47710
44796 44553 44774 45503
44244 44049 44107 44580
43423 43862 43564 43955
44941 45563 44414 44692
43115 43377 43385 43393
42349 42108 42164 42857
40921 40988 41099 41293
40103 40307 40437 41295
38188 38540 38265 38605
35746 36145 36034 35798
31393 31703 31826 31920
28652 28801 28264 28723
24480 24012 23986 24133
17902 17778 17619 17757
14519 14446 14154 14449
10971 10932 10955 10844
6409 6477 6488 6510
4178 4185 4483 4365
237 279 227 260
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
