dragonfruit

#include<fstream>
#include<cstring>
using namespace std;

ifstream fin("dragonfruit.in");
ofstream fout("dragonfruit.out");

const int SMAX = 11;
const int KMAX = 1e3 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int NMAX = 1e5 + 1;

struct sol
{
    int cactusi = INF,moduri = 0;
};

sol vechi[SMAX][KMAX][2],nou[SMAX][KMAX][2],initial[SMAX][KMAX][2];

int v[NMAX];

// daca subsecventa e deschisa avem 1,daca nu avem 0

int s,k;


sol update(sol a,sol b)
{
    if(a.cactusi ^ b.cactusi)
        {
            if(a.cactusi > b.cactusi)
                {
                    return b;
                }
            else
                {
                    return a;
                }
        }

    sol noua = a;
    noua.moduri += b.moduri;
    noua.moduri = noua.moduri % MOD;

    return noua;
}

void sterge(sol v[][KMAX][2],int n,int m)
{
    for(int i = 0 ; i <= n ; i++)
    {
        for(int j = 0 ; j <= m ; j++)
        {
            v[i][j][0] = initial[i][j][0];
            v[i][j][1] = initial[i][j][1];
        }
    }
}


void par(int i)
{
    sterge(vechi,s,k);
    vechi[0][0][0].moduri = 1;
    vechi[0][0][0].cactusi = 0;
    for(int e = 1; e <= s; e++)
                {
                    for(int suma = 1 ; suma <= k ; suma++)
                        {
                            if(suma >= v[i])
                                {
                                    //adaug la interval deschis

                                    sol f = nou[e][suma - v[i]][1]; f.cactusi++;
                                    vechi[e][suma][1] = update(vechi[e][suma][1],f);

                                    // deschid un nou interval

                                    f = nou[e - 1][suma - v[i]][0]; f.cactusi++;
                                    vechi[e][suma][1] = update(vechi[e][suma][1],f);

                                    f = nou[e - 1][suma - v[i]][1]; f.cactusi++;
                                    vechi[e][suma][1] = update(vechi[e][suma][1],f);
                                }


                                    // inchid intervalul curent

                                    vechi[e][suma][0] = update(vechi[e][suma][0],nou[e][suma][1]);

                                    //pastrez intervalul inchis

                                    vechi[e][suma][0] = update(vechi[e][suma][0],nou[e][suma][0]);
                        }
                }
}

void impar(int i)
{
    sterge(nou,s,k);
    nou[0][0][0].moduri = 1;
    nou[0][0][0].cactusi = 0;
    for(int e = 1; e <= s; e++)
                {
                    for(int suma = 1 ; suma <= k ; suma++)
                        {
                            if(suma >= v[i])
                                {
                                    sol f = vechi[e][suma - v[i]][1]; f.cactusi++;
                                    nou[e][suma][1] = update(nou[e][suma][1],f);



                                    f = vechi[e - 1][suma - v[i]][0]; f.cactusi++;
                                    nou[e][suma][1] = update(nou[e][suma][1],f);

                                    f = vechi[e - 1][suma - v[i]][1]; f.cactusi++;
                                    nou[e][suma][1] = update(nou[e][suma][1],f);
                                }


                                    nou[e][suma][0] = update(nou[e][suma][0],vechi[e][suma][1]);
                                    nou[e][suma][0] = update(nou[e][suma][0],vechi[e][suma][0]);
                        }
                }
}

void rezpar()
{
    int cmin = INF;
    int moduri = 0;

    for(int e = 1; e <= s ; e++)
        {
            if(vechi[e][k][0].moduri)
                {
                    if(vechi[e][k][0].cactusi == cmin){
                    moduri += vechi[e][k][0].moduri;
                    if(moduri > MOD)
                        moduri -= MOD;
                    }

                    if(vechi[e][k][0].cactusi < cmin)
                        {
                            moduri = vechi[e][k][0].moduri;
                            cmin = vechi[e][k][0].cactusi;
                        }
                }

            if(vechi[e][k][1].moduri)
                {
                    if(vechi[e][k][1].cactusi == cmin){
                    moduri += vechi[e][k][1].moduri;
                    if(moduri > MOD)
                        moduri -= MOD;
                    }

                    if(vechi[e][k][1].cactusi < cmin)
                        {
                            moduri = vechi[e][k][1].moduri;
                            cmin = vechi[e][k][1].cactusi;
                        }
                }
        }

    int st = cmin ^ INF ? cmin : 0;
    fout << st << " " << moduri << '\n';
}

void rezimpar()
{
    int cmin = INF;
    int moduri = 0;

    for(int e = 1; e <= s ; e++)
        {
            if(nou[e][k][0].moduri)
                {
                    if(nou[e][k][0].cactusi == cmin){
                    moduri += nou[e][k][0].moduri;
                    if(moduri > MOD)
                        moduri -= MOD;
                    }

                    if(nou[e][k][0].cactusi < cmin)
                        {
                            moduri = nou[e][k][0].moduri;
                            cmin = nou[e][k][0].cactusi;
                        }
                }

            if(nou[e][k][1].moduri)
                {
                    if(nou[e][k][1].cactusi == cmin){
                    moduri += nou[e][k][1].moduri;
                    if(moduri > MOD)
                        moduri -= MOD;
                    }
                    if(nou[e][k][1].cactusi < cmin)
                        {
                            moduri = nou[e][k][1].moduri;
                            cmin = nou[e][k][1].cactusi;
                        }
                }
        }

    int st = cmin ^ INF ? cmin : 0;
    fout << st << " " << moduri << '\n';
}

void testcase()
{
    int n;
    fin >> n >> k >> s;

    for(int i = 1; i <= n ; i++)
        {
            fin >> v[i];
        }

    sterge(vechi,s,k);

    // caz de baza

    vechi[0][0][0].cactusi = 0;
    vechi[0][0][0].moduri = 1;

    for(int i = 1; i <= n ; i++)
        {
            if(i & 1)
                {
                    impar(i);
                }
            else
                {
                    par(i);
                }
        }

    if(n & 1)
        {
            rezimpar();
        }
    else
        {
            rezpar();
        }

}

int main()
{
    int t;
    fin >> t;
    while(t--)
        testcase();

    fin.close();
    fout.close();
    return 0; // superpeace
}