Migrated from Lutece 2882 多重和式

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

现有一多重和式：

$\sum_{i=1}^{n} \sum_{j=1}^{m} \operatorname{lcm}(i, j)[\gcd(i, j) \leq a]$

给出 $n, m, a$，请求出多重和式的结果，答案模 $10 ^ 9 + 7$。

Input

第一行，三个整数 $n, m, a\ (1 \leq n, m, a \leq 10^7)$ 。

Output

输出一个整数，表示多重和式的结果。答案模 $10 ^ 9 + 7$。

Samples

9 9 2

1373

2 2 1

5

4 5 6

122

100 100 95

18445734

Resources

2022 UESTC ICPC Training for Math and Geometry