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

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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