刚接触这个算法，代码极其丑陋qwq

调了两个小时,样例都过不了（大雾）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int x1,x2,x,mx;
int n;
int m[105],num[105],f[105];
struct mat{
	int s[105][105];
	mat operator * (const mat o)const{
		mat a1;
		for(int i=1;i<=mx;i++)
			for(int j=1;j<=mx;j++)a1.s[i][j]=0;
		for(int i=1;i<=mx;i++)
			for(int j=1;j<=mx;j++)
				for(int k=1;k<=mx;k++)
					a1.s[i][j]+=s[i][k]*o.s[k][j],a1.s[i][j]%=mod;
		return a1;
	}
}A;
mat qpow(int a){
	mat b=A,ans;
	for(int i=1;i<=mx;i++){
		ans.s[i][i]=1;
	}
	while(a){
		if(a%2)ans=ans*b;
		b=b*b,a/=2;
	}
	return ans;
}
signed main(){
	cin>>n;
	cin>>x1;
	for(int i=1;i<=x1;i++){
		int s;
		cin>>s;
		m[s]++;
	}
	cin>>x2;
	for(int i=1;i<=x2;i++){
		int s;
		cin>>s;
		m[s]++;
	}
	for(int i=1;i<=100;i++){
		if(m[i]>=2)num[++x]=i,mx=i;
	}
	for(int i=1;i<=x;i++){
		A.s[1][num[i]]=1;
	}
	for(int i=1;i<=mx;i++){
		A.s[i+1][i]=1;
	}
	f[0]=1;
	for(int i=1;i<=mx;i++){
		for(int j=1;j<=x;j++){
			if(i>=num[j]){
				f[i]+=f[i-num[j]];
				f[i]%=mod;
			}
		}
	}
	mat ans;
	for(int i=1;i<=mx;i++)ans.s[i][1]=f[mx-i];
	ans=ans*qpow(n-mx+1);
	cout<<ans.s[1][1];
	return 0;
}