区间加
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

牛牛给牛妹出了到简单区间加题，牛妹觉得太简单于是稍微修改了一下。

牛妹有个长为的序列。每次牛妹会选择这个序列中的一段区间进行区间加，但是要满足的条件：对于任意两次区间加的起始，结束位置各不相同。

现在牛妹问你存在多少种区间加方式使得最后得到的序列使得，由于方案数过多，答案对取模。

输入描述:

第一行两个整数表示序列的长度以及任意的目标值。
接下来个整数，为牛妹的初始序列。

输出描述:

一个整数表示方案数，答案对取模。
示例1

输入

复制 
3 2
1 1 1

输出

复制 
4

说明

存在一下四种分法{[(l,r)}表示{[l,r]}这个区间里面加{1]}:
{(1,3)}
{(1,2)(3,3)}
{(1,1)(2,3)}
{(1,1)(2,2)(3,3)}

备注:

对于的数据，
对于另的数据，，且保证
对于另的数据，，且保证
对于的数据，