You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

本题的评测时间较长，若发现有恶意利用此题堵塞评测队列的，我们会采取包括但不限于禁赛等措施

视传奇旅人伊雷娜小姐为偶像的碳钾钨因憧憬成为魔女而报考了重庆魔法大学的法阵工程专业！但是一入学碳钾钨就遇到了难题，于是他打算向你求助。

结构化法术设计的老师给碳钾钨布置了一个任务：试计算有多少种不同的长度为$n$的咒语序列合法。一个长度为$n$的魔法咒语序列可以用一个长度为$n$的数组$b$表示。为判定要给序列是否合法，老师给定了$n$个互不相同的魔法关键值和两个整数$k,m$，第$i$个魔法关键值用$a_i$表示。对于一个魔法序列$b$，若同时满足以下两个条件则合法：

1. 对任意$i,j(1<=i,j<=n)$，若$a_i= \lfloor \frac{a_j}{k}\rfloor$成立，则有$b_i > b_j$.
2. 对于任意$i$，都有$0<b_i<=m$

因为答案可能很大，老师只要求输出合法的咒语序列数量，且答案对$10^9+7$取模。

求求你帮碳钾钨解决这个问题，等碳钾钨成为魔女后，会把这段往事写到日记中的。

形式化的说：现给定三个整数$n,k,m$和长度为$n$的互不相同的数组$a$

求有多少个不同的长度为n的非负整数数组$b$满足以下两个条件

1. 对任意$i,j(1<=i,j<=n)$，若$a_i= \lfloor \frac{a_j}{k}\rfloor$成立，则有$b_i > b_j$.
2. 对于任意$i$，都有$b_i<=m$

求满足条件的数组$b$的个数，答案对$10^9+7$取模

Input Format

第一行三个整数$n,m,k$。

第二行$n$个整数，其中第$i$个整数表示$a_i$

Output Format

一个整数，表示合法的数组$b$的个数，答案对$10^9+7$取模

Sample

输入

3 3 2
1 2 3

输出

5

Hint

其中$n\leq2*10^3,m\leq10^8,1 \leq k \leq10,0\leq a_i\leq10^{12}$

样例中合法的长度为3的魔法序列有以下五种：

2 1 1
3 1 1
3 1 2
3 2 1
3 2 2