for(int i=1;i<=n;i++)
	cin>>a[i],a[i]%=Mod;

即使你是这样写的，但 $a[] \times a[]$ 仍然会爆 int，请开 long long

十年OI一场空，不开long long见祖宗