「2017 山东一轮集训 Day6」三元组

传统 1000 ms 512 MiB

$149$ 通过 $354$ 提交

题目描述

给定三个整数 $a, b, c$，一个三元组 $(i, j, k)$ 是合法的，当且仅当满足：

1. $i, j, k$ 均为整数
2. $1 \leq i \leq a$, $1 \leq j \leq b$, $1 \leq k \leq c$
3. $\gcd(i, j) = \gcd(i, k) = \gcd(j, k) = 1$

请求出合法的三元组数量对 $10^9 + 7$ 取模的值。

输入格式

一行三个整数 $a, b, c$。

输出格式

输出一行，表示合法的三元组数量对 $10^9 + 7$ 取模的值。

样例

输入

4 5 6

输出

46

数据范围与提示

• 对于 $20\%$ 的数据，$1 \le a,b,c \le 500$；
• 对于 $20\%$ 的数据，$1 \le a,b \le 50000$, $c=1$；
• 对于 $40\%$ 的数据，$1 \le a,b,c \le 5000$；
• 对于 $100\%$ 的数据，$1 \le a,b,c \le 50000$。