A = [
995373 920311 6431246 736304 686413 692933 661810 809471 914498 955481 1010986 1294985 1476898 1412219 1719961 1838987 1682710 1795116 1884312 1869987 1795122 1230501 1095543 998548 787215 1630899 1650198 1789510 2706933 2716843 2774667 2822607 2851049 2907538 2920068 2892573 2809437 2781522 2745537 2681514 2690263 2682782 2650894 2667030 2640588 2577737 2552040 2502576 2424299 2406409 2382288 2334031 2330697 2320384 2282658 2270157 2228540 2178663 2144507 2114312 2064573 2053175 2034122 2000372 1987284 1968085 1922364 1901296 1866760 1817602 1802054 1774631 1743768 1733240 1715802 1686904 1670912 1647179 1602884 1583936 1561742 1526325 1513336 1498178 1466254 1454446 1437913 1403511 1388499 1365284 1333828 1318831 1301714 1272706 1263717 1248905 1222387 1209068 1193264 1165213 1153847 1133107 1107493 1097259 1080028 1062423 1053262 1035228 1016582 1001225 984776 962972 955030 937104 918262 908183 895332 877800 866058 854309 835216 822584 811119 793536 786452 776186 760251 747817 736796 721509 711859 701987 687588 675519 666179 655854 646566 637604 623968 613542 602238 592780 583504 575865 563018 555128 547633 536161 529876 519607 511151 501972 494361 485069 478082 470394 460737 454899 448862 437325 434956 424517 417259 410766 403908 395534 390789 385358 377796 372599 366373 358132 354160 348454 340677 335523 330515 322929 319075 313973 308394 303026 298249 291364 287256 282752 278175 274020 269053 265010 260371 255982 250985 247695 242268 237864 234058 230974 227249 222941 218717 215114 212175 208054 204131 201056 197492 193739 191071 187128 183689 181756 177503 174280 172348 169049 166215 163971 161252 157615 155715 152732 150419 147647 145525 141603 140199 137173 135355 133237 130644 128549 126306 123939 121988 120489 118452 116279 114031 111839 109947 108168 106269 104860 102733 101335 99648 97543 96231 93895 92871 91572 89396 87525 86966 84848 83796 82716 80576 79753 78774 76738 75255 74095 73184 71881 70493 69301 68065 67330 66451 64940 63820 62838 61326 60700 59845 58385 57755 56797 55580 54708 53296 52333 51944 51252 49631 49204 48088 47685 46874 45741 45863 44497 43548 43313 42322 41055 40950 40227 39825 38871 38052 37563 36647 36088 35405 34939 34644 33783 33373 32552 32170 31689 31538 30543 30357 30076 29095 28918 28193 27576 27433 26927 26516 26243 25825 25474 25116 24474 23871 23519 23288 22934 22557 22183 21514 21565 21139 20678 20540 20016 20004 19630 19285 19021 18537 18156 18115 17566 17738 17031 17013 16876 16767 16459 16163 15851 15570 15098 15042 14907 14583 14410 13992 14229 13941 13666 13397 13244 12698 12278 12684 12436 12251 12130 11831 11491 11529 11290 11225 11093 10884 10729 10656 10473 10457 10208 10244 9971 10011 9682 9652 9629 9673 9550 9044 9105 9106 9060 8827 8672 8530 8470 8404 8406 8319 7920 7902 7862 7828 7708 7630 7673 7518 7200 7289 7182 7105 6968 6916 6840 6563 6594 6513 6321 6468 6235 6187 6159 6226 6069 6069 6118 6042 5852 5992 5646 5558 5597 5696 5696 5393 5645 5438 5405 5203 5448 5154 5274 5125 5130 5016 5099 5097 4947 4752 4895 4845 4855 4628 4657 4700 4592 4781 4643 4320 4252 4118 4276 4297 4205 4244 4284 4160 4140 4199 4021 4079 4140 3850 4019 3778 3952 3795 3811 3645 3706 3658 3601 3688 3512 3476 3754 3675 3410 3544 3380 3400 3510 3402 3588 3592 3518 3303 3345 3368 3393 3100 3153 3331 3351 3448 3312 3295 3207 3236 3267 3238 3144 3000 2975 2870 2899 2926 2928 2810 2946 2867 2883 2821 2837 2879 2858 2982 2815 2797 2788 2806 2684 2749 2652 2682 2675 2786 2625 2713 2651 2653 2595 2561 2662 2699 2576 2567 2518 2543 2522 2547 2691 2449 2409 2691 2465 2576 2524 2515 2518 2411 2407 2371 2475 2223 2293 2222 2422 2267 2273 2247 2206 2365 2280 2083 2334 2293 2332 2362 2238 2062 2178 1984 2176 1903 1994 2124 2032 2109 1944 2108 1961 1996 2059 1916 1999 2014 1961 1859 1949 2044 2026 2019 2060 2031 1891 2016 1838 1901 2041 2006 1862 1899 1899 1830 1810 1891 1752 1785 1762 1919 1768 1767 1772 1856 1801 1862 1909 1844 1844 1835 1924 1802 1958 1677 1759 1665 1665 1667 1864 1786 1726 1762 1729 1651 1685 1727 1678 1593 1639 1725 1700 1633 1615 1525 1661 1722 1736 1636 1629 1544 1658 1671 1674 1583 1602 1705 1661 1665 1722 1625 1537 1591 1639 1463 1569 1541 1580 1528 1486 1527 1495 1427 1525 1523 1556 1520 1598 1680 1490 1545 1362 1560 1607 1502 1575 1500 1366 1448 1505 1497 1397 1416 1470 1461 1364 1520 1574 1410 1423 1400 1438 1277 1563 1464 1420 1498 1352 1370 1436 1483 1446 1580 1431 1533 1537 1357 1454 1432 1387 1402 1321 1271 1462 1274 1282 1282 1326 1328 1209 1235 1253 1278 1314 1274 1341 1352 1220 1229 1289 1406 1321 1329 1276 1334 1242 1282 1239 1341 1247 1200 1272 1265 1207 1210 1186 1111 1079 1074 1073 1018 1113 1204 1149 1207 1168 1137 1201 1162 1127 1145 1073 1109 1063 1040 1071 1006 1135 1044 1009 1000 915 1018 1090 1082 1110 1029 952 1026 1018 1065 1059 959 910 1076 1005 952 1036 949 995 946 1032 974 874 907 826 929 989 999 959 928 967 1000 897 975 945 1046 1016 1010 1051 1012 976 948 905 971 1025 893 922 1024 905 935 846 944 854 969 923 910 958 1021 988 992 910 845 936 925 915 883 975 946 854 867 851 918 1017 860 901 866 866 899 898 831 838 821 794 764 776 808 694 792 797 812 854 786 873 774 803 850 820 842 805 824 772 802 911 884 813 905 886 863 738 827 979 845 879 783 799 857 708 794 785 779 872 800 807 728 764 724 741 684 703 734 633 695 684 616 682 665 654 677 659 628 677 684 719 755 793 776 762 766 695 697 642 652 694 758 696 681 772 713 618 653 613 573 546 609 542 634 623 650 678 647 623 592 583 540 519 586 594 597 601 669 596 579 628 583 572 574 587 517 600 567 594 544 613 558 604 597 548 664 565 541 590 532 553 628 530 532 606 515 611 664 478 468 590 570 569 619 488 559 457 530 498 534 546 498 461 457 462 465 509 447 476 478 387 465 396 398 491 493 419 440 488 399 446 396 504 410 374 395 436 479 380 407 431 449 487 434 401 415 432 386 395 465 462 482 429 363 409 497 394 394 365 390 384 422 423 463 457 466 504 414 486 473 464 471 446 452 426 393 465 366 421 436 502 464 444 545 484 461 418 439 477 349 433 436 398 476 414 399 371 359 402 401 397 419 441 406 369 323 329 422 395 339 395 425 423 400 332 375 365 310 313 297 306 298 356 313 360 319 312 355 357 342 366 338 383 341 273 314 299 221 309 277 294 220 237 221 269 232 284 252 267 281 274 342 343 314 333 242 332 303 317 314 310 317 352 347 308 314 316 349 362 416 324 395 289 359 341 323 349 322 362 372 362 361 341 345 306 313 321 312 366 327 338 334 454 383 369 362 324 340 348 290 326 362 290 312 311 306 310 210 354 304 310 315 302 246 292 281 355 295 303 385 287 282 353 278 280 274 234 246 298 251 246 260 291 215 270 310 258 239 236 243 261 244 311 257 287 320 294 293 323 278 371 323 344 294 248 312 305 276 249 251 292 240 309 264 196 253 284 257 305 262 222 270 224 191 178 214 223 225 200 220 193 267 209 179 242 223 241 276 245 246 235 205 249 251 283 245 205 230 213 221 224 195 200 248 208 171 196 166 206 216 205 192 211 199 231 211 200 263 199 249 207 264 212 210 231 195 241 201 186 254 251 252 247 265 299 259 285 262 279 272 286 217 218 242 240 216 248 235 266 242 249 231 232 252 258 182 238 257 194 210 219 207 221 242 225 183 239 253 251 245 286 238 256 205 220 197 220 208 218 144 156 167 165 182 180 212 182 189 180 192 195 191 202 172 179 186 223 192 229 178 200 198 186 190 246 161 186 186 229 188 240 199 197 221 256 177 267 248 221 258 250 216 198 230 207 182 186 166 163 178 172 174 180 179 155 170 185 220 148 163 196 158 165 143 154 126 146 156 162 165 189 158 137 162 184 227 208 182 177 214 225 206 212 168 231 205 155 147 195 223 196 227 209 246 204 207 220 260 219 273 274 228 213 275 196 183 218 238 243 211 244 211 243 215 167 216 222 219 202 194 163 236 186 202 220 269 248 287 272 250 252 184 229 257 284 188 245 251 237 244 167 208 243 215 257 201 203 221 217 246 239 259 278 255 174 208 218 169 224 223 198 176 206 149 187 158 179 187 234 208 162 172 183 133 218 170 203 125 150 208 187 147 169 149 155 137 142 159 104 146 190 155 164 143 225 171 134 129 172 135 133 188 188 187 206 161 159 135 184 150 144 160 154 144 219 179 158 214 154 202 209 195 173 201 193 189 196 140 172 169 146 162 193 133 149 130 133 154 143 179 174 158 177 137 199 214 172 205 153 167 185 165 210 171 204 166 206 206 197 217 194 253 312 244 194 229 212 246 228 250 289 258 290 379 294 262 307 288 286 308 343 360 272 274 298 299 409 288 340 336 290 310 383 302 285 304 312 264 307 249 310 263 240 264 284 207 223 277 222 222 186 207 180 195 189 161 191 169 184 168 164 189 129 229 179 183 170 160 186 154 152 134 185 130 184 164 185 191 159 179 139 149 176 168 141 162 140 159 128 162 139 122 141 171 152 150 182 144 143 170 121 137 120 125 143 148 146 140 114 113 130 213 181 244 161 178 224 219 205 147 174 215 169 154 261 225 179 169 206 157 153 201 109 181 146 155 150 95 122 121 99 108 103 143 74 121 98 125 100 129 130 139 159 106 131 116 138 119 102 126 112 117 147 140 118 119 143 143 145 126 112 126 107 117 112 116 121 151 127 121 144 100 150 160 131 118 151 81 110 115 104 150 131 144 110 84 105 95 76 109 101 100 83 92 105 92 156 108 102 88 129 108 110 134 120 110 80 121 96 133 120 100 137 83 83 116 127 126 113 113 89 141 118 123 95 104 94 143 149 108 135 118 147 150 142 126 137 68 151 89 96 96 63 89 94 108 123 113 99 148 80 120 99 112 101 61 93 100 101 75 77 69 82 78 87 82 116 90 92 80 64 74 76 62 40 58 49 53 42 56 62 57 74 64 51 48 53 41 56 52 50 44 54 57 58 71 52 65 67 81 100 48 80 37 61 62 84 95 84 103 85 74 84 69 101 61 84 90 93 56 96 112 88 113 85 100 100 90 51 86 60 55 101 45 53 49 46 49 80 
];
B = [
0 0 0
 124917 71450 53467
 96265 52790 43475
 129068 73201 55867
 140716 76648 64068
 102280 57216 45064
 107725 64497 43228
 120790 71362 49428
 163161 99322 63839
 115966 73657 42309
 143272 86387 56885
 169358 103849 65509
 147497 93219 54278
 273853 176515 97338
 67767 43891 23876
 519078 337916 181162
 66853 44315 22538
 53230 34104 19126
 107057 74691 32366
 63436 43468 19968
 78996 54089 24907
 75880 55198 20682
 138840 98260 40580
 61491 46177 15314
 85980 64490 21490
 131063 98621 32442
 54688 44025 10663
 308449 233508 74941
 239050 183551 55499
 59243 49261 9982
 185188 166793 18395
 91786 80257 11529
 195015 141244 53771
 202476 175430 27046
 93199 81095 12104
 528345 360943 167402
 75953 65426 10527
 176977 160396 16581
 44923 40334 4589
 282432 226314 56118
 94226 86188 8038
 109230 99791 9439
 194715 147505 47210
 132537 121493 11044
 318005 291726 26279
 77774 68442 9332
 175232 134474 40758
 646591 595004 51587
 367088 326953 40135
 192174 155888 36286
 432907 406061 26846
 182445 168255 14190
 103139 91177 11962
 297907 227966 69941
 564379 506821 57558
 188906 170292 18614
 158619 130541 28078
 234356 209233 25123
 239194 219592 19602
 758029 705195 52834
 120660799 111101293 9559506
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
276 1803 44 96
67 250 17 31
125 344 35 46
231 454 61 58
278 435 65 100
296 524 2474 395
1246 796 6021 1499
15470 898 7370 2834
240551 1170 9498 4539
662042 1835 12665 7050
1071270 2388 14437 9846
1680060 4174 18799 14143
2276953 7325 23558 19785
2860173 14895 32564 29526
3026626 29583 45252 42422
2892441 56643 66477 64495
2262140 95103 92505 91935
1404544 142769 125007 124108
686327 206658 164619 163636
315574 282873 203404 203466
225222 357359 240803 241921
233729 419422 276305 278936
261993 454608 311418 311861
293842 472893 340995 340341
326604 481018 368993 368504
363016 486711 396235 394401
399142 491841 426909 426155
436181 505725 456843 458176
473311 521764 489278 490169
510138 548453 524501 526502
548388 578085 559986 557154
584107 610258 594301 592462
618237 640877 625079 624797
646532 674534 657155 658033
675660 700634 686860 685530
702414 721885 712487 711935
725836 742409 734723 734081
744355 760495 752993 753386
763410 779011 770577 770037
776882 792503 785076 785452
789801 805728 797492 798059
801032 812670 805222 806740
806746 818802 811986 811290
804621 819225 811067 811762
797554 807961 804103 802891
786073 791591 788864 789060
752061 761267 757558 757948
708435 713368 708684 709348
651627 657208 653970 654636
591432 594793 591842 592662
518320 522006 519289 521656
454103 457605 454671 456048
396037 398493 398378 398390
352177 351991 351415 352851
322351 321448 322966 322330
301187 302553 300882 301327
287798 288154 287608 288117
283235 284186 283379 283411
288830 288608 288289 289570
297120 298967 297712 298513
317760 319211 319392 318967
325124 324753 325020 325726
330370 331494 332521 331107
330185 330237 329488 330414
316944 317366 317879 317432
292682 293642 292104 292201
246744 248315 246746 247258
196677 197643 197640 196363
143472 145035 145103 144096
91570 92571 92611 91773
39850 41586 41375 39859
6722 6887 6755 6644
3 2 2 3
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
