Description

“少年有他的山海，
有他的重重山影，有他的万里波涛。
如果可以，风给他，沙漠给他，天空也给他。
是无拘无束的风，会下大雨的沙漠，和铺满星辰的天空。
万物给他，让他自由。”

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

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

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

Format

Input

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

Output

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

Sample 1

Input

2 2 4

Output

1

【样例解释1】 只有(2,2)能够满足要求。

Sample 2

Input

3 4 8

Output

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)

Limitation

1s, 256MiB for each test case.
【数据范围】
对于20%的数据1<=n,m<=8 k<=100
对于40%的数据1<=n<=50 1<=m<=10^6 1<=k<=10^4
对于70%的数据1<=n<=100 1<=m<=10^9 1<=k<=10^7
对于100%的数据1<=n<=3000 1<=m<=10^9 1<=k<=10^7