题目描述

给出三个正整数 n, m, k, 现在要构造一个数组，要求满足：

1、数组中含有 n 个元素；

2、每个元素均为不超过 m 的正整数；

3、所有元素的和是 k 的倍数。

4、至少有一个元素是素数。

问：能构造出多少个不同的数组？

答案可能很大，你需要输出其 mod $(10^9 + 7)$ 的值。

注：两个长度为 n 的数组 A 和 B 不同，当且仅当存在一个整数 i （1 ≤ i ≤ n），满足 Ai ≠ Bi。

输入格式

一行，包含三个整数 $n, m, k$。

输出格式

一个整数，表示答案 mod $(10^9 + 7)$。

输入样例

3 5 3

输出样例

33

数据范围

对 $20\%$ 的数据，$1 ≤ n, m ≤100$。

对 $50\%$ 的数据，$1 ≤ m ≤ 100$。

对 $80\%$ 的数据，$1 ≤ m ≤ 10^6$。

对 $100\%$ 的数据，$1 ≤ n ≤ 10^9, 1 ≤ m ≤ 2×10^7, 1 ≤ k ≤ 100$。