该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

“少年有他的山海，

有他的重重山影，有他的万里波涛。

如果可以，风给他，沙漠给他，天空也给他。

是无拘无束的风，会下大雨的沙漠，和铺满星辰的天空。

万物给他，让他自由。”

少年向大海走去，他在大海边发现了 $n$ 个一连串按序排列的贝壳，每个贝壳 都可以表示一个 $[1,m]$ 的整数。这些数的乘积代表这一串贝壳的和谐值，且贝壳的和谐值与大海的和谐值 $k$ 的比值 $v$ 代表少年此时的心情的和谐值，如果 $v$ 和 $k$ 为互质正整数，或许少年将转身向山里走去。

贝壳数值有多少选择的方法，能让少年回到那山里去？

“他明白他明白我给不起，于是转身向山里走去。 ”——《山海》

Input Format

一行三个正整数 $n,m,k$（意义见题目描述）。

Output Format

输出一个答案，代表选择方案数。因为答案可能会很大，所以输出选择方案数 $\text{mod}$ $10007$ 的值。

Sample

【输入样例1】

2 2 4

【输出样例1】

1

【样例解释1】

只有 $(2,2)$ 能够满足要求。

【输入样例2】

3 4 8

【输出样例2】

13

【样例解释2】

$(1,2,4)(1,4,2)(2,1,4)(2,2,2)(2,3,4)(2,4,1)(2,4,3)(3,2,4) (3,4,2)(4,1,2)(4,2,1)(4,2,3)(4,3,2)$

Hint

对于 $20\%$ 的数据 $1 \le n,m \le 8，k \le 100$

对于 $40\%$ 的数据 $1 \le n \le 50，1 \le m \le 10^6，1 \le k \le 10^4$

对于 $70\%$ 的数据 $1 \le n \le 100 ，1 \le m \le10^9 ，1 \le k \le 10^7 $

对于 $100\%$ 的数据 $1 \le n\le 3000，1 \le m \le 10^9，1 \le k \le 10^7$