Duff trên bãi biển

Cho mảng $a$ gồm $n$ số nguyên dương $a_0,a_1,\dots ,a_{n-1}$. Từ mảng $a$ ta dựng mảng $b$ gồm $l$ phần tử theo quy tắc

$$b_i=a_{imodn}\text{với }0\le i<l,$$

nghĩa là mảng $a$ được lặp lại tuần hoàn cho tới khi thu đủ $l$ phần tử.

Xem mỗi phần tử $b_i$ thuộc khối mang số $\lfloor i/n\rfloor$ (khối $0$ gồm $n$ phần tử đầu, khối $1$ gồm $n$ phần tử tiếp theo, v.v.).

Hãy đếm số dãy con $b_{i_1},b_{i_2},\dots ,b_{i_x}$ (với $0\le i_1<i_2<\cdots <i_x<l$) thỏa mãn đồng thời:

• $1\le x\le k$;
• hai phần tử liên tiếp thuộc hai khối khác nhau và tăng dần: $\lfloor i_j/n\rfloor <\lfloor i_{j+1}/n\rfloor$ với mọi $1\le j\le x-1$;
• giá trị không giảm: $b_{i_j}\le b_{i_{j+1}}$ với mọi $1\le j\le x-1$.

Hai dãy con được coi là khác nhau nếu tập chỉ số $\{i_1,\dots ,i_x\}$ khác nhau. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $l$, $k$.
• Dòng thứ hai chứa $n$ số nguyên $a_0,a_1,\dots ,a_{n-1}$.

Dữ liệu ra

• Một số nguyên duy nhất: số dãy con thỏa mãn, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le n,k$ và $n\times k\le {10}^6$.
• $1\le l\le {10}^{18}$.
• $1\le a_i\le {10}^9$ với mọi $0\le i\le n-1$.

Ví dụ