#include #define MOD 1000000007LL using namespace std; typedef long long ll; typedef pair P; ll n; ll a[1000005],b[1000005]; vector G[2][1000005]; int group[2][1000005]; int size[2][1000005]; vector gg[2][1000005]; list lis[2][100005]; int dist[2][1000005]; bool used[1000005]; ll extgcd(ll a,ll b,ll& x,ll& y){ ll d=a; if(b!=0LL){ d=extgcd(b,a%b,y,x); y-=(a/b)*x; }else{ x=1; y=0; } return d; } ll mod_inverse(ll a,ll m){ ll x,y; extgcd(a,m,x,y); return (m+x%m)%m; } ll gcd(ll a,ll b){ if(b==0LL)return a; return gcd(b,a%b); } void dfs(int v,int div,int s){ group[div][v]=s; size[div][s]++; gg[div][s].push_back(v); for(int i=0;i vs; int gcdval=gcd(ga_size,gb_size); if(gcdval==0)while(1); ll all=(ll)ga_size*(gb_size/gcdval); vs.push_back(0); for(int j=0;j=MOD)ans%=MOD; } //printf("%d\n",vs[vs.size()-1]); //printf("get%d %lld\n",i,ans); } printf("%lld\n",ans); return 0; }