记二维数组行下标从 0 开始，列下标从 1 开始。一维数组下标从 1 开始。
给定长为 n 的数组 a。设有二维数组 s，满足 s_{0,i}=a_i，且： s_{i,1}=a_{i}, s_{i,j}=s_{i,j-1}+s_{i-1,j}(i\ge 1,j > 1) 求任意 s_{y,x}\bmod (10^9+7)。
输入
输入一行三个整数 n,x,y(1\le n\le10^5,1\le x\le n,0\le y\le10^9)。
接下来输入一行 n 个整数，第 i 个整数为 a_i(0\le a_i\le 10^9)。
输出
输出一行一个整数代表答案。
样例
| 标准输入 复制文本 |
5 4 2 1 1 1 1 1 |
| 标准输出 复制文本 |
10 |
| 标准输入 复制文本 |
6 6 2 1 1 4 5 1 4 |
| 标准输出 复制文本 |
48 |
| 标准输入 复制文本 |
7 7 1000000000 1 4 3 7 5 8 1 |
| 标准输出 复制文本 |
999999840 |
提示
对样例一，有 s_0=(1,1,1,1,1),s_1=(1,2,3,4,5),s_2=(1,3,6,10,15)，故 s_{2,4}=10。
对样例二，有 s_0=(1,1,4,5,1,4),s_1=(1,2,6,11,12,16),s_2=(1,3,9,20,32,48)，故 s_{2,6}=48。
自主思考：如果扩展到 n\le 10^7 怎么做。