A = [
169944 133467 510792 142140 138700 131607 129383 129571 131298 129287 135196 147549 161301 179903 207373 226309 243995 268591 275358 278002 284493 282273 280942 281761 283686 312121 305673 299045 319267 268970 268734 260451 204864 207685 203226 202342 200497 194719 194818 191956 191142 188938 191317 192243 191015 193185 190524 189566 188504 185036 184366 183660 183687 183482 182381 181964 180414 180531 179548 178252 177745 176002 176709 174477 175060 173487 172613 170663 171236 169977 168120 167370 165838 165502 164904 163433 161885 159698 159449 157986 156536 154448 154162 152700 150812 150994 149743 147648 147027 145732 145173 143139 141878 140707 139677 138561 137555 134945 135127 133924 132708 130431 129379 128319 127366 126363 124910 124142 122717 121898 120169 119310 118757 116637 115049 115121 114221 112866 111785 111522 109754 108646 106704 107112 105106 103756 102633 101861 100693 99454 98570 97364 96782 95742 94970 93488 92410 91456 90284 90066 88810 87693 87483 86732 85359 84916 83327 82352 80941 79986 79335 78554 77535 76361 75035 75010 73988 73004 72199 71064 70202 69067 68578 67323 66203 65993 65194 64695 63037 62056 62346 61157 60434 59266 58661 57487 56895 55970 55104 55003 53489 53527 52625 51402 51447 50285 49854 49326 48444 47507 46804 46864 45893 45240 44911 44239 43497 42985 42239 41947 41459 40372 39411 39235 38909 37678 37730 36664 36317 36131 35482 34892 34038 33310 32755 32580 32182 31596 31260 31006 30400 29584 29821 29108 28806 28028 27608 27494 26911 26770 26429 25757 25692 25065 24313 24235 23837 23708 23672 22803 22463 22153 22174 21318 21248 20901 20411 20134 19743 20026 19320 19054 18873 18585 18019 17998 17353 17274 16828 16599 16353 16248 16012 15837 15544 15391 15051 14846 14653 14493 14246 13968 13857 13755 13449 13311 13452 13255 12494 12616 12760 12101 11946 12364 11984 11840 11153 11437 11967 11143 11481 10835 10617 10458 10114 10478 10041 9745 9732 9734 9589 9074 8817 8927 8748 8602 8505 8366 8086 8015 7628 7685 7610 7551 7531 7465 7214 7068 6894 6862 6921 6641 6411 6373 6288 6104 6325 5975 5877 5711 5792 5757 5558 5442 5488 5190 5408 5514 5666 5456 5239 5317 5446 5443 6407 6601 5273 4969 5211 5335 5144 5183 5324 4851 4953 4866 5327 4927 4674 4815 4687 4791 4690 6200 6108 5028 5244 4892 4577 4348 4097 3978 3683 3626 3679 4102 3919 3551 3376 3184 3073 3102 2882 2953 3158 3030 3034 3158 3196 3114 3046 3105 2930 3001 2941 2896 2801 2730 2914 2656 2759 2870 2718 2809 2780 2660 2560 2603 2606 2496 2729 2698 3002 2856 3086 2798 2851 2879 3211 2765 2692 2793 2509 2364 2831 2608 2491 2603 2745 2539 2521 2661 2703 2813 2426 2461 2295 2425 2467 2536 2339 2255 2211 2281 2232 2332 2279 2258 2202 2092 2062 2153 2198 1919 2082 1955 1933 1804 1843 1881 1827 1932 1819 1974 1878 1857 1896 1959 1890 1839 1716 1876 1807 1826 1750 1726 1750 1673 1632 1778 1747 1772 1677 1687 1781 1744 1704 1648 1687 1773 1575 1670 1651 1565 1644 1540 1577 1562 1577 1518 1595 1627 1571 1635 1569 1716 1662 1633 1646 1672 1718 1633 1734 1724 1453 1613 1568 1729 1625 1608 1683 1672 1628 1579 1651 1558 1539 1513 1588 1557 1587 1659 1541 1560 1610 1592 1499 1819 1540 1497 1464 1406 1483 1309 1451 1440 1558 1386 1666 1546 1608 1438 1427 1394 1333 1343 1363 1387 1437 1377 1295 1370 1190 1328 1203 1171 1126 1178 1122 1257 1180 1296 1196 1104 1142 1203 1176 1156 1215 1196 1222 1281 1227 1127 1149 1196 1225 1242 1182 1056 1064 1217 1095 1021 1057 1173 1206 1051 1145 1135 1105 1175 1333 1249 1328 1398 1442 1459 1308 1357 1242 1310 1278 1246 1381 1217 1194 1328 1272 1366 1265 1344 1673 1340 1259 1278 1275 1231 1510 1268 1297 1421 1320 1323 1326 1478 1354 1435 1186 1287 1177 1358 1413 1252 1153 1260 1296 1143 1156 1143 1174 1241 1142 1248 1310 1376 1215 1369 1157 1150 1183 1144 1233 1189 1156 1271 1110 1167 1131 1197 1124 1100 1113 1091 1169 1106 989 1130 1113 1132 1110 1078 1189 1157 1195 1052 1122 1163 1192 1165 1197 1342 1462 1634 1587 1910 1830 1817 1841 1926 1831 1836 1791 1695 1604 1754 1671 1614 1713 1551 1665 1449 1481 1404 1547 1614 2075 1880 1920 1573 1634 1610 1749 1628 1549 1528 1407 1397 1481 1483 1550 1274 1436 1677 1524 1573 1859 1762 1834 1477 1382 1282 1361 1657 1390 1483 1610 1463 1229 1453 1687 1513 1454 1522 1332 1272 1256 1435 1345 1216 1196 1060 1026 1141 1249 1306 1389 1197 1431 1438 1230 1314 1508 1562 1723 1671 2115 1946 2278 2308 1269 1188 1153 1252 1140 1261 1488 1859 1224 959 927 1020 1322 950 1066 981 980 1052 997 1105 979 982 946 921 992 934 1003 953 1171 1146 922 849 946 862 846 890 935 944 887 802 761 888 899 1005 955 1023 1073 1035 1017 998 972 969 1127 922 1021 1055 1045 1166 1127 1101 1208 1021 1081 1050 1105 1134 986 1093 1035 1081 1054 976 1007 1137 1207 1087 1121 986 1085 1062 983 1033 1011 1100 1019 1016 1125 1059 1205 1124 1334 1088 1055 1110 1022 872 878 882 900 883 598 540 634 761 569 556 603 574 579 557 549 584 575 576 513 529 708 818 850 827 918 917 789 754 784 814 793 815 872 1196 1006 1320 910 1247 843 785 918 834 865 944 849 790 712 755 1093 896 675 756 652 701 742 731 726 774 750 712 770 854 789 726 873 722 974 713 636 795 712 676 743 609 559 503 527 511 490 534 510 547 523 532 563 478 514 533 540 453 568 482 451 476 487 513 505 497 561 518 525 525 579 501 474 483 573 479 501 575 572 635 581 645 592 617 559 561 516 569 555 600 502 524 550 525 550 537 580 579 595 586 672 597 536 548 566 596 610 583 533 566 583 524 512 539 528 575 514 610 574 516 519 569 483 506 499 527 551 595 556 515 626 575 620 527 608 594 563 538 567 568 601 581 555 573 549 577 584 539 581 573 657 539 556 604 649 646 630 652 616 558 580 567 522 565 524 593 516 521 503 559 557 533 474 599 544 462 498 556 610 584 480 592 574 615 652 543 559 593 516 474 500 504 533 560 531 555 634 546 717 671 701 611 665 627 586 670 634 615 661 656 636 574 559 642 642 669 634 619 567 671 531 659 579 652 609 708 693 590 577 580 543 494 587 525 648 708 726 736 690 634 649 674 618 680 606 566 631 691 568 591 581 670 643 604 669 988 583 586 610 570 553 551 512 506 547 510 520 407 474 428 415 522 405 392 414 409 368 456 431 420 439 442 482 470 429 543 438 439 482 483 452 460 492 451 449 540 463 425 442 508 486 517 549 580 549 556 561 544 477 486 550 556 543 553 568 537 488 547 538 504 601 549 532 541 540 534 580 439 489 491 465 458 500 492 459 423 424 451 436 460 457 515 402 343 364 393 400 416 388 350 381 387 428 415 433 434 417 441 498 427 419 419 375 406 413 418 434 424 381 418 327 397 518 373 339 355 418 415 361 349 367 396 374 502 405 408 453 411 398 487 441 368 381 429 394 377 427 407 379 394 455 480 430 446 382 432 398 412 442 392 468 486 802 931 809 419 823 777 814 888 801 917 791 1023 1260 848 905 785 1022 1162 863 950 1228 950 1105 1075 913 959 1086 953 1272 1452 1239 1095 1139 984 1102 1276 1073 955 1070 947 1092 1147 1188 1193 1157 1064 1036 979 879 927 959 850 1034 1154 875 1046 1116 1070 1303 1054 961 870 806 984 737 721 1270 1142 1118 926 888 588 792 886 1023 1045 1086 1165 1200 1291 834 837 781 718 675 646 803 647 619 781 767 915 884 1271 1447 1287 1016 1214 1029 1229 1630 1181 1716 2524 1810 1634 1902 1520 1359 1436 1093 697 586 789 712 705 791 928 873 846 800 665 736 701 732 691 644 674 732 870 742 801 767 685 717 826 696 689 685 455 645 717 824 769 831 805 736 566 711 518 525 475 518 550 457 516 533 495 490 465 477 515 446 427 479 442 369 384 586 623 659 651 605 540 640 768 844 763 682 569 589 545 633 501 642 465 433 374 434 358 378 339 403 347 312 435 321 372 357 355 383 323 370 370 376 423 413 399 766 841 746 699 570 716 678 638 706 704 795 782 827 839 995 920 696 391 746 1012 682 730 719 773 843 878 999 787 706 617 689 588 415 376 359 419 592 420 380 394 404 372 409 359 396 441 378 405 367 379 359 398 358 380 351 336 323 419 344 340 382 349 330 317 356 310 304 313 318 334 319 388 321 334 387 377 366 378 374 375 313 333 365 338 332 297 309 346 335 603 363 346 314 321 303 314 323 346 429 388 305 326 346 406 369 421 336 350 335 373 363 346 360 316 328 374 336 351 318 318 377 329 349 419 367 346 330 350 434 382 395 411 340 316 324 297 337 358 325 324 384 296 339 325 316 279 331 279 287 312 295 312 329 264 290 299 282 255 273 265 244 263 262 290 272 225 314 241 244 246 279 253 287 293 308 345 296 261 325 237 282 307 282 269 271 282 287 304 305 317 301 301 316 321 297 280 292 281 282 281 359 335 342 388 389 316 412 299 401 361 343 415 383 355 372 436 395 402 414 382 413 419 427 352 367 376 425 374 368 369 400 391 410 377 385 398 420 328 335 397 504 379 367 360 356 1204 350 329 365 383 372 370 354 304 298 312 391 326 346 353 301 337 323 334 304 336 398 348 334 364 403 362 322 398 417 370 381 353 356 355 377 349 363 378 412 460 376 390 385 414 329 332 400 443 342 375 445 380 414 342 374 441 404 401 394 406 390 384 325 334 395 564 402 366 371 393 360 403 380 333 362 357 407 353 294 352 279 252 280 308 274 298 283 299 285 303 284 335 257 323 345 280 456 317 302 474 334 309 289 330 265 328 327 328 339 279 253 322 292 299 334 289 308 253 287 310 270 272 280 313 326 321 299 322 291 308 306 307 323 311 320 390 378 356 292 272 324 329 304 306 288 393 330 310 307 311 342 321 293 364 373 320 313 407 269 315 286 302 308 296 357 366 364 368 347 404 383 363 470 369 316 1026 333 387 361 363 365 392 376 338 329 330 270 383 388 389 349 349 368 352 314 385 330 343 339 340 317 292 304 297 286 342 310 323 346 323 314 284 302 330 379 411 393 360 337 371 325 347 378 314 306 356 
];
B = [
0 0 0
 237283 17170 220113
 252831 19837 232994
 264420 19933 244487
 390394 34400 355994
 237729 20712 217017
 815886 93923 721963
 383169 39613 343556
 248355 31028 217327
 244349 32636 211713
 114716 13494 101222
 92366 9874 82492
 64109 7832 56277
 55739 6114 49625
 94619 11567 83052
 90488 10235 80253
 78783 9044 69739
 215113 31210 183903
 156199 19483 136716
 142507 18882 123625
 112401 14296 98105
 122810 18987 103823
 117910 19774 98136
 90634 15281 75353
 112602 18808 93794
 86389 14631 71758
 161353 26903 134450
 132378 22211 110167
 102182 17375 84807
 127382 22948 104434
 99448 18209 81239
 127860 24513 103347
 124021 24606 99415
 112888 22720 90168
 151281 30820 120461
 128574 26395 102179
 150828 31927 118901
 305449 53016 252433
 143863 31234 112629
 163133 35602 127531
 292465 54415 238050
 159940 36022 123918
 281238 54813 226425
 151123 34656 116467
 168454 39702 128752
 283845 57869 225976
 178959 42138 136821
 282150 58218 223932
 177632 43818 133814
 299111 62530 236581
 168607 42291 126316
 325810 70848 254962
 162766 42851 119915
 316038 70963 245075
 153154 40647 112507
 341240 78764 262476
 332542 79947 252595
 163916 46372 117544
 334290 81431 252859
 138844 42227 96617
 15344683 4825909 10518774
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
19 17 1 0
1 3 0 0
10 8 0 0
19 8 1 0
17 13 0 0
38 18 0 0
110 21 1 1
488 37 2 1
4568 65 9 5
43722 79 11 9
142840 115 17 10
301821 160 35 29
471600 205 37 34
677340 415 79 71
835038 817 115 127
924109 1745 227 188
816694 3255 304 336
541399 5117 443 490
242969 7206 663 621
59472 9552 880 825
8175 11501 1043 1044
3125 13301 1242 1408
2825 13727 1472 1541
2690 12542 1610 1559
2429 9877 1712 1698
2437 7455 2163 1706
2317 5352 2046 1946
2381 4257 1906 1852
2251 3621 1859 1991
2224 3014 2020 1945
2538 3210 2173 2119
2444 2703 2276 2276
2851 2943 2332 2252
3183 3065 2459 2443
3050 3295 2682 2638
3163 3251 2916 2987
3678 3658 3315 3226
4076 3990 3696 3361
4138 4125 4138 3752
4348 4254 4212 4241
4758 5010 4748 4567
5391 5359 5399 5291
6052 6266 6242 6013
6818 7142 6766 6943
7627 7696 7588 7746
8809 8762 8731 8775
9851 9931 10044 9764
10893 11122 11002 10964
12258 12543 12354 12320
13725 13499 13799 13487
14920 14764 15240 14985
16098 16090 16177 16128
17017 17173 16884 16903
17805 17898 17919 18123
18407 18409 18732 18204
19211 19324 19370 19432
19966 19831 19986 19823
20465 20590 20614 20122
20985 21128 21921 21610
21232 21276 21205 21185
20991 21047 21204 21115
20751 20461 20273 20302
18666 18738 18838 18856
15556 15457 15540 15356
10991 10612 10766 10615
5519 5452 5466 5528
1870 1843 1925 1968
347 339 319 333
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
