1000 1000 130 1 2 1
719730 265368 766225 978873 180882 759547 799075 652390 846784 103245 459582 527132 263286 875985 799682 891145 100193 88894 987389 957935 788555 838621 490241 492976 211689 983306 786624 536496 66529 302515 193420 648550 811429 619495 698831 327320 858313 113793 193509 179067 150461 885560 243848 852471 581570 325461 430354 777241 882948 316071 85705 694323 518730 916987 405523 13089 855503 652044 750860 686618 921096 740351 172480 355559 922176 210079 287800 549983 509057 54375 504900 433337 995935 923834 83592 933400 64830 368237 970893 20804 148548 680392 523481 841760 731829 971566 145442 984096 823015 72613 194861 301258 866656 242280 969531 738522 6094 963329 608191 331092 536418 230862 414192 888327 331090 430053 952223 637394 175666 453929 811110 350871 904179 259425 851918 334142 241765 613806 867094 219967 571026 28558 210630 406379 229383 701298 833729 546761 28019 853153 519282 562193 132151 179583 299612 899696 796862 535732 546066 952296 650863 54216 355760 861840 948372 988964 373678 893824 942925 272149 359312 947063 702350 901056 970643 108416 28498 448428 131708 255414 460576 772993 96132 668268 601255 323624 842105 454842 341135 387319 60782 974955 401752 585947 896355 212977 66061 173056 639966 228218 324434 882829 264924 946588 56984 539186 632434 400563 812424 187183 79860 548270 268594 631224 522809 701807 168253 425798 646376 785475 188878 375577 711198 562140 781922 743050 643932 115488 730994 2513 212692 318928 474395 582267 179052 893634 464223 777092 854213 130004 151647 22104 110352 933235 632684 419589 96617 153327 105377 941958 458910 262190 287978 453242 178702 37184 637167 752891 182021 130335 826408 267118 318275 515815 13004 339467 419736 926960 446405 879815 209481 257166 821076 331920 958077 353345 809694 46465 779376 42552 669919 602146 365912 343180 954583 912774 257927 836662 61826 50150 656127 742240 694979 124910 908946 866018 736347 517332 874115 331334 924001 6284 454748 180502 99175 253937 277450 991722 753750 631773 543605 892769 134107 635738 858848 205325 753381 772443 272710 704101 934465 537408 649777 63432 351014 204728 853572 44181 684817 500830 378729 88802 937850 713562 583713 666723 793623 166885 289096 922474 174666 696460 124640 48483 981718 32024 764671 339586 292537 551190 309699 849593 608669 200610 81992 92903 363673 566309 104382 739894 975050 269668 977433 31170 214710 576539 899922 464712 923636 434555 96165 522436 508069 813411 754252 91393 517748 954845 23580 116558 552707 267287 692731 82201 930235 7873 861089 71062 130460 389757 855031 693335 198709 949565 345819 523679 762651 509831 429840 118928 621674 501208 503316 573700 270057 277093 167775 950044 674704 524560 787318 994434 109287 245962 767704 546484 734251 101860 67033 29666 610855 541095 732962 79821 633378 520226 499206 467900 600449 990028 864444 23595 775886 632333 613700 420331 641239 433908 954536 790164 82371 514689 547348 150092 559736 472718 891224 277984 417781 936418 830392 340197 169594 550857 964595 55502 92968 268315 627456 710576 152138 931743 842769 624869 843516 851997 454225 942726 845697 998520 200295 437765 899737 78362 65089 300978 187431 207245 598671 260314 783146 205474 815166 644089 992641 901870 436625 700283 731117 979827 745887 602012 247012 585083 796542 769937 194211 684936 132274 484950 578306 123616 527149 609846 205317 832382 379045 656738 297814 727066 958864 977753 33693 391415 345636 637610 893463 124666 116223 557739 36951 714941 11592 91483 823375 123914 270728 744008 544468 575415 123487 88345 614416 523859 506590 391666 742136 827345 542652 285244 466282 65389 605487 352602 906210 641134 632840 188677 674825 636538 857317 740543 612840 745385 954159 945262 418499 831111 984838 69483 523183 887223 633552 162513 842617 351938 566998 981724 231156 231319 47375 12949 998275 693451 88860 708198 830526 955514 968291 183040 792644 741534 178341 565790 531945 131338 767680 918910 489190 847769 322891 772324 69103 480589 331822 522314 552527 322515 312635 691761 448171 62134 752938 940491 436420 516281 495632 481112 608962 444448 15989 72653 823203 148966 447495 80617 655886 885278 689722 329962 539955 650477 975863 283751 654411 270572 164734 511814 373485 522743 814329 720278 730944 228609 665074 828786 794142 647562 923157 155623 412099 660089 680022 2513 806453 903634 599177 894137 506557 840902 136631 251645 801113 733655 451718 498656 54012 858149 834413 719391 340092 24838 1125 444549 719966 299841 30934 486455 230872 478057 943815 493092 976724 938813 558852 132558 993891 649311 38584 86254 172057 430883 962780 359048 875477 994088 313255 296989 60643 384860 995275 7609 855207 623936 845548 997541 271501 698917 662540 739951 274302 479000 395712 718545 830968 347038 236011 56519 458237 982066 732887 974064 947804 587224 745455 309431 88776 185443 780653 379929 325265 549988 159960 158562 467694 359483 407715 723760 610076 896629 131825 689912 179273 424353 526443 268557 452369 674105 469575 583902 385451 59939 83046 637470 279446 224096 47012 901830 817342 817079 157457 178695 217524 845501 431621 388138 325396 800134 919401 854475 7917 867332 378990 97255 506245 332385 82933 919426 237989 759951 230498 403849 140272 705483 768448 393567 331329 759236 543046 567023 517976 705306 502903 912965 161898 554717 322898 380124 393144 471067 531901 474944 397535 920874 37275 803370 381882 14056 761511 848472 22918 232970 503340 132153 422929 817489 190054 548743 257087 814795 730373 108278 435935 457783 248714 878653 112071 202371 969709 95389 917082 747224 61025 10150 441479 349268 824628 569171 819607 195619 951549 930298 204217 61278 677915 264242 565392 477756 833535 551164 611384 841278 58106 762660 28023 956360 227644 620223 233269 6247 884695 830296 347773 861765 982859 771834 265971 79167 568004 528067 394815 235070 674159 503172 324959 840501 27903 317606 819157 585077 326335 57645 515088 493607 282312 555687 90766 743160 130666 984860 154392 231832 656739 447406 120844 901844 755652 24029 208775 727373 499618 440972 380180 246091 643500 149677 814974 702593 300675 371707 516193 735520 602858 2085 457325 415997 370604 436636 595233 375243 823301 932990 299915 837656 827017 567869 270894 614889 661778 753693 527186 797443 511962 441295 383867 652211 523131 273620 443815 404127 284180 359999 583212 605627 841816 172370 332483 102426 235763 204544 45932 719522 770041 344564 656290 998028 762162 470213 168013 927110 418739 484110 719914 518753 738947 965167 678548 146917 27211 165563 414830 817809 660251 719499 158469 207430 944842 210381 921707 839557 684457 549439 899667 365824 30119 472029 290441 281157 970583 261317 620320 746881 469853 267771 752234 880595 332315 952278 839619 573936 884836 780582 724056 440959 800872 544606 395159 476721 637687 97719 860133 866346 633697 15339 499997 407542 808780 356282 962338 277317 559661 318013 549171 409 853176 627962 929145 273287 524281 616510