A = [
35890 10885 13461 226823 4757 5712 5046 4822 5257 5220 5981 5279 5335 5359 5339 5281 5051 5305 5036 4999 4956 4946 5261 6300 40124 39720 40371 40963 43106 80567 80393 80482 80993 80840 84418 84628 83786 84149 83111 83267 83170 83048 81972 81907 81361 81643 81085 80476 80531 79913 79446 79119 78786 79056 79059 78275 78229 77301 77658 77696 76424 76257 76407 75008 74963 75281 74793 73812 74451 72597 72682 72139 71908 71417 71015 70674 69739 68907 68357 67723 67328 66403 65918 65855 65208 64161 63743 63391 62618 61779 61003 60562 59791 58487 58110 57613 57062 56222 55782 55040 54278 53872 52819 52717 51596 51186 51058 49862 49262 48265 47485 47285 46352 45879 45382 44434 44444 43454 42738 42555 41623 41417 40334 40179 39299 38922 38161 37501 37011 36686 36053 35856 35253 34227 33999 33503 32855 32745 32376 31833 31118 30615 29965 29862 29320 28823 28529 27993 27712 27444 27066 26542 26133 25685 25111 24841 24592 24426 23845 23368 22910 22988 22307 21980 21792 21679 21223 20758 20459 19801 19604 19584 19141 18931 18560 18208 18072 17742 17377 17273 16757 16423 16246 16216 15933 15808 15372 15341 15107 14683 14420 14054 14191 13769 13537 13308 13223 12984 12918 12450 12348 12078 11782 11949 11721 11542 11351 11112 11044 10739 10731 10564 10507 10074 10004 9974 9654 9572 9364 9430 9239 8853 8890 8675 8533 8468 8231 8118 8197 7998 7878 7681 7630 7660 7381 7251 7115 6944 6960 6963 6759 6553 6568 6454 6320 6428 6125 6144 6009 6149 5728 5789 5637 5590 5580 5395 5390 5325 5230 5238 5105 5053 4866 4817 4757 4747 4628 4690 4648 4526 4404 4328 4363 4287 4172 4128 3987 4093 4014 3948 3899 3928 3807 3813 3683 3560 3572 3628 3492 3362 3296 3393 3191 3165 3268 3192 3141 3082 3097 3032 3027 2882 3004 2928 2860 2830 2666 2691 2584 2655 2588 2563 2583 2626 2565 2459 2414 2344 2441 2443 2247 2302 2291 2314 2258 2207 2353 2096 2126 2092 2114 2044 2054 1967 2057 1905 1964 1995 1927 1958 1903 1778 1850 1821 1828 1771 1803 1820 1807 1702 1710 1627 1742 1650 1692 1644 1581 1559 1637 1638 1503 1566 1527 1479 1463 1475 1484 1423 1481 1396 1428 1463 1391 1394 1333 1358 1314 1332 1338 1306 1327 1256 1318 1238 1334 1304 1178 1197 1213 1299 1263 1228 1189 1203 1182 1208 1135 1160 1137 1116 1120 1142 1111 1111 1068 1088 1060 1096 1078 1115 1020 982 1041 1064 982 1032 972 1041 984 966 1002 981 1026 952 1010 880 897 927 914 935 956 896 913 934 845 937 936 873 901 840 835 873 937 875 873 875 925 817 815 864 865 863 869 858 833 804 826 791 884 848 809 805 871 797 802 839 765 795 789 793 785 748 775 802 823 792 815 794 810 773 791 800 718 766 750 762 808 751 763 768 743 787 751 785 762 751 759 775 770 739 782 681 736 769 685 774 742 785 726 764 733 712 763 722 725 725 736 714 781 754 753 712 697 728 716 741 747 693 757 704 707 725 675 729 672 732 648 716 696 673 727 673 688 709 681 688 689 685 678 659 704 675 664 688 603 674 679 643 674 652 683 655 700 658 682 655 650 635 679 723 664 660 651 664 610 681 635 652 632 657 636 598 718 666 676 667 618 640 708 642 670 674 635 666 628 637 658 664 631 675 618 662 621 642 670 696 749 692 656 640 651 695 651 620 613 664 640 648 673 619 615 595 616 627 567 638 651 678 589 618 608 649 662 627 599 610 637 627 621 606 638 617 601 598 631 639 640 585 617 617 600 571 593 614 595 608 639 620 627 634 627 577 590 572 634 613 674 644 616 613 588 610 635 623 613 595 578 547 600 606 601 618 618 593 612 577 588 601 616 616 600 593 611 649 563 573 568 652 607 604 611 623 589 656 596 642 600 635 660 635 601 584 580 583 623 677 545 566 597 626 635 571 619 574 602 605 698 630 552 665 607 651 607 620 610 628 588 584 598 632 577 617 583 596 588 551 606 607 596 588 581 625 593 611 594 597 561 570 585 607 622 592 534 577 561 549 607 540 610 583 587 577 592 648 568 569 617 557 564 597 582 592 557 633 599 620 611 597 552 600 539 552 616 563 533 573 624 608 583 581 568 529 558 576 551 587 541 537 549 573 600 618 554 558 581 587 591 542 616 584 644 590 586 571 543 531 557 563 549 557 550 610 579 587 546 579 575 566 526 563 568 565 556 558 537 544 583 539 556 537 587 567 517 597 554 535 567 522 514 531 548 510 561 575 589 546 570 555 517 559 547 569 540 560 549 550 532 558 586 585 514 559 597 552 552 579 549 612 548 568 596 542 574 552 569 536 537 548 586 534 535 540 519 518 545 597 547 542 554 564 537 557 561 531 517 519 552 539 556 546 593 532 574 560 553 562 614 555 603 527 579 537 548 507 562 531 532 564 544 566 557 574 550 593 565 556 537 534 554 538 531 552 528 606 564 529 527 539 528 544 592 538 496 531 484 514 548 525 540 542 562 547 522 519 493 523 571 548 522 529 535 516 548 544 515 509 509 522 531 573 511 547 515 506 497 505 545 486 543 534 461 479 495 533 502 482 504 510 520 526 534 496 518 514 533 530 521 516 530 552 503 537 474 518 522 492 521 552 502 518 549 538 534 530 533 505 505 520 483 522 528 537 497 515 518 521 518 487 487 521 500 461 499 530 471 477 478 491 495 479 545 519 476 442 520 493 486 472 478 540 487 525 529 512 543 502 526 506 488 512 539 505 491 519 495 495 491 485 476 496 517 498 516 523 495 476 499 467 518 482 495 472 437 515 509 504 442 479 507 521 491 511 490 464 510 479 453 546 469 489 487 518 472 489 513 484 499 542 493 526 514 519 502 496 486 536 511 474 463 492 478 460 483 554 508 529 461 549 507 508 519 550 477 540 500 520 503 515 537 521 506 475 470 510 458 490 482 496 497 506 493 481 488 488 453 501 502 521 486 478 495 499 489 508 499 492 474 476 496 497 508 463 477 459 500 461 447 491 551 478 479 463 529 491 453 494 487 479 511 481 505 485 454 459 479 448 482 496 492 488 445 454 451 459 461 449 422 478 463 460 441 430 471 439 449 436 439 442 428 447 447 431 407 419 430 423 453 432 467 471 455 474 474 507 460 439 464 470 455 427 458 437 442 423 464 433 480 456 430 442 432 472 438 428 438 471 435 467 459 435 464 437 448 479 474 466 425 516 411 510 513 495 473 530 445 496 415 494 494 443 464 496 454 471 456 440 438 446 490 464 448 468 476 477 481 448 462 479 482 506 452 515 486 429 454 448 477 457 480 478 439 435 448 453 449 461 408 445 441 447 494 424 429 456 456 466 437 449 446 448 494 440 419 418 433 408 437 413 406 444 467 477 409 492 464 453 438 427 467 438 431 444 433 423 451 399 420 466 433 424 445 436 449 431 444 402 455 439 447 446 437 420 387 437 437 447 419 426 429 422 432 474 420 405 404 472 428 460 442 410 429 435 415 393 416 466 391 407 376 414 403 383 446 432 427 391 412 402 419 411 382 420 448 459 432 379 364 425 440 426 423 439 401 438 402 384 414 397 453 419 404 437 387 403 419 396 387 436 412 446 373 412 417 418 375 447 395 425 459 431 380 411 398 392 452 447 364 411 406 458 436 452 407 405 404 408 409 356 428 405 400 413 384 384 428 417 429 396 363 410 413 389 417 420 371 370 398 406 383 399 404 395 387 385 382 388 408 386 431 392 443 384 426 402 410 376 402 402 404 377 406 372 421 387 433 444 369 370 384 396 399 398 375 378 357 429 397 372 393 422 400 415 402 423 395 375 376 376 389 386 411 380 391 411 401 374 365 359 407 390 387 394 404 356 366 378 396 404 352 370 409 418 365 362 407 362 352 384 344 363 371 384 372 395 409 380 406 404 351 369 367 412 371 406 375 418 387 377 397 374 415 368 402 401 357 406 353 489 429 408 405 373 397 399 398 433 396 388 376 403 414 366 371 403 363 385 399 401 384 400 363 372 375 368 411 421 435 387 385 401 374 410 401 377 354 387 364 376 411 398 415 395 355 372 364 392 378 387 386 365 347 380 383 387 386 390 370 381 379 392 372 377 368 357 393 368 373 365 365 363 360 353 356 381 373 411 409 348 377 361 313 380 332 385 353 318 368 370 352 371 342 340 356 395 367 374 354 359 381 387 371 382 394 382 379 366 378 360 358 367 397 350 423 356 334 369 348 374 384 337 345 374 379 347 373 398 361 382 349 362 379 348 391 383 351 349 372 382 342 355 348 406 389 346 382 357 398 341 371 371 366 367 380 373 371 341 360 362 359 371 399 331 359 357 353 349 356 380 384 375 397 366 373 359 368 368 358 383 356 383 370 356 357 371 374 405 382 329 346 333 369 343 355 353 341 391 361 387 349 340 357 381 371 342 384 376 402 352 358 353 367 343 337 359 349 361 341 369 347 381 359 381 333 359 338 351 358 352 319 349 381 365 365 365 343 364 381 380 349 376 331 382 376 334 333 357 357 381 323 363 351 329 330 331 363 348 367 385 360 345 351 333 358 336 339 340 358 340 360 332 364 319 359 370 333 342 322 350 352 337 337 361 359 317 313 301 349 338 328 364 339 305 333 325 354 333 340 307 360 358 341 358 346 319 346 343 349 326 318 299 334 303 305 297 307 287 301 344 309 322 306 316 323 310 332 299 330 301 331 295 334 350 312 358 308 377 338 327 351 338 327 362 317 282 313 366 348 312 348 334 319 296 339 303 313 342 341 339 322 305 299 335 302 308 299 327 312 274 300 341 326 338 304 344 296 309 323 335 322 309 
];
B = [
0 0 0
 4409 1557 2852
 2789 877 1912
 6613 2825 3788
 2602 911 1691
 2517 869 1648
 3746 1298 2448
 4472 1584 2888
 3193 1157 2036
 7383 2812 4571
 3497 1208 2289
 3638 1220 2418
 4822 1591 3231
 6847 2631 4216
 5946 1742 4204
 9169 3621 5548
 5459 1953 3506
 6900 2313 4587
 5381 1989 3392
 8320 3277 5043
 7005 2468 4537
 9213 4173 5040
 8620 3384 5236
 6241 2465 3776
 10296 4389 5907
 14544 5898 8646
 2038 916 1122
 33561 16376 17185
 1384 581 803
 2276 1281 995
 1716 781 935
 2720 1262 1458
 1249 509 740
 8313 4225 4088
 1634 611 1023
 2519 1601 918
 1491 761 730
 2457 1164 1293
 222 123 99
 10157 5372 4785
 3 3 0
 88 65 23
 439 307 132
 3264 2290 974
 306 209 97
 236 159 77
 368 276 92
 1037 726 311
 23335 12768 10567
 45 28 17
 407 295 112
 303 212 91
 476 330 146
 1756 1260 496
 28197 17062 11135
 705 513 192
 768 563 205
 1633 1268 365
 46844 36369 10475
 17115 13118 3997
 5152047 4021629 1130418
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
1 3 0 0
0 0 0 1
0 0 0 0
0 0 0 1
1 0 0 4
0 0 12 1
70 0 36 11
181 0 34 16
319 3 54 34
1269 3 60 33
6001 1 89 63
20510 9 104 96
43937 9 126 136
72545 24 158 157
90318 51 198 193
88928 104 268 258
66009 195 367 378
43754 360 493 562
24401 690 732 783
10902 999 953 1002
4907 1731 1302 1317
2790 2431 1581 1655
2629 3463 2238 2110
2911 4210 2803 2914
3927 5338 3602 3649
4499 5686 4407 4337
5107 6513 5214 5125
5906 6752 5886 5914
6950 7775 7198 7041
8284 8906 8512 8258
9517 10341 9763 9553
10921 11770 11115 11070
12470 13910 12676 12566
13971 15589 14458 14218
15307 17232 15958 15863
16653 18645 17598 17265
18126 20012 18783 18758
19241 21463 20218 20249
20752 22695 21842 21427
22376 23607 22902 23055
23330 24591 24325 23828
24254 25434 24679 24716
24787 26103 25513 25210
25573 26537 26229 26152
25777 26892 26792 26400
26242 27309 26678 26465
26436 27085 26758 26335
25541 26521 26570 26064
25210 26093 25405 25701
24647 25353 25165 24696
24241 24885 24448 24422
23465 24047 24072 23500
23306 23439 23612 23238
22959 23324 22983 22976
22807 22804 22998 22848
22605 22626 22845 22499
22515 22734 22908 22563
22648 23132 23014 22946
23831 23628 24019 23830
24317 24709 24657 24412
25527 25571 25748 25490
26257 26203 26780 26322
27405 27319 27474 27260
27368 27546 27608 27076
26286 26151 26744 26593
24558 24089 24625 24255
21408 21491 21606 21442
18178 17856 18442 17781
14226 14143 14708 14176
10518 10334 10592 10421
4844 4983 5013 4911
772 736 690 764
0 1 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 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 
];
