HOÁN VỊ ĐẸP

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}
constexpr bool typetest = 0;
constexpr int N = 1e2 + 5;
constexpr int mod = 1e9;
int n, m;

int dp[N][9000];

void Solve();

void Read()
{
    while (cin >> n >> m)
        Solve();
}

#define bit(i, x) (((x) >> (i)) & 1)

void Solve()
{
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;

    int k = m * 2 + 1;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < (1 << k); ++j)
            if (dp[i][j])
            {
                for (int t = max(0, i - m); t < n && t <= i + m; ++t)
                {
                    // bit h cua x la so thu t = i - m + h => h = t + m - i

                    // assert(t + m - i < k && t + m - i >= 0);

                    int mask = j;

                    if (!bit(t + m - i, mask))
                    {
                        mask |= 1 << (t + m - i);
                        if (i < m || bit(0, mask))
                            (dp[i + 1][mask >> 1] += dp[i][j]) %= mod;
                    }
                }
            }

    cout << dp[n][(1 << m) - 1] << "\n";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("tests.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }

    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        // cout << "Case #" << _ << ": ";
        Read();
        // Solve();
    }
    // //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

/*
1
3
1 0
1 1 2
0 3 4
*/