题目描述

$\red{2018}$年$\red{1}$月$\red{31}$日，$\red{152}$年一遇的超级大月全食在中国高空出现（没看到的朋友真是可惜），小$\red{B}$看到月食，便对月球的轨道产生了兴趣。他上网查重力加速度的公式，公式如下：

$\red{v=\frac{GM}{r^2}}$

就在这个时候，他想到了一个跟这个差不多的问题，那就是对于以下公式：

$\red{v=\frac{a_1\times a_2\times ......\times a_n}{k}}$

已知$\red{n}$和$\red{k，}$求这$\red{n}$个正整数在都不大于$\red{m}$的情况下有多少种选择方式，使得$\red{v}$为与$\red{k}$互质正整数？

输入格式

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

输出格式

输出一个答案，代表方案数。

因为答案可能会很大，所以输出方案数$\red{mod~ 10007}$的值。

样例

输入样例1

2 2 4

输出样例1

1

输入样例2

3 4 8

输出样例2

13

提示

对于$\red{20\%}$的数据 $\red{1<=n,m<=8 ，k<=100}$

对于$\red{40\%}$的数据 $\red{1<=n<=50 1<=m<=10^6 ，1<=k<=10^4}$

对于$\red{70\%}$的数据 $\red{1<=n<=100 1<=m<=10^9 ，1<=k<=10^7}$

对于$\red{100\%}$的数据 $\red{1<=n<=3000， 1<=m<=10^9 ，1<=k<=10^7}$