#217. 构造数组

构造数组

题目描述

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

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

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

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

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

问:能构造出多少个不同的数组?

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

注:两个长度为 n 的数组 A 和 B 不同,当且仅当存在一个整数 i (1 ≤ i ≤ n),满足 Ai ≠ Bi。

输入格式

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

输出格式

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

输入样例

3 5 3

输出样例

33

数据范围

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

对 50%50\% 的数据,1≤m≤1001 ≤ m ≤ 100。

对 80%80\% 的数据,1≤m≤1061 ≤ m ≤ 10^6。

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