1 1 2 1 3 2 4 3 5 5 6 8 7 13 8 21 9 34 10 55 11 89 12 144 13 233 14 377 15 61 16 438 17 499 18 937 19 1436 20 2373 21 389 22 2762 23 3151 24 5913 25 964 26 6877 27 7841 28 14718 29 22559 30 37277 31 59836 32 97113 33 156949 34 25462 35 182411 36 27873 37 21284 38 49157 39 7441 40 56598 41 6439 42 6337 43 12776 44 19113 45 31889 46 512 47 3241 48 3753 49 6994 50 1747 51 8741 52 1488 53 1229 54 2717 55 3946 56 6663 57 169 58 6832 59 71 60 693 61 764 62 1457 63 2221 64 3678 65 5899 66 9577 67 15476 68 2553 69 1829 70 4382 71 6211 72 1593 73 784 74 2377 75 3161 76 5538 77 8699 78 14237 79 22936 80 37173 81 619 82 37792 83 38411 84 7623 85 4634 86 12257 87 16891 88 29148 89 4639 90 33787 91 38426 92 72213 93 11639 94 83852 95 95491 96 179343 97 274834 98 454177 99 72911 100 52788 101 125699 102 178487 103 34186 104 212673 105 246859 106 459532 107 76391 108 535923 109 612314 110 1148237 111 176551 112 1324788 113 151339 114 1476127 115 1627466 116 313593 117 194159 118 57752 119 251911 120 39663 121 291574 122 331237 123 622811 124 95448 125 718259 126 81377 127 799636 128 88113 129 887749 130 975862 131 1863611 132 2839473 133 47384 134 2886857 135 2934241 136 582198 137 3516439 138 498637 139 41576 140 54213 141 95789 142 152 143 95941 144 9693 145 15634 146 25327 147 4961 148 3288 149 8249 150 11537 151 19786 152 31323 153 5119 154 36442 155 41561 156 783 157 42344 158 43127 159 85471 160 128598 161 21469 162 1567 163 2336 164 393 165 2729 166 3122 167 5851 168 8973 169 14824 170 23797 171 38621 172 62418 173 1139 174 63557 175 64696 176 128253 177 192949 178 32122 179 22571 180 54693 181 77264 182 131957 183 29221 184 161178 185 19399 186 18577 187 37976 188 56553 189 94529 190 15182 191 19711 192 34893 193 5464 194 4357 195 9821 196 14178 197 23999 198 38177 199 62176 200 1353 201 63529 202 64882 203 128411 204 193293 205 32174 206 225467 207 257641 208 48318 209 35959 210 84277 211 12236 212 96513 213 18749 214 115262 215 13411 216 128673 217 14284 218 142957 219 157241 220 3198 221 16439 222 19637 223 3676 224 23313 225 26989 226 532 227 27521 228 2853 229 3374 230 6227 231 961 232 7188 233 8149 234 15337 235 23486 236 38823 237 6239 238 4562 239 181 240 4743 241 4924 242 9667 243 14591 244 24258 245 38849 246 6317 247 45166 248 51483 249 96649 250 148132 251 244781 252 392913 253 637694 254 1367 255 63961 256 65328 257 129289 258 194617 259 32396 260 22713 261 5519 262 28232 263 33751 264 61983 265 95734 266 157717 267 253451 268 411168 269 664619 270 175787 271 8446 272 184233 273 192679 274 376912 275 569591 276 94653 277 664244 278 758897 279 1423141 280 218238 281 1641379 282 1859617 283 35996 284 1895613 285 193169 286 288782 287 481951 288 77733 289 559684 290 637417 291 119711 292 757128 293 876839 294 1633967 295 25186 296 1659153 297 1684339 298 3343492 299 527831 300 3871323 301 4399154 302 827477 303 5226631 304 65418 305 529249 306 594667 307 1123916 308 1718583 309 2842499 310 456182 311 3298681 312 3754863 313 753544 314 45847 315 799391 316 845238 317 1644629 318 2489867 319 4134496 320 6624363 321 1758859 322 8383222 323 114281 324 849753 325 96434 326 946187 327 142621 328 18888 329 16159 330 3547 331 1976 332 5523 333 7499 334 1322 335 8821 336 1143 337 9964 338 1117 339 1181 340 2298 341 3479 342 5777 343 9256 344 1533 345 1789 346 3322 347 5111 348 8433 349 13544 350 21977 351 35521 352 57498 353 9319 354 66817 355 76136 356 142953 357 21989 358 164942 359 186931 360 351873 361 53884 362 45757 363 99641 364 145398 365 24539 366 169937 367 194476 368 364413 369 558889 370 92332 371 651221 372 743553 373 1394774 374 2138327 375 353311 376 2491638 377 2844949 378 5336587 379 8181536 380 13518123 381 21699659 382 35217782 383 56917441 384 92135223 385 14952664 386 1787887 387 1674551 388 3462438 389 5136989 390 8599427 391 13736416 392 22335843 393 3672259 394 26812 395 369971 396 396783 397 766754 398 1163537 399 193291 400 1356828 401 155119 402 1511947 403 166766 404 1678713 405 1845479 406 3524192 407 5369671 408 8893863 409 14263534 410 23157397 411 3742931 412 269328 413 412259 414 681587 415 193846 416 875433 417 169279 418 144712 419 313991 420 45873 421 359864 422 45737 423 4561 424 5298 425 9859 426 15157 427 2516 428 17673 429 2189 430 19862 431 2251 432 22113 433 24364 434 46477 435 7841 436 54318 437 62159 438 116477 439 178636 440 295113 441 473749 442 768862 443 1242611 444 211473 445 145484 446 356957 447 52441 448 49398 449 11839 450 61237 451 7376 452 68613 453 75989 454 14462 455 9451 456 23913 457 33364 458 57277 459 9641 460 66918 461 76559 462 143477 463 2236 464 145713 465 147949 466 293662 467 441611 468 735273 469 1176884 470 1912157 471 38941 472 195198 473 234139 474 429337 475 663476 476 192813 477 856289 478 14912 479 87121 480 1233 481 88354 482 89587 483 177941 484 267528 485 445469 486 712997 487 1158466 488 1871463 489 329929 490 221392 491 551321 492 772713 493 132434 494 95147 495 227581 496 322728 497 5539 498 328267 499 33386 500 361653 501 39539 502 41192 503 8731 504 49923 505 58654 506 18577 507 77231 508 9588 509 86819 510 9647 511 96466 512 16113 513 112579 514 128692 515 241271 516 369963 517 611234 518 981197 519 1592431 520 2573628 521 416659 522 299287 523 715946 524 115233 525 831179 526 946412 527 1777591 528 27243 529 184834 530 21277 531 26111 532 47388 533 73499 534 12887 535 86386 536 99273 537 185659 538 284932 539 47591 540 332523 541 38114 542 37637 543 75751 544 113388 545 189139 546 32527 547 221666 548 254193 549 475859 550 7352 551 483211 552 49563 553 532774 554 582337 555 1115111 556 1697448 557 2812559 558 4517 559 281776 560 286293 561 56869 562 343162 563 431 564 343593 565 34424 566 37817 567 72241 568 1158 569 73399 570 74557 571 147956 572 222513 573 37469 574 259982 575 297451 576 557433 577 854884 578 1412317 579 226721 580 163938 581 39659 582 23597 583 63256 584 86853 585 1519 586 88372 587 89891 588 178263 589 268154 590 446417 591 714571 592 116988 593 831559 594 948547 595 17816 596 966363 597 984179 598 195542 599 1179721 600 1375263 601 2554984 602 393247 603 2948231 604 3341478 605 628979 606 397457 607 126436 608 523893 609 65329 610 589222 611 654551 612 1243773 613 1898324 614 314297 615 2212621 616 2526918 617 4739539 618 7266457 619 125996 620 7392453 621 7518449 622 149192 623 7667641 624 7816833 625 15484474 626 233137 627 15717611 628 1595748 629 17313359 630 189917 631 1753276 632 1943193 633 3696469 634 5639662 635 9336131 636 14975793 637 24311924 638 39287717 639 63599641 640 12887358 641 76486999 642 89374357 643 165861356 644 255235713 645 4219769 646 259455482 647 263675251 648 52313733 649 315988984 650 36832717 651 35282171 652 72114888 653 1739759 654 73854647 655 7559446 656 8141493 657 157939 658 8299432 659 8457371 660 1675683 661 113354 662 178937 663 292291 664 471228 665 763519 666 1234747 667 1998266 668 323313 669 2321579 670 2644892 671 4966471 672 7611363 673 12577834 674 2189197 675 1476731 676 3665928 677 5142659 678 888587 679 631246 680 1519833 681 215179 682 173512 683 388691 684 56223 685 444914 686 51137 687 49651 688 1788 689 51439 690 53227 691 14666 692 67893 693 82559 694 15452 695 9811 696 25263 697 3574 698 28837 699 32411 700 61248 701 93659 702 15497 703 19156 704 34653 705 5389 706 442 707 5831 708 6273 709 1214 710 7487 711 871 712 8358 713 9229 714 17587 715 26816 716 4443 717 31259 718 3572 719 34831 720 3843 721 38674 722 42517 723 81191 724 12378 725 93569 726 15947 727 19516 728 35463 729 54979 730 9442 731 64421 732 73863 733 138284 734 212147 735 35431 736 247578 737 2839 738 25417 739 28256 740 53673 741 81929 742 13562 743 95491 744 1953 745 97444 746 99397 747 196841 748 296238 749 49379 750 345617 751 394996 752 74613 753 46969 754 121582 755 168551 756 29133 757 197684 758 226817 759 42451 760 269268 761 311719 762 58987 763 3776 764 62763 765 66539 766 12932 767 79471 768 9243 769 88714 770 97957 771 186671 772 284628 773 471299 774 755927 775 1227226 776 1983153 777 321379 778 234532 779 555911 780 79443 781 635354 782 714797 783 135151 784 849948 785 98599 786 948547 787 147146 788 195693 789 342839 790 538532 791 881371 792 141993 793 123364 794 265357 795 388721 796 65478 797 454199 798 519677 799 973876 800 1493553 801 2467429 802 396982 803 2864411 804 3261393 805 612584 806 3873977 807 4486561 808 836538 809 532399 810 1368937 811 191336 812 156273 813 34769 814 19142 815 53911 816 7353 817 61264 818 68617 819 129881 820 198498 821 328379 822 526877 823 855256 824 1382133 825 2237389 826 3619522 827 5856911 828 9476433 829 15333344 830 2489777 831 17823121 832 2312898 833 213619 834 2526517 835 274136 836 28653 837 32789 838 61442 839 94231 840 155673 841 24994 842 18667 843 43661 844 62328 845 15989 846 78317 847 9436 848 87753 849 97189 850 184942 851 282131 852 46773 853 32894 854 79667 855 112561 856 192228 857 34789 858 22717 859 5756 860 28473 861 34229 862 6272 863 451 864 6723 865 7174 866 13897 867 2171 868 1668 869 3839 870 557 871 4396 872 4953 873 9349 874 1432 875 1781 876 3213 877 4994 878 827 879 5821 880 6648 881 12469 882 19117 883 31586 884 573 885 32159 886 32732 887 64891 888 97623 889 162514 890 26137 891 188651 892 214788 893 43439 894 258227 895 31666 896 289893 897 321559 898 611452 899 93311 900 74763 901 16874 902 91637 903 18511 904 11148 905 29659 906 487 907 3146 908 3633 909 6779 910 1412 911 8191 912 963 913 9154 914 1117 915 1271 916 2388 917 3659 918 647 919 436 920 183 921 619 922 82 923 71 924 153 925 224 926 377 927 61