Background

Special for beginners, ^_^

Description

为了防止支付宝被盗，小明想写一个密码生成器，用于定期更换密码。

小明相信，密码生成器的代码越长越安全，所以，他拼了老命，想出来下面这个非常复杂的式子保财产安全。

输入a、b和c，密码生成器会输出：

$\sum\limits_{i=1}^a \sum\limits_{j=1}^b \sum\limits_{k=1}^c \left([ \gcd(i, j, k)=1]\cdot min( \lfloor \frac{a}{i} \rfloor, \lfloor \frac{b}{j} \rfloor, \lfloor \frac{c}{k} \rfloor) \right) mod (10^9+7)$

请你帮助小明写一个这样的程序。

提示：中括号是艾弗森括号。

Format

Input

每个测试点包含多组数据（不超过1e5）组。

每组数据一行，包含三个不超过$10^{10}$的正整数a、b和c。

Output

对于每组数据，在一行中输出结果。

Samples

1 1 1
114514 114514 114514

1
312317026

Limitation

1s, 1024KiB for each test case.