[AdditionalFile6076.zip](file://AdditionalFile6076.zip?type=additional_file)

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

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

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

• $i, j, k$ 均为整数
• $1 \leq i \leq a, 1 \leq j \leq b, 1 \leq k \leq c$
• $\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$。