P17702 [HackerEarth] There are n+2 people sitting in a line, numbered from 0 to n+1. Some K distinct people with numbers ranging between 1 and n (inclusive) have letters given to them. The role of people wit
普及
题目描述

There are n+2 people sitting in a line, numbered from 0 to n+1. Some K distinct people with numbers ranging between 1 and n (inclusive) have letters given to them. The role of people with letters is to give their letters to one person sitting adjacent to them. At the end of this procedure, let X denote the sum of the numbers of all the people who have letters. Find the number of possible ways that X can equal a given number, T, modulo 10^9 + 7.

Note, if a person has two letters, count him/her twice.

Input:

The first line contains three integers, N, K, and T, in that order.

Next line consists of K integers, the numbers of the people who have letters.

Output:

Output the answer to the problem.

Constraints:

1 ≤ N ≤ 2000
1 ≤ K ≤ 2000
1 ≤ T ≤ 4000000
1 ≤ Number of everyone who has a letter ≤ N

SAMPLE INPUT
3 1 1
2

SAMPLE OUTPUT
1

Explanation

In order for this to work, person 2 must pass the letter to person 1. So, there is exactly 1 way.

输入格式

见题面

输出格式

见题面

样例输入
1073 536 287420 351 949 383 114 672 49 652 173 620 570 640 228 167 358 692 905 55 876 197 596 483 50 810 275 878 755 639 14 36 406 379 935 748 160 611 571 946 699 61 676 749 654 1002 732 856 948 1028 563 903 141 1010 586 665 775 1058 237 1055 787 7 846 694 2 374 90 386 247 220 89 847 566 245 855 560 75 806 123 945 411 1065 743 757 995 273 698 281 898 284 486 354 319 823 994 174 99 795 511 349 965 985 80 47 282 307 39 1043 136 334 46 891 834 731 270 496 133 1004 94 15 947 939 490 429 175 298 851 244 953 144 936 921 543 625 970 456 246 890 219 537 737 746 101 594 1052 493 871 440 111 16 325 364 797 590 668 391 809 578 179 1064 155 821 764 290 826 269 312 497 1038 68 768 451 211 256 800 704 952 969 633 463 894 788 170 866 53 224 798 726 122 200 1007 1032 196 71 1015 321 162 778 718 448 747 575 989 188 659 344 330 774 517 701 112 156 182 607 86 460 204 40 512 929 623 515 62 773 591 450 861 428 1008 555 941 209 260 697 458 230 74 241 222 293 887 238 983 785 805 276 553 679 405 647 545 21 820 613 401 955 120 508 627 840 685 782 389 548 288 84 562 1025 366 362 149 925 444 38 724 700 794 488 127 495 291 103 609 608 883 728 1062 906 585 315 30 433 593 1051 18 629 51 13 424 918 313 587 189 128 105 368 253 387 926 802 1014 913 696 968 756 205 569 392 882 546 261 556 722 754 192 892 687 10 168 134 249 107 158 714 677 588 841 54 558 34 911 693 1009 434 66 720 498 763 328 980 649 599 37 884 1005 920 963 739 413 385 744 902 741 738 345 827 251 592 191 885 886 73 930 940 742 242 300 1059 264 52 365 750 423 531 91 977 1042 412 771 44 478 808 421 979 1020 552 88 897 549 621 489 169 733 287 670 716 216 359 1037 335 618 661 974 1026 706 829 938 1 310 5 390 183 455 879 457 452 616 859 186 360 712 664 978 725 641 177 958 341 65 48 683 567 960 630 400 954 964 137 838 233 523 919 642 453 828 6 868 481 308 1060 102 198 839 262 147 184 145 910 634 904 402 956 373 961 266 337 124 306 23 780 786 278 770 227 64 1046 110 967 1029 203 171 848 407 784 194 815 26 752 837 187 667 781 982 597 872 326 818 248 398 532 682 231 323 305 984 201 580 121 577 916 727 544 644 937 740 425 81 327 807 417 606 987 268 998 681 125 962 686 153
样例输出
0