A = [
487002 467420 2448379 529710 518792 521531 507200 537490 528241 534268 553273 531541 545629 542834 540647 542061 538020 545107 549601 541267 543279 545487 546643 547181 577249 1374156 1413886 1440852 2238242 2265382 2317595 2340377 2344385 2406965 2400061 2381678 2361047 2325147 2289633 2248509 2223417 2208409 2181789 2160041 2152619 2110565 2075136 2067551 2024528 1990004 1966071 1923167 1913959 1899968 1866687 1832451 1816645 1804720 1761369 1719756 1704851 1679428 1657754 1632258 1613544 1595545 1567416 1539147 1514286 1483387 1455863 1434577 1406972 1385663 1368892 1342294 1316818 1296085 1265568 1237513 1213165 1193927 1168527 1143871 1127707 1101365 1077529 1047683 1023152 1003732 978440 957620 938048 919687 900231 883360 864571 850146 831938 812029 797318 778635 760363 743995 728705 714391 698745 684906 671907 657719 643071 627999 615863 602892 589514 577782 566338 553013 542288 530350 518755 506447 494293 484491 473646 463634 453729 442529 432728 425101 414723 406421 396667 388317 379346 370775 362485 355007 347913 340011 332651 325455 319051 310915 304691 296387 291801 286981 278894 272835 267174 260927 254919 249069 243028 238477 232423 227176 222046 217398 213005 207919 203491 199112 194038 189411 184519 180442 177365 173716 170029 166174 162995 158169 155940 152421 148316 145852 142838 139140 136364 133444 130897 128164 125415 122661 119501 118061 114775 113066 110270 107813 105580 103440 101623 99059 97199 94803 92676 91028 88937 87577 85486 83922 82217 80495 78738 77119 75574 74302 72288 70552 69501 67666 66333 64930 63522 62389 61224 60050 58958 57313 56356 55326 53736 52787 50970 49783 49167 47707 46321 45303 44871 43648 42652 41771 40923 39649 39530 38201 37470 36926 36330 35585 34916 34386 33751 32523 32032 31634 30731 30057 29464 28898 28335 27787 27241 26661 26059 25524 24936 24702 24016 23106 23081 22713 21740 21464 20894 20778 20086 19662 19491 19229 18474 18112 17800 17320 17012 16698 16420 15887 15481 15372 15164 14698 14561 14219 13710 13608 13017 13032 12792 12348 12119 12042 11796 11525 11311 10967 10647 10610 10296 10124 9846 9824 9553 9471 9332 9043 9009 8951 8447 8557 8063 8061 7947 7778 7526 7481 7298 7173 7111 6972 6550 6651 6526 6192 6433 6078 6057 5934 5726 5592 5516 5505 5195 5307 5023 5055 5128 4872 4776 4815 4649 4455 4493 4449 4244 4223 4082 4081 3955 3913 3909 3816 3723 3667 3494 3574 3459 3503 3301 3248 3320 3152 3083 3090 2977 2959 2867 2871 2789 2804 2750 2639 2581 2659 2598 2559 2512 2336 2431 2347 2304 2321 2219 2238 2100 2100 2044 2061 1998 1967 1986 1951 1783 1874 1749 1816 1808 1835 1685 1694 1694 1689 1701 1561 1551 1600 1598 1520 1444 1457 1554 1439 1478 1418 1495 1412 1358 1329 1320 1297 1290 1264 1305 1295 1232 1208 1168 1149 1159 1140 1109 1071 1029 1061 1086 1058 1058 1072 1006 1044 1009 982 1032 977 901 948 901 888 842 889 836 894 832 816 816 823 798 861 776 783 795 761 700 721 742 769 725 736 771 678 719 745 713 738 697 669 705 689 633 727 633 621 635 634 614 602 651 637 578 592 645 580 621 567 569 578 606 573 576 556 596 600 518 526 525 520 486 522 536 507 479 489 465 456 476 457 503 490 497 509 434 462 462 451 452 454 423 419 434 445 444 385 415 387 395 373 380 405 414 389 413 387 383 385 383 366 431 399 386 395 357 367 367 399 398 365 365 313 349 374 339 346 332 347 341 328 308 331 319 345 326 342 310 303 327 289 321 316 335 264 311 300 289 284 272 290 309 278 302 262 295 324 295 259 289 266 245 303 293 265 276 291 273 268 296 282 270 281 298 253 283 208 255 234 259 275 270 267 247 257 239 211 233 257 223 249 236 224 235 244 225 246 229 203 246 218 256 223 235 239 222 224 185 203 221 242 226 212 226 239 226 244 207 233 207 199 183 240 190 202 195 181 213 184 178 167 195 189 218 194 202 176 190 180 163 167 170 202 181 171 156 191 186 189 193 150 157 159 178 174 170 173 171 157 169 168 176 174 147 172 189 164 181 169 145 186 156 148 184 140 161 142 157 153 192 139 152 172 167 146 162 173 157 169 167 159 162 131 164 157 158 151 159 148 172 163 170 153 141 141 126 119 131 146 133 154 135 125 128 126 123 133 143 141 111 145 129 122 146 113 136 126 134 101 123 104 123 121 119 129 122 124 120 116 129 113 122 120 99 104 110 101 115 122 113 81 102 95 94 96 99 102 89 102 100 93 110 101 114 107 99 107 101 99 95 88 100 96 94 100 112 104 93 98 99 90 84 93 96 83 100 105 84 77 74 81 81 83 92 85 86 91 104 83 98 100 89 74 101 97 68 84 76 74 89 83 91 85 78 86 89 80 87 74 76 96 76 71 75 103 81 84 72 76 81 73 91 82 66 69 91 72 86 89 62 73 73 67 87 82 71 65 82 70 72 75 52 76 72 73 70 66 59 68 60 60 65 62 71 56 67 39 56 51 92 66 91 78 79 74 73 89 66 72 75 79 75 67 61 69 60 59 51 57 64 59 56 51 63 45 72 46 45 41 56 48 50 50 58 41 49 50 52 72 54 56 42 36 68 48 52 50 50 58 65 48 46 53 53 48 52 46 53 42 33 62 40 41 44 35 38 47 45 46 41 52 38 44 40 39 30 34 39 40 48 42 39 37 38 43 52 48 39 29 28 43 32 49 35 38 39 39 42 42 43 37 35 40 33 38 28 41 27 34 39 31 36 39 40 40 29 26 49 57 44 42 36 34 39 44 27 27 48 34 22 37 40 21 31 27 27 31 40 24 24 32 27 26 32 28 27 26 17 34 27 20 23 32 30 30 23 21 27 31 26 28 27 21 27 25 27 33 23 24 23 22 21 20 25 25 13 25 27 23 26 21 37 33 32 30 40 33 35 50 33 39 25 32 34 20 25 22 23 21 23 23 26 18 28 31 24 14 23 30 20 25 23 27 23 18 21 23 27 14 18 20 23 23 22 26 20 19 19 16 19 17 21 21 22 19 19 23 20 26 18 24 15 15 18 13 18 27 26 31 21 27 27 16 114 109 96 97 137 99 126 135 118 117 116 112 98 112 88 58 24 34 19 13 15 24 19 21 17 14 14 8 21 23 21 18 14 15 17 20 19 20 18 14 16 19 10 21 11 16 23 21 23 19 24 18 16 11 21 13 15 24 13 18 16 24 17 31 12 21 13 10 11 16 14 17 31 23 25 14 12 19 18 16 14 21 14 14 15 13 15 17 17 14 14 13 23 21 18 13 11 20 15 21 11 8 14 11 15 14 11 16 17 16 18 23 15 16 14 18 141 37 23 14 9 17 11 13 16 17 15 15 12 12 15 12 17 10 7 13 10 13 17 3 14 8 8 12 19 8 15 16 15 10 12 12 14 6 13 15 9 8 12 9 13 13 13 16 7 9 10 12 7 10 10 18 9 16 8 9 7 7 5 7 7 4 10 7 4 12 3 8 4 12 10 16 12 7 16 11 18 14 11 11 12 10 13 13 9 12 16 7 19 11 9 14 12 8 7 6 10 6 14 11 15 7 7 6 10 12 9 13 9 12 9 7 12 7 11 9 10 11 8 5 6 13 8 4 6 13 7 9 5 9 7 4 7 5 4 4 6 11 6 11 12 8 15 7 4 11 8 12 14 7 7 10 8 12 9 8 10 10 7 7 9 4 8 20 10 23 5 11 6 3 10 12 4 7 8 6 6 5 5 6 7 6 9 4 7 6 8 4 11 9 8 6 7 7 8 16 9 7 8 7 6 10 6 13 23 16 21 20 23 18 24 14 15 10 10 9 18 8 9 10 9 6 7 7 6 11 6 4 7 7 7 10 7 7 4 9 6 3 7 1 10 5 7 9 16 7 20 13 15 23 16 22 19 14 14 13 15 7 8 25 14 11 10 11 13 11 12 11 9 6 4 3 5 5 9 3 1 2 6 1 4 3 2 10 4 4 8 6 7 6 5 6 1 8 3 3 2 4 4 7 6 3 4 4 5 5 7 4 3 7 9 5 5 1 3 0 1 4 3 7 4 5 3 5 7 6 5 6 3 2 1 5 5 3 6 4 8 7 6 3 4 6 16 22 25 15 14 7 26 17 9 9 6 5 1 10 3 3 4 4 5 4 3 4 6 6 3 8 1 2 2 4 7 6 5 6 5 3 5 2 7 8 8 12 10 11 11 11 6 10 12 10 8 7 2 5 4 5 5 5 5 7 7 9 16 3 1 9 6 4 6 6 3 3 9 6 4 3 4 4 3 9 9 1 6 3 0 3 2 3 1 2 2 4 3 1 3 2 5 1 3 0 0 1 2 4 3 6 5 2 1 2 4 3 1 4 4 3 3 3 1 1 3 2 2 1 2 4 1 1 5 0 2 6 2 1 2 3 2 2 2 2 2 1 2 3 4 3 1 2 7 5 3 2 11 2 3 4 4 2 3 1 3 3 3 3 6 3 3 3 2 4 2 1 3 4 2 4 0 0 1 2 2 4 2 2 3 6 2 4 5 4 3 3 6 0 6 2 2 2 1 6 5 0 0 0 1 1 1 4 0 2 1 3 4 3 4 4 1 3 2 4 4 3 2 2 0 5 4 3 2 4 7 5 3 3 2 2 4 1 1 4 3 1 1 1 0 4 3 1 2 3 0 0 5 2 0 4 4 3 4 3 2 2 8 3 3 5 4 4 6 3 6 5 0 3 4 6 5 4 3 5 6 3 1 4 4 2 4 5 6 5 0 5 2 2 2 1 3 0 4 1 4 4 5 6 8 9 7 4 2 5 5 10 9 2 1 3 3 2 2 4 1 2 1 0 1 1 1 2 2 3 1 0 1 1 1 1 3 0 2 2 1 0 0 0 2 0 1 2 3 3 1 1 3 2 4 0 0 3 2 0 1 1 3 2 2 1 1 4 3 1 1 1 1 0 2 2 
];
B = [
0 0 0
 1157392 778280 379112
 580305 384763 195542
 1271611 901293 370318
 1118955 787350 331605
 599348 424166 175182
 1490463 1097192 393271
 668602 482732 185870
 1237498 925470 312028
 1289363 961045 328318
 376263 279718 96545
 2154571 1648322 506249
 678054 517827 160227
 292354 222812 69542
 1126124 880748 245376
 448640 348296 100344
 154112 119678 34434
 1233228 970734 262494
 121157 94391 26766
 113546 89153 24393
 57275 45698 11577
 41573 33590 7983
 28744 22396 6348
 1912241 1503315 408926
 169527 132807 36720
 205246 162610 42636
 1908563 1513831 394732
 289150 232363 56787
 177922 142419 35503
 2762039 2199545 562494
 304738 246278 58460
 320723 261816 58907
 2020573 1631508 389065
 405816 334351 71465
 2355190 1914761 440429
 563344 466560 96784
 512999 425943 87056
 4193557 3462623 730934
 918122 767340 150782
 1456677 1220932 235745
 4263499 3532185 731314
 1524262 1277521 246741
 1857534 1554532 303002
 3183390 2640991 542399
 1056738 888763 167975
 1322436 1105661 216775
 3495955 2915028 580927
 1229828 1029650 200178
 256188 213911 42277
 6592396 5539002 1053394
 257999 215721 42278
 900871 755538 145333
 9429928 7979487 1450441
 763682 642387 121295
 7 6 1
 14964050 12761437 2202613
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
9 37 0 0
2 6 0 0
2 11 0 0
3 25 0 0
1 23 1 0
10 26 391 13
805 40 1146 98
7611 42 1432 318
36807 57 1917 598
133400 78 2747 1112
323429 132 3244 1728
683305 227 4442 2856
1126303 402 6066 4583
1534941 787 8740 7577
1552160 1643 12868 11834
1259406 3043 18884 18379
798067 4741 26186 25786
431988 7130 35551 35408
214278 11454 46551 47171
114630 18456 59524 59341
87730 29571 73672 73688
95130 43543 88296 88586
113315 64472 106204 106664
133510 90364 126380 127276
156146 120236 149553 149706
180827 153711 174663 174822
207015 187303 200814 201073
234009 218490 229260 229155
257862 246718 253059 253473
277558 270292 273287 275973
293201 288230 291059 290982
301831 300254 301939 301633
307879 307722 307296 308408
311014 310990 311348 311988
313341 312718 312233 312808
314249 314778 314547 315337
314578 315220 316287 314935
317886 318316 317486 318529
321207 322100 320533 320381
323491 324438 324446 324958
328695 329566 329613 330534
337763 337931 337338 337109
346743 347233 347276 347264
359560 359935 360958 359319
374081 375243 374362 375148
391783 392270 390451 391612
407769 408666 409450 408871
424131 424604 424472 424567
438868 439223 438233 438118
450040 451077 450457 451157
456720 457752 458443 456827
459448 460525 458776 459109
455138 456932 456199 455337
447728 450279 449047 448936
433711 434908 433282 434196
415912 417755 416123 416886
392297 394016 393978 393947
364078 366665 366330 366045
333306 334307 333924 334354
302810 304055 304593 304820
273957 274092 275368 274881
249007 250715 249827 250125
223573 224318 223894 223688
205941 206451 206471 206434
193383 194350 193924 194132
187124 187498 186023 187027
184538 184902 185276 186545
184297 184128 183211 183927
176164 176839 175892 177059
178959 178636 179056 178923
174050 175023 173957 173845
164241 163481 164025 164045
152913 152769 152930 152726
131016 131887 131479 131744
110223 110544 110894 110493
89911 89651 89821 89261
65992 66518 66201 65930
42003 42220 42040 41922
31757 31225 31255 31342
22115 22045 21987 21948
12352 12104 12186 12119
5470 5525 5526 5293
238 248 217 239
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
