Description

小黄终于还是疯了。

那天，小杨给了小黄三株毒蘑菇。小黄吃下第一株毒蘑菇后，从 $l$ 开始到 $r$ 结束的所有整数盘旋于小黄上空，小黄必须 $k$ 次的从这些整数中任意选择一个数，每选择一次后，小黄的大脑中将会多出一个那个数，但原本的数并不会消失，这也就是说，小黄可以多次选择同一个数。

吃下第二株毒蘑菇后，小黄突然意识到所有已经在大脑中的数一起可以求出一个最大公因数，于是在小黄大脑中的所有数都被除以了那个最大公因数，那之后在小黄大脑中的已经被除的数再全部都乘在了一起，得到了一个乘积结果。

吃下第三株毒蘑菇后，小黄才发现在吃下第一株毒蘑菇后的 $k$ 次选择只不过是一种方案，在两种方案中，只要两种方案中存在第 $i$ 次取的数不同，就是两种不同的方案。而现在所有平行世界收束到一起，小黄可能选择的所有方案求出的乘积结果乘在一起，得到了最终结果。这个过程实在是太复杂了，小黄迷失在了那些数中。只有求出那个最终结果，小黄才能脱离幻觉，回到现实。

请你帮忙求出这个最终结果，拯救小黄。这个结果很大，请输出最终结果对 $1e9 + 7$ 取模的值。

Format

Input

输入一行三个整数 $l, r, k\ (1 \leq l \leq r \leq 10^6, 1 \leq k \leq 10^6)$，表示可选择的整数从 $l$ 开始，到 $r$ 结束，一共选择 $k$ 次。

Output

输出一个整数，表示最终结果对 $1e9 + 7$ 取模的值。

Samples

2 4 2

20736

Note

对于第一个样例，可以选择的方案有 $[2,2],[2,3],[2,4],[3,2],[3,3],[3,4],[4,2],[4,3],[4,4]$，他们的乘积结果分别为 $1, 6, 2, 6, 1, 12, 2, 12, 1$，最终结果为 $20736$。

Limitation

1s, 1024KiB for each test case.