题目描述

输入一个包含 \(n\) 个正整数的数组 \(A\)，以及两个整数 \(m\) 和 \(k\)。先将这个数组 \(A\) 重复 \(m\) 次，得到长度为 \(m×n\) 的新数组 \(B\)。

现在请求出，在新数组 \(B\) 中，有多少个连续子区间，满足区间的元素总和不超过 \(k\) 。

由于答案可能很大，请对\(10^9+7\)取模。

格式

输入格式

第一行三个整数 \(n,m,k\)，意义如题所述。

第二行 \(n\) 个正整数，描述数组 \(A\)。

输出格式

一行一个整数，表示答案对 \(10^9+7\) 取模的结果。

样例1

样例输入1

2 2 4
4 4

样例输出1

4

限制

\(Subtask1(20pts)\)：\(n,m≤100\)。

\(Subtask2(40pts)\)：\(k=10,1≤m≤100\)。

\(Subtask3(40pts)\)：无特殊限制。

对于全部数据：\(1≤n,m≤100000, 1≤k≤10^{16}, ∀1≤i≤n,1≤a_i≤10^6\)。