1000
0 884800 491108 338370 157996 76815 792580 939010 437543 473985 715500 638102 91308 933712 536039 27966 708593 85920 668555 428805 419923 17699 54886 802663 352186 710108 256319 495438 617102 449341 647831 765898 603837 344207 453080 70129 968821 402133 420214 111576 588390 960216 794461 886790 241107 745764 884437 320814 375865 971099 824975 208356 882982 432750 142050 485859 563348 37492 854978 776384 428947 360695 155496 658841 375367 377399 846343 445058 128363 157280 662524 896092 114650 582005 756277 458116 364911 114468 795378 688661 329181 811405 270147 795619 401665 457347 462386 968062 252742 805681 810950 315616 516521 534995 496094 814313 768448 162625 611596 83252 91287 719771 603009 150134 125110 71347 251736 377592 109058 143971 905050 784903 982310 465143 683696 209185 948817 838425 420737 773269 351437 326638 791801 399286 638378 533290 963372 878111 785935 857193 465500 973598 324920 441816 844250 638448 426159 14625 515357 541787 381807 439593 712986 872807 900297 624515 324723 322792 367824 55736 597774 36869 546792 597245 439247 196493 608480 288169 256394 555851 332426 951934 350381 73327 542690 479271 590391 13484 970630 360176 926072 846969 999634 307439 120618 264953 388077 712458 754004 412163 343792 874974 28913 938023 5784 718764 405216 599600 445746 503981 614377 82408 495476 846412 63038 447145 429095 405427 353461 427275 596250 100764 590390 236925 801015 73756 7968 60192 377508 701156 198866 883251 113005 16809 569886 769515 576530 157011 437126 707061 157309 460121 804270 514310 909175 949464 417502 487592 219478 52464 625129 734995 250212 808017 419958 515117 48523 404045 473193 956283 770255 340931 897936 615018 326869 725816 251198 536904 986059 371985 148906 457620 586916 276446 598362 63302 627928 238029 172283 858655 492859 502385 593785 280905 545371 849337 856428 764336 450604 744470 542413 213923 513193 292689 488381 886280 597256 757742 22976 502194 483757 12709 476464 86654 571148 345432 325451 500269 414694 826463 984232 352345 591877 403890 214907 45514 144221 127118 922869 351293 832414 367073 200030 418383 178443 872758 907849 994605 224037 260745 403618 821413 700982 250339 276378 617297 469542 601865 744015 250618 498834 873335 411318 663547 812479 456502 393585 65187 573578 480715 207782 672488 203393 11070 199243 267151 616990 86319 578771 466201 386486 840539 952611 515992 965663 749038 915121 777223 673820 208113 796770 495590 344961 30815 286663 142337 504450 503233 784111 616240 954947 938547 429647 349385 74856 182075 387280 667600 918668 672246 368685 133081 35989 985657 58321 798771 791968 950806 739965 708897 907123 864167 614328 788535 512896 493114 190957 944766 287737 446141 481306 441989 400744 359219 260551 72670 855941 540279 682360 656344 48125 619539 99697 234737 959760 753970 746739 44079 604873 513836 563169 175495 188867 307363 698062 390721 994619 827506 884753 416267 949116 680835 749472 982898 816011 851213 818110 174399 14276 937706 851471 316655 94645 150706 83813 299784 585649 384001 312546 852985 763854 91419 109939 249393 979743 786353 691508 465229 853764 305451 608902 350690 450202 238626 404645 337228 346228 514420 329955 770094 512364 241564 947727 44498 160070 510820 765145 129634 106696 967262 430232 745659 651484 570568 338420 634721 398876 84292 214626 672704 730073 860008 938149 447987 991409 254659 637423 366651 827213 526468 25169 624281 813205 165894 856709 254925 31202 895621 366563 363282 165723 62406 896260 972242 573673 159532 588195 40619 374555 896429 437343 838540 418824 50074 90674 80201 910955 991195 603910 541118 692084 788207 457877 214498 951915 991909 247009 673375 64164 548372 805355 864007 693636 370131 824507 822551 281758 608354 439356 988313 91800 416431 256619 238770 536348 441492 223243 739614 381237 149868 272779 495998 823663 858236 334126 767912 586090 300689 780034 710870 498150 47225 600305 115646 391070 786710 697136 178289 415681 283703 639725 458589 48281 720739 371295 231249 888842 251485 885569 387493 355745 335920 295917 124469 93271 651549 542767 639314 778197 922650 372921 403747 630444 641310 205492 168744 772488 947150 844197 173133 353809 183133 147126 189922 111164 346665 831266 646318 678792 162112 841442 674880 912227 982920 11859 390890 697430 390383 903703 868894 437894 735586 344408 893765 572150 45974 404724 879274 303138 748777 403291 377008 211368 393640 482253 717919 954894 990527 300399 622876 400744 601065 550338 487464 385157 358441 374504 991718 270155 370004 260668 379520 315531 566841 542724 288949 899602 954033 145933 281468 452192 841881 606805 258028 55779 399555 333472 697575 310623 472992 115479 617254 990159 16341 67136 35763 634156 199728 665802 898627 561897 729225 919540 58924 646336 687652 770992 404735 748207 24848 384875 486421 958393 733414 303255 955639 622215 731164 401106 867601 821535 988566 991647 336420 950575 913143 452656 205804 196856 117679 89336 275759 690300 116508 793849 948254 265727 428573 457673 12736 780099 677107 484773 122692 309279 51585 555109 562392 329733 607001 51747 324130 294949 320839 442380 471515 514183 637550 738382 518983 459169 192957 721056 488178 191416 349543 396185 1288 461342 543356 242293 219864 21922 505741 668240 175228 253071 357654 600549 405820 736045 118282 181278 751511 761152 236803 224169 693809 969201 188824 162234 818746 596014 678890 372901 146776 790562 688064 811055 966688 449774 667339 936077 643731 408815 581985 613364 194136 279771 955878 333085 848406 51393 598990 587241 770705 558737 964960 246483 536333 698402 174334 105187 401556 8836 580018 387390 34101 402362 510433 23013 481450 657601 970509 355790 300150 511388 588880 934351 960254 677453 130857 554424 200756 698552 994967 839662 82593 644395 380062 918551 641970 811636 341726 341870 181336 338723 139401 680856 746665 685048 371753 474475 612012 869078 717081 47440 295306 663503 900409 43470 562406 166058 323770 300539 988052 258113 76191 670762 47459 352052 841702 817241 301479 866209 990018 395577 149377 604223 591772 316758 716863 347723 620753 316641 288333 793925 210420 708670 330484 619436 376102 26038 609985 740416 189830 767372 889245 260395 871933 841979 881929 238297 589748 778001 680726 251126 904207 628102 661968 703240 560880 977087 666490 509898 948099 796273 63997 480532 120254 390791 881364 487732 871464 515442 744648 542932 411344 387569 677678 360620 542780 298100 758738 537123 901830 539255 396614 315121 174482 433413 587633 258553 925831 665526 616728 364284 561103 379290 594676 801042 553841 97068 794528 852386 85900 48412 39720 230081 136568 731587 839244 782938 409829 411278 944606 17415 513502 924398 110566 566601 38152 413816 366832 673967 137393 121703 2869 188779 742697 452638 825494 352112 326884 560813 577038 348610 651629 193940 114846 322746 841508 130951 282464 654818 86238 241104 129676 237102 538398 702996 723632 599763 632668 852963 412495 735608 699185 636644 0