1895F - Fancy Arrays - CodeForces Solution

/*******************************
| Author:  starfish_
| Problem: F. Fancy Arrays
| Contest: Codeforces - Educational Codeforces Round 157 (Rated for Div. 2)
| URL:     https://codeforces.com/contest/1895/problem/F
| When:    2023-11-09 16:26:46
|
| Memory:  512 MB
| Time:    4000 ms
*******************************/
#include<bits/stdc++.h>
#define int long long
using namespace std; void solve();

#define SZ(pigstar) ((int)(pigstar).size())
#define all(pigstar) pigstar.begin(),pigstar.end()
#define fi first
#define se second
typedef long long ll;

const int maxn = 1e6 + 7, mod = 1e9 + 7;
struct combination {combination(int n, ll mo) {siz = n, mod = mo; inv.resize(n + 1, 1), infac.resize(n + 1, 1), fac.resize(n + 1, 1); for (int i = 2; i <= n; i++)inv[i] = (mod - mod / i) * inv[mod % i] % mod, infac[i] = infac[i - 1] * inv[i] % mod; for (long long i = 2; i <= n; i++)fac[i] = fac[i - 1] * i % mod;} ll C(int n, int m) {if (n == 0 && m == 0)return 1; if (n < m || m < 0 || n < 0)return 0; return fac[n] * infac[m] % mod * infac[n - m] % mod;} ll A(int n, int m) {if (n == 0 && m == 0)return 1; if (n < m || m < 0 || n < 0)return 0; return fac[n] * infac[n - m] % mod;} vector<ll>inv; vector<ll>infac; vector<ll>fac; private: int siz; ll mod;};
ll qmi(ll a, ll b, ll p = mod) {ll res = 1; a %= p; assert(b >= 0); for (; b; b >>= 1) {if (b & 1)res = res * a % p; a = a * a % p;} return res;}
template<class T>//[1,size-1]
struct segtree {int siz; vector<T>sum, minn, maxx, a; segtree(vector<T>&v) {a = v; siz = a.size() - 1; sum.resize(siz * 4 + 1), minn.resize(siz * 4 + 1), maxx.resize(siz * 4 + 1); build(1, 1, siz);} void upchange(int k, int l, int r, int x, T y) {if (l == r) {sum[k] = minn[k] = maxx[k] = y; return;} int mid = (l + r) >> 1; if (x <= mid)upchange(k << 1, l, mid, x, y); else upchange(k << 1 | 1, mid + 1, r, x, y); up(k);} void upadd(int k, int l, int r, int x, T y) {if (l == r) {sum[k] += y, minn[k] += y, maxx[k] += y; return;} int mid = (l + r) >> 1; if (x <= mid)upadd(k << 1, l, mid, x, y); else upadd(k << 1 | 1, mid + 1, r, x, y); up(k);} T qsum(int k, int l, int r, int x, int y) {if (l == x && r == y)return sum[k]; int mid = (l + r) >> 1; if (y <= mid)return qsum(k << 1, l, mid, x, y); else if (x > mid)return qsum(k << 1 | 1, mid + 1, r, x, y); else return qsum(k << 1, l, mid, x, mid) + qsum(k << 1 | 1, mid + 1, r, mid + 1, y);} T qmin(int k, int l, int r, int x, int y) {if (l == x && r == y)return minn[k]; int mid = (l + r) >> 1; if (y <= mid)return qmin(k << 1, l, mid, x, y); else if (x > mid)return qmin(k << 1 | 1, mid + 1, r, x, y); else return min(qmin(k << 1, l, mid, x, mid), qmin(k << 1 | 1, mid + 1, r, mid + 1, y));} T qmax(int k, int l, int r, int x, int y) {if (l == x && r == y)return maxx[k]; int mid = (l + r) >> 1; if (y <= mid)return qmax(k << 1, l, mid, x, y); else if (x > mid)return qmax(k << 1 | 1, mid + 1, r, x, y); else return max(qmax(k << 1, l, mid, x, mid), qmax(k << 1 | 1, mid + 1, r, mid + 1, y));} private: void build(int k, int l, int r) {if (l == r) {sum[k] = minn[k] = maxx[k] = a[l]; return;} int mid = (l + r) >> 1; build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r); up(k);} void up(int k) {sum[k] = sum[k << 1] + sum[k << 1 | 1], minn[k] = min(minn[k << 1], minn[k << 1 | 1]), maxx[k] = max(maxx[k << 1], maxx[k << 1 | 1]);}};
struct DSU {std::vector<int>f, siz; DSU(int n): f(n), siz(n, 1) {std::iota(f.begin(), f.end(), 0);} int leader(int x) {while (x != f[x])x = f[x] = f[f[x]]; return x;} bool same(int x, int y) {return leader(x) == leader(y);} bool merge(int x, int y) {x = leader(x); y = leader(y); if (x == y)return false; siz[x] += siz[y]; f[y] = x; return true;} int size(int x) {return siz[leader(x)];}};


signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(16);
    int times = 1, T = 1; cin >> T;
    for (int i = 1; i <= T; ++ i)
    {
        //cout << "Case " << (i) << ": ";
        solve();
    }
    return (0 - 0); //<3
}

int x;
// struct mat
// {
//     int f[41][41];
//     mat operator*(const mat &p) const
//     {
//         mat tmp;
//         memset(tmp.f, 0, sizeof(tmp.f));
//         for (int k = 0; k < x; k++)
//             for (int i = 0; i < x; i++)
//                 if (f[i][k])
//                     for (int j = 0; j < x; j++)
//                         tmp.f[i][j] = (tmp.f[i][j] + 1ll * f[i][k] * p.f[k][j] % mod) % mod;
//         return tmp;
//     }
// } base, now;

struct Matrix
{
    const static int N = 41;
    array<array<int, N>, N> m{};
    int n;

    // Constructor
    Matrix(int _n): n(_n) {}

    friend Matrix operator * (const Matrix& x, const Matrix& y)
    {
        Matrix res(x.n);
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                for (int k = 0; k < N; k++)
                {
                    res.m[i][j] = (1ll * res.m[i][j] + 1ll * x.m[i][k] * y.m[k][j] % mod) % mod;
                }
            }
        }
        return res;
    }

    friend Matrix operator ^ (const Matrix& x, long long b)
    {
        Matrix ans(x.n); ans.id();
        Matrix base = x;
        while (b)
        {
            if (b & 1) ans = ans * base;
            base = base * base; b >>= 1;
        }
        return ans;
    }

    Matrix &operator ^= (long long b)
    {
        *this = *this ^ b;
        return *this;
    }
    Matrix &operator *= (const Matrix& x)
    {
        *this = *this * x;
        return *this;
    }

    void id()
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                m[i][j] = i == j;
            }
        }
    }
};





void solve()
{

    int n, k;
    cin >> n >> x >> k;

    Matrix now(x), base(x);
    int ans = qmi((2 * k + 1) % mod, n - 1) * (x + k) % mod;

    for (int i = 0; i < x; i += 1) now.m[0][i] = 1;

    for (int i = 0; i < x; i += 1)
    {
        for (int j = 0; j < x; j += 1)
        {
            base.m[i][j] = abs(i - j) <= k;
        }
    }


    now = now * (base ^ (n - 1));

    for (int i = 0; i < x; i += 1)
    {
        ans = ans - now.m[0][i];
        if (ans < 0) ans += mod;
    }
    cout << ans << '\n';









}