题目描述

给定 $n$ 个整数 $a_1,a_2,\dots,a_n$ 作为上界，再给定一个整数 $m$，请问方程

有多少种不同的整数解且满足 $1\leq x_i\leq a_i$。由于解的数量可能很大，输出答案模 $1,000,000,007$ 的余数。

输入格式

• 第一行：两个整数 $n$ 与 $m$。
• 第二行：$n$ 个整数 $a_1,a_2,\dots,a_n$

输出格式

• 单个整数表示答案

3 5
1 3 2

2

样例解释 1

1+2+2=5 1+3+1=5

3 5
2 2 2

3

样例解释 2

1+2+2=5 2+1+2=5 2+2+1=5

数据范围

• $30\%$ 的数据，$1\leq n\leq 4$，$1\leq a_i\leq 50$
• $60\%$ 的数据，$1\leq n\leq 10$，$1\leq a_i\leq 20000$
• $100\%$ 的数据，$1\leq n\leq 20$，$1\leq a_i\leq 1,000,000$
• $1\leq m\leq 1,000,000,000$