题目描述

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

样例

input

4 5 6

output

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 $。