f466ef70.cpp

#include <bits/stdc++.h>
#define alive std::cout << "$LINE @" << __LINE__ << " ALIVE" << std::endl
#define watch(var) std::cout << "$ LINE @" << __LINE__ << " FUN @" << __FUNCTION__ \
                             << " VAR @" << (#var) << ": " << (var) << std::endl

using namespace std;

typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef double f64;
typedef long double f128;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    x = 0;
    bool neg = false;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int MOD = 1e9 + 7;
const int N = 100 + 5;

inline void inc(int &x, const int &y)
{
    x += y;
    if (x >= MOD)
    {
        x -= MOD;
    }
}

int f[N][N];
int A[N], B[N];

inline void solve()
{
    int n, k;

    read(n), read(k);
    for (int i = k; i <= n; ++i)
    {
        memset(f[i], 0, sizeof(int) * (n + 1));
    }

    int curA = 0, curB = 0;
    for (int i = 1, x; i <= k; ++i)
    {
        read(x);
        if (i - x <= 0)
        {
            A[++curA] = x;
        }
        else
        {
            B[++curB] = x;
        }
    }

    for (int i = 1; i < curA; ++i)
    {
        if (A[i] >= A[i + 1])
        {
            puts("0");
            return;
        }
    }
    for (int i = 1; i < curB; ++i)
    {
        if (B[i] >= B[i + 1])
        {
            puts("0");
            return;
        }
    }

    f[k][std::max(A[curA], B[curB])] = 1;
    for (int i = k + 1; i <= n; ++i)
    {
        for (int j = i; j <= n; ++j)
        {
            for (int k = 0; k <= j; ++k)
            {
                inc(f[i][j], f[i - 1][k]);
            }
        }
    }

    printf("%d\n", f[n][n]);
}

int main()
{
    int T;
    read(T);

    for (int cas = 1; cas <= T; ++cas)
    {
        printf("Case #%d: ", cas);
        solve();
    }

    return 0;
}