给定三个整数 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 109+7 取模的值。

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

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

对于 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。