TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3051
  • 题目
  • P3051浇花
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

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

    输入格式

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

    输出格式

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

    样例输入

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

    样例输出

    Sample1:
    4
    Sample2:
    1