Jennie

谁都能看出来是个背包求方案数，不过问题是怎么求

毕竟这个数据范围太诡异了。

但是背包计数不过是一种递推吧了。

并不容易但唯一的方法是采用矩阵乘法来加速

然后开一个100*100的矩阵开始递推。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<stack>
#include<algorithm>
#define int long long
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int n;
int x;
int l;
int y;
int a[1000001];
int mod=1000000007;
int b[1000001];
struct rtc{
    int con[105][105];
      rtc friend operator *(rtc x,rtc y){
        rtc tem;
        for(int i=1;i<=l;++i){
            for(int j=1;j<=l;++j){
                tem.con[i][j]=0;
            }
        }
        //memset(tem.con,0,sizeof(tem.con));
        for(int i=1;i<=l;++i){
            for(int j=1;j<=l;++j){
                for(int k=1;k<=l;++k){
                    tem.con[i][j]=(tem.con[i][j]+x.con[i][k]*y.con[k][j])%mod;
                }
            }
        }
        return tem;
    }
} bas,org,res;
int f[105];
int av[105];
int cnt;
rtc qk(rtc bas,int m){
    for(int i=1;i<=l;++i){
        for(int j=1;j<=l;++j){
            res.con[i][j]=0;
        }
    }
    for(int i=1;i<=l;++i){
        res.con[i][i]=1;
    }
    while(m){
        if(m&1){
            res=res*bas;
        }
        bas=bas*bas;
        m>>=1;
    }
    return res;
}
signed main(){
    read(n);
    read(x);
    for(int i=1;i<=x;++i){
        read(y);
        a[y]=1;
    }
    read(y);
    for(int i=1;i<=y;++i){
        read(x);
        b[x]=1;
    }
    for(int i=1;i<=100;++i){
        if(a[i]&&b[i]){
            av[++cnt]=i;
            l=i;
            bas.con[i][1]=1;        
        }   
    }
    for(int i=2;i<=l;++i){
        bas.con[i-1][i]=1;
    }
    f[0]=1;
    for(int i=1;i<l;++i){
        for(int j=1;j<=cnt;++j){
            if(av[j]<=i){
                f[i]=(f[i]+f[i-av[j]])%mod;
            }
        }
    }
    for(int i=1;i<=l;++i){
        org.con[1][i]=f[l-i];
    }
    org=org*qk(bas,n-l+1);
    cout<<org.con[1][1];
    return 0;
}