Problem1409--#6076. 「2017 山东一轮集训 Day6」三元组(数据范围有误)

1409: #6076. 「2017 山东一轮集训 Day6」三元组(数据范围有误)

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

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 1ia,1jb,1kc
  • 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 109+7 取模的值。

Input

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

Output

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

Sample Input Copy

4 5 6

Sample Output Copy

46

HINT

对于 20% 20\% 20% 的数据,n≤20 n \leq 20 n20
对于 40% 40\% 40% 的数据,n≤1000 n \leq 1000 n1000
对于 60% 60\% 60% 的数据,n≤10000 n \leq 10000 n10000
对于 100% 100\% 100% 的数据,1≤n,q≤100000,1≤l≤r≤n 1 \leq n, q \leq 100000, 1 \leq l \leq r \leq n 1n,q100000,1lrn

Source/Category