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

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

题目描述

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

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

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

输入格式

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

输出格式

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

4 5 6
46

数据范围与提示

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