TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3051
  • Problem
  • P3051浇花
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    n 个非负整数排成一行,每个数值为Ai,数的位置不可改变。需要把所有的数都恰好等于h。可进行的操作是:对任意长度的区间[i,j]中的每个数都加1,i 和j 也任选,但要求每个数只能作为一次区间的起点,也只能作为一次区间的终点。 也即是说: 对任意的两个区间[l1, r1] 和[l2, r2], 要求: l1≠l2 并且r1 ≠ r2.
    请问有多少种不同的方式,使所有的数都等于h.输出答案模1000000007 (10^9+7)后的余数。
    两种方式被认为不同,只要两种方式所实施的操作的区间集合中,有一个区间不同即可.

    Input Format

    第1 行:2 个整数n, h (1 ≤ n, h ≤ 2000)
    接下来n 行,每行1 个整数,表示Ai (1≤Ai≤2000)
    30%的数据,n, h <= 30
    100%的数据,n, h <= 2000

    Output Format

    第1 行:1 个整数,表示答案

    Sample Input

    Sample1:
    3 2
    1 1 1
    Sample2:
    5 1
    1 1 1 1 1

    Sample Output

    Sample1:
    4
    Sample2:
    1