题目描述
给定三个整数 a,b,c,一个三元组 (i,j,k) 是合法的,当且仅当满足:
- i,j,k 均为整数
- 1≤i≤a,1≤j≤b,1≤k≤c
- gcd(i,j)=gcd(i,k)=gcd(j,k)=1
请求出合法的三元组数量对 109+7 取模的值。
输入格式
一行三个整数 a,b,c。
输出格式
输出一行,表示合法的三元组数量对 109+7 取模的值。
4 5 6
46
数据范围与提示
对于 20% 的数据,n≤20;
对于 40% 的数据,n≤1000;
对于 60% 的数据,n≤10000;
对于 100% 的数据,1≤n,q≤100000,1≤l≤r≤n。