题目描述

徐老师热爱数学，而这天石老师决定考考徐老师

石老师设定了一个函数 $fun(x)$，这个函数的意义是计算 $x$ 的因数个数

例如 $fun(12)=6$，因为 $12$ 有 $6$ 个因数：$1,2,3,4,6,12$

而石老师提出的问题是，给出一个区间 $[l,r]$ 他希望徐老师计算 $fun(l) + fun(l+1) + fun(l+2) \dots + fun(r)$ 的结果，即 $\sum_{i=l}^{r} fun(i)$ 的和

由于数字范围不大，所以徐老师轻松解决了这个问题

但是接着徐老师就想到了一个问题，如果这道题的数字变大呢？

为了方便让所有数字变大，徐老师想到的方案是——让所有数字变成 $n$ 次幂！

也就是现在徐老师会给出一个区间 $[l,r]$ 和一个整数 $n$,他希望计算 $fun(l^n) + fun((l+1)^n) + fun((l+2)^n) \dots + fun(r^n)$ 的结果，即 $\sum_{i=l}^{r} fun(i^n)$ 的和

这个问题让徐老师很满意，于是他决定用这个问题来考考你，由于结果可能很大，请你将结果对 $1000000007$ 取模

输入格式

输入一行包含三个整数 $l,r,n$ 含义如题

输出格式

输出一个整数表示答案，并将答案对 $1000000007$ 取模

数据范围

对于所有数据满足 $r-l \leq 10^6$

样例输入1

1 12 2 

样例输出1

66

样例输入2

1 100 2

样例输出2

1194