TO-DO gcd

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
const int mod = 10007;
int n;
struct Int{
	int factor,m;
	bool operator < (Int &a) const {
		return factor < a.factor;
	}
}Ta[200],Tb[200];
int ta[20],tb[20],_Ta,_Tb;
void break_down(Int t[],int &T,int x)
{
	int __t = sqrt(x + 0.5);
	for(int i = 2;i <= __t;++i)
	{
		if(x % i == 0)
		{
			t[T++].factor = i;
			while(x % i == 0)
			{
				x /= i;
				t[T].m++;
			}
		}
	}
	if(x != 1)
	{
		t[T++].factor = x;
		t[T].m++;
	}
}
int Pow(int a,int b)
{
	int c = 1;
	for(;b;b >>= 1)
	{
		if(b&1)
		{
			c = c*a%mod;
		}
		a = a*a%mod;
	}
	return c;
}
void solve()
{
	int ans = 0;
	sort(Ta,Ta + _Ta);
	sort(Tb,Tb + _Tb);
	for(int i = 0;i < _Ta;++i)
	{
		printf("<%d , %d>
",Ta[i].factor,Ta[i].m);
	}
	printf("
");
	for(int i = 0;i < _Tb;++i)
	{
		printf("<%d , %d>
",Tb[i].factor,Tb[i].m);
	}
	if(Ta[0] < Tb[0])
	{
		for(int i = 0;i < n;++i)
		{
			for(int j = i;j < n;++j)
			{
				if(Ta[i].factor == Tb[j].factor)
				{
					ans = ((ans%mod)*(Pow(Ta[i].factor,Ta[i].m + Tb[j].m)%mod))%mod;
				}
			}
		}
	}
	else{
		for(int i = 0;i < n;++i)
		{
			for(int j = i;j < n;++j)
			{
				if(Tb[i].factor == Ta[j].factor)
				{
					ans = (ans%mod + Pow(Tb[i].factor,Tb[i].m + Ta[j].m)%mod)%mod;
				}
			}
		}
	}
	printf("%d
",ans);
}
int main()
{
	scanf("%d",&n);
	for(int i = 0;i < n;++i)
	{
		scanf("%d",&ta[i]);
		break_down(Ta,_Ta,ta[i]);
	}
	for(int i = 0;i < n;++i)
	{
		scanf("%d",&tb[i]);
		break_down(Tb,_Tb,tb[i]);
	}
	solve();
	return 0;
}
/*
in: 
3
12 15 70
20 75 49
out:
2100
*/