题目描述

给定三个整数 $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$。