Problem1461--「2017 山东一轮集训 Day6」三元组（数据范围有误）

1461: 「2017 山东一轮集训 Day6」三元组（数据范围有误）

[Creator : ]
Time Limit : 1 sec  Memory Limit : 512 MB

Solved: 0Submit: 0Statistics

Description

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

  • i,j,k i, j, k i,j,k 均为整数
  • 1≤i≤a,1≤j≤b,1≤k≤c 1 \leq i \leq a, 1 \leq j \leq b, 1 \leq k \leq c 1≤i≤a,1≤j≤b,1≤k≤c
  • gcd(i,j)=gcd(i,k)=gcd(j,k)=1 \gcd(i, j) = \gcd(i, k) = \gcd(j, k) = 1 gcd(i,j)=gcd(i,k)=gcd(j,k)=1

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

输入格式

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

输出格式

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

样例

样例输入

4 5 6

样例输出

46

数据范围与提示

对于 20% 20\% 20% 的数据，n≤20 n \leq 20 n≤20；
对于 40% 40\% 40% 的数据，n≤1000 n \leq 1000 n≤1000；
对于 60% 60\% 60% 的数据，n≤10000 n \leq 10000 n≤10000；
对于 100% 100\% 100% 的数据，1≤n,q≤100000,1≤l≤r≤n 1 \leq n, q \leq 100000, 1 \leq l \leq r \leq n 1≤n,q≤100000,1≤l≤r≤n。

Source/Category

 
Submit