题解 p5343 [xr

using namespace std;
const int n = 100, mod = 1000000007;
struct  {
    int a[110][110];
    inline int* operator [] (int x) {return a[x];}
    inline () {memset(a, 0, sizeof a);}
    friend inline matrix operator * (matrix &a, matrix &b) {
        matrix ans;
        for(int i = 0; i < n; i++)
            for(int k = 0; k < n; k++)
                for(int j = 0; j < n; j++) ans[i][j] = (ans[i][j] + 1ll * a[i][k] * b[k][j]) % mod;
        return ans;
    }
} res, ans;
int pr, nf, able[110];
long long len;
int main() {
    scanf("%lld%d", &len, &pr);
    for(int i = 0, x; i < pr; i++) scanf("%d", &x), able[x] = 1;
    scanf("%d", &nf);
    for(int i = 0; i < n; i++) ans[i][i] = 1;
    for(int i = 1; i < n; i++) res[i][i - 1] = 1;
    for(int x, i = 0; i < nf; i++) {
        scanf("%d", &x);
        if(able[x]) res[n - x][n - 1] = 1;
    }
    for(; len; len >>= 1, res = res * res) if(len & 1) ans = ans * res;
    printf("%dn", ans[n - 1][n - 1]);
    return 0;
}