#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9;
const ll J=1e18,N=1e6+7;
namespace FPS {
	const ll P=998244353;
	inline ll add(ll x,ll y){return(x+=y)<P?x:x-P;}
	inline ll dec(ll x,ll y) {return(x-=y)>=0?x:x+P;}
	inline ll qpow(ll x,ll y,ll mul=1) {while(y)mul=y&1?mul*x%P:mul,x=x*x%P,y>>=1;return mul;}
	ll N;
	vector<ll> rev,_inv={0,1};
	inline void NTT_init(ll n) {
		if (N>=n&&N<n<<1) return;
		ll c=-1; N=1; while (N<n) N<<=1,c++;
		if (N>rev.size()) rev.resize(N);
		for (ll i=0;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<c);
	}
	inline void inv_init(ll n) {
		ll t=_inv.size();
		if (n>t) _inv.resize(n);
		for (ll i=t;i<n;i++) _inv[i]=_inv[P%i]*dec(0,P/i)%P;
	}
	struct fps:vector<ll> {
		friend fps operator * (fps f,fps g) {
			static ll t;
			t=f.size()+g.size()-1;
			if (min(f.size(),g.size())<=40) {
				fps ret(t);
				for (ll i=0;i<f.size();i++) for (ll j=0;j<g.size();j++)
					ret[i+j]=(ret[i+j]+f[i]*g[j])%P;
				return ret;
			}
			NTT_init(t),f.NTT(1),g.NTT(1);
			for (ll i=0;i<N;i++) f[i]=f[i]*g[i]%P;
			f.NTT(-1);
			return f.pre(t);
		}
		friend fps operator + (fps f,fps g) {
			if (f.size()<g.size()) f.swap(g);
			for (ll i=0;i<g.size();i++) f[i]=add(f[i],g[i]);
			return f;
		}
		friend fps operator - (fps f,fps g) {
			if (f.size()<g.size()) f.resize(g.size());
			for (ll i=0;i<g.size();i++) f[i]=dec(f[i],g[i]);
			return f;
		}
		#define f (*this)
		using vector<ll>::vector;
		inline fps pre(ll n) { return fps(f.begin(),f.begin()+min((ll)f.size(),n)); }
		void NTT(ll op) {
			f.resize(N);
			for (ll i=0;i<N;i++) if (i<rev[i]) ::swap(f[i],f[rev[i]]);
			for (ll i=1;i<N;i<<=1) {
				ll w1=qpow(op==1?3:332748118,(P-1)/(i<<1));
				for (ll j=0;j<N;j+=i<<1) for (ll k=j,w=1;k<j+i;k++,w=w*w1%P) {
					ll t1=f[k],t2=w*f[k+i]%P;
					f[k]=add(t1,t2),f[k+i]=dec(t1,t2);
				}
			}
			if (op==-1) {
				ll inv=qpow(N,P-2);
				for (ll i=0;i<N;i++) f[i]=f[i]*inv%P;
			}
		}
		fps inv(ll n=0) {
			if (!n) n=f.size();
			fps g={qpow(f[0],P-2)},h;
			for (ll d=1;d<n;) {
				d<<=1;
				NTT_init(d<<1),h=f.pre(d);
				g.NTT(1),h.NTT(1);
				for (ll i=0;i<N;i++) g[i]=g[i]*dec(2,h[i]*g[i]%P)%P;
				g.NTT(-1),g.resize(d);
			}
			return g.pre(n);
		}
		fps ln(ll n=0) {
			if (!n) n=f.size();
			fps h=f.pre(n);
			for (ll i=0;i+1<h.size();i++) h[i]=(i+1)*h[i+1]%P;
			h.pop_back(),h=(h*f.inv(n)).pre(n),inv_init(n);
			for (ll i=n-1;i>=1;i--) h[i]=h[i-1]*_inv[i]%P;
			return h[0]=0,h;
		}
		fps exp(ll n=0) {
			if (!n) n=f.size();
			fps g={1};
			for (ll d=1;d<n;) d<<=1,g=g*(fps{1}+f.pre(d)-g.ln(d));
			return g.pre(n);
		}
		#undef f
	};
} using FPS::fps;
ll P,n,m,a[N],b[N],g,phi,ans;
ll ca[N],cb[N],cc[N];
ll qp(ll x,ll y=P-2) { return y?(y&1?x:1)*qp(x*x%P,y>>1)%P:1; }
ll sq(ll x) { return x*x%P; }
ll cal(ll a,ll b) {
	if (!sq(3*a+b)||!sq(3*a+2*b)) return P+1;
	return ((sq(2*a+3*b)+5*sq(a))*qp(sq(3*a+b))+(sq(2*a+5*b)+3*sq(b))*qp(sq(3*a+2*b)))%P;
}
void mian() {
	scanf("%lld%lld",&P,&n),phi=P-1;
	for (ll i=1;i<=n;i++) scanf("%lld",&a[i]),ca[a[i]]=1;
	scanf("%lld",&m);
	for (ll i=1;i<=m;i++) scanf("%lld",&b[i]),cb[b[i]]=1;
	for (ll i=1;i<P;i++) if (cb[cal(i,1)]) cc[i]=1;
	vector<ll> prm;
	for (ll i=2,ph=phi;i<=ph;i++) if (ph%i==0) {
		prm.pb(i);
		while (ph%i==0) ph/=i;
	}
	for (g=2;g<P;g++) {
		ll flg=1;
		for (ll j:prm) if (qp(g,phi/j)==1) { flg=0; break; }
		if (flg) break;
	}
	fps F(P+1),G(P+1);
	for (ll i=0,x=1;i+1<P;i++,(x*=g)%=P) if (ca[x]) F[i]=G[P-i]=1;
	F=F*G;
	for (ll i=0,x=1;i+1<P;i++,(x*=g)%=P) if (cc[x]) ans+=F[P+i]+F[i+1];
	if (ca[0]) for (ll i=1;i<P;i++) if (ca[i]) ans+=cb[cal(0,i)]+cb[cal(i,0)];
	cout<<ans;
}
bool ORY; int main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	while (1)
//	int t; for (scanf("%d",&t);t--;)
	mian();
	cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
	return 0;
}