fast pet

#include <algorithm>
#include <numeric>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <list>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <ctime>
#include <cassert>

using namespace std;
typedef long long LL;
#define FOR(k,a,b) for(LL k(a); k < (b); ++k)
#define FORD(k,a,b) for(LL k(a-1); k >= (b); --k)
#define REP(k,a) for(LL k=0; k < (a); ++k)
#define ABS(a) ((a)>0?(a):-(a))

char *ipos, *opos, InpFile[20000], OutFile[2000];
inline int readInt()
{
    while(*ipos <= 32) ++ipos;
    int x=0, neg = 0;char c;
    while( 1 )
    {
        c=*ipos++;
        if (c<=32) return x;
        x*=10;;
        x+=c-'0';
    }
}

inline void writeLL(LL a)
{
    opos+=sprintf("%lld\n",a);
}

inline void InitIO() {
    ipos = InpFile; opos = OutFile;
    fread_unlocked(InpFile,20000,1,stdin);
}
inline void FlushIO() {
    fwrite_unlocked(OutFile,opos-OutFile,1,stdout);
}

int main()
{
    InitIO();
    int T,K,D[20];
    const LL mod=1000000007;
    T=readInt();
    LL N,C[82],inverse[18],act[36],mpow[66][36];
    REP(testCase,T)
    {
        N=readInt();
        K=readInt();
        REP(i,K)
            D[i]=readInt();
        sort(D,D+K);
        memset(C,0,sizeof(C));
        REP(i,K)
            C[D[i]]=1;
        if(K==1)
        {
            if(N%D[0])
                writeLL(0);
            else
                writeLL(1);
            continue;
        }
        const int tmpMax=min(81,N+1);
        FOR(i,1,tmpMax)
        {
            REP(j,K)
            {
                if(D[j]<i)
                    C[i]+=C[i-D[j]];
                else
                    break;
            }
            C[i]%=mod;
        }
        if(N<tmpMax)
        {
            writeLL(C[N]);
            continue;
        }
        int& mMax=D[K-1];
        memset(inverse,0,sizeof(inverse));
        memset(act,0,sizeof(act));
        memset(mpow,0,sizeof(mpow));

        vector<LL> inverse(mMax),act(mMax*2);
        N-=mMax;
        vector<vector<LL> > mpow(100,vector<LL> (mMax*2));
        inverse[0]=1;
        REP(i,K-1)
        {
            inverse[D[i]]=-1;
        }
        reverse(inverse.begin(),inverse.end());
        REP(i,K)
        {
            mpow[0][D[i]-1]=1;
        }
        for(int i=1;(1LL<<i)<N;++i)
        {
            REP(j,mMax)
                REP(u,mMax)
            {
                mpow[i][j+u]+=mpow[i-1][j]*mpow[i-1][u];
                mpow[i][j+u]%=mod;
            }
            for(int u=mpow[i].size()-1;u>=mMax;--u)
            {
                REP(j,inverse.size())
                {
                    mpow[i][u-j-1]+=inverse[j]*mpow[i][u];
                    if(mpow[i][u-j-1]>=mod)
                        mpow[i][u-j-1]-=mod;
                    else if (mpow[i][u-j-1]<0)
                        mpow[i][u-j-1]+=mod;
                }
                mpow[i][u]=0;
            }
        }
        int depth=0;
        bool started=false;
        while(N)
        {
            if(N&(1LL<<depth))
            {
                if(!started)
                {
                    act=mpow[depth];
                    started=true;
                }
                else
                {
                    vector<LL> prev(mMax*2);
                    act.swap(prev);
                    REP(j,mMax)
                        REP(u,mMax)
                    {
                        act[j+u]+=prev[j]*mpow[depth][u];
                        act[j+u]%=mod;
                    }
                    for(int u=act.size()-1;u>=mMax;--u)
                    {
                        REP(j,inverse.size())
                        {
                            act[u-j-1]+=inverse[j]*act[u];
                            if(act[u-j-1]>=mod)
                                act[u-j-1]-=mod;
                            else if (act[u-j-1]<0)
                                act[u-j-1]+=mod;
                        }
                        act[u]=0;
                    }
                }
            }
            N&=~(1LL<<depth);
            ++depth;
        }
        LL a=0;
        REP(i,mMax)
        {
            a+=act[i]*C[mMax-i];
            a%=mod;
        }
        printf("%lld\n",a);
    }
    FlushIO();
    return 0;
}