Discription

Let's denote d(n) as the number of divisors of a positive integer n. You are given three integers a, b and c. Your task is to calculate the following sum:

Find the sum modulo 1073741824 (2³⁰).

Input

The first line contains three space-separated integers a, b and c (1 ≤ a, b, c ≤ 2000).

Output

Print a single integer — the required sum modulo 1073741824 (2³⁰).

Example

Input

2 2 2

Output

20

Input

4 4 4

Output

328

Input

10 10 10

Output

11536

Note

For the first example.

• d(1·1·1) = d(1) = 1;
• d(1·1·2) = d(2) = 2;
• d(1·2·1) = d(2) = 2;
• d(1·2·2) = d(4) = 3;
• d(2·1·1) = d(2) = 2;
• d(2·1·2) = d(4) = 3;
• d(2·2·1) = d(4) = 3;
• d(2·2·2) = d(8) = 4.

So the result is 1 + 2 + 2 + 3 + 2 + 3 + 3 + 4 = 20.

 

 

我是直接暴力合并a和b，然后设 to(i) 为有多少对有序对(x,y) 满足 1<=x<=a 且 1<=y<=b 且 x*y==i。

然后式子就是 Σ(i=1 to a*b) to(i) Σ(j=1 to c) d(i*j)

这个用约数个数函数的基本式子就可以化简，最后可以 用不到 O(a*b*log(a*b)) 的时间计算出答案。

所以a,b就取三个数中最小的两个就行了。

 

#include
       
        #define ll long long#define maxn 4000000using namespace std;const int ha=1<<30;int a,b,c,miu[maxn+5];int zs[maxn/5],t=0,D,low[maxn+5];int d[maxn+5],to[maxn+5],ans=0;bool v[maxn+5];inline void init(){	for(int i=1;i<=a;i++)	    for(int j=1;j<=b;j++) to[i*j]++;	miu[1]=d[1]=low[1]=1;		for(int i=2;i<=maxn;i++){		if(!v[i]) zs[++t]=i,miu[i]=-1,low[i]=i,d[i]=2;		for(int j=1,u;j<=t&&(u=zs[j]*i)<=maxn;j++){			v[u]=1;						if(!(i%zs[j])){				low[u]=low[i]*zs[j];				if(low[i]==i) d[u]=d[i]+1;				else d[u]=d[low[u]]*d[i/low[i]];				break;			}			low[u]=zs[j],d[u]=d[i]<<1,miu[u]=-miu[i];		}	}    	for(int i=1;i<=maxn;i++) d[i]+=d[i-1];}inline int add(int x,int y){	x+=y;	return x>=ha?x-ha:x;}inline void calc(){	for(int i=1,sum;i<=c;i++) if(miu[i]){		sum=0;		for(int j=i;j<=D;j+=i) sum=add(sum,to[j]*(ll)(d[j/i]-d[j/i-1])%ha);		sum=sum*(ll)d[c/i]%ha;		if(miu[i]==1) ans=add(ans,sum);		else ans=add(ans,ha-sum);	}	printf("%d\n",ans);}int main(){	scanf("%d%d%d",&a,&b,&c);	if(a>b) swap(a,b);	if(a>c) swap(a,c);	if(b>c) swap(b,c);	D=a*b;		init();	calc();		return 0;}