[滋磁去我的博客看吖](http://www.vixbob-lwc.pw/2019/05/18/BJOI2019/)
又是二合一...
下文中$x^{\underline{n}}$表示$x$的$n$次下降幂，即：$x^{\underline{n}}=\prod_{i=1}^n(x-i+1)$
先考虑第一问：
这个东西实际上就上要我们求：
$$\sum_{i=l}^r\binom{f[i]}{k}$$
$f[i] = fib[i+1]$.
考虑展开：
$$\sum_{i=l}^r\frac{f[i]^{\underline{k}}}{k!}$$
想的时候是往生成函数方面想的，你直接把$x^{\underline{n}}$看成一个$n$次多项式就可以把这个下降幂转成一个幂和的形式了。事后发现原来这个多项式的系数就是有符号第一类斯特林数.....(~~没学过，告辞~~)
然后有：
$$\frac{1}{k!}\sum_{i=l}^r\sum_{j=1}^k\begin{bmatrix}k\\j\end{bmatrix}_sf[i]^j$$
显然有$f[i]$的递推式：
$$\begin{cases}f[n]=1, 0\le n\le1\\f[n]=f[n-1]+f[n-2],n>1\end{cases}$$
然后我们用特征方程解一下可得：
$$f[n]=\frac{5+\sqrt5}{10}\left(\frac{1+\sqrt5}{2}\right)^n+\frac{5-\sqrt5}{10}\left(\frac{1-\sqrt5}{2}\right)^n$$
则$f[n]$可以被表示为$A\alpha^n+B\beta^n$的形式，我们把这个代回上式有：
$$\begin{aligned}&\frac{1}{k!}\sum_{i=l}^r\sum_{j=1}^k\begin{bmatrix}k\\j\end{bmatrix}_s\left(A\alpha^i+B\beta^i\right)^j\\=&\frac{1}{k!}\sum_{i=l}^r\sum_{j=1}^k\begin{bmatrix}k\\j\end{bmatrix}_s\sum_{v=0}^j\binom{j}{v}A^v\alpha^{iv}B^{j-v}\beta^{i(j-v)}\\=&\frac{1}{k!}\sum_{j=1}^k\begin{bmatrix}k\\j\end{bmatrix}_s\sum_{v=0}^j\binom{j}{v}A^vB^{j-v}\sum_{i=l}^r(\alpha^{v}\beta^{j-v})^i\end{aligned}$$
后面明显是个等差数列的形式直接用公式就好了。(注意存在公比为一的情况)
但是有个问题就是$\sqrt5$在膜$998244353$的意义下并不存在。我们可以尝试模仿复数，也搞一个"虚部"$i$，只不过这个$i^2=5$。因为斐波那契数列最后求出来一定是个整数所以虚部的系数一定为$0$.
考虑第二问：
先考虑求出这个东西的递推式，首先$n$为奇数的时候方案肯定等于零。所以我们设$g_i$表示$n =2\times i$的方案数。
考虑怎么递推，首先最后的一个$3 \times 2$的块中有三种摆放方式，但这一种转移肯定是漏掉了一些方案的，实则我们可以跨越最后一个偶数位置，如图：
然后我们枚举一下第二种情况跨越红线的数量就有递推式：
$$\begin{aligned}g[n]&=3\times g[n-1]+2\times\sum_{i=1}^{n-1}g[n-1-i]\\&=3 \times g[n-1]+2\times\sum_{i=0}^{n-2}g[i]\end{aligned}$$
则有：
$$\begin{cases}g[n]=3 \times g[n-1]+2\times\sum_{i=0}^{n-2}g[i]\\g[n+1]=3\times g[n]+2\times g[n-1]+2\times \sum_{i=0}^{n-2}g[i]\end{cases}$$
差分一下：
$$g[n+1]=4 \times g[n]-g[n-1]$$
也就是说$g[n]$的递推式为：
$$\begin{cases}g[n]=1,n=0\\g[n]=3,n=1\\g[n]=4 \times g[n-1]-g[n-2],n>1\end{cases}$$
用特征方程方程解得：
$$g[n]=\frac{3+\sqrt3}{6}(2+\sqrt3)^n+\frac{3-\sqrt3}{6}(2-\sqrt3)^n$$
然后就是一模一样的了。复杂度$O(k^2 \log{(r-l)})$。
代码：
```cpp
/*
* 3090.cpp
* This file is part of 3090
*
* Copyright (C) 2019 - ViXbob
*
* 3090 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 3090 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 3090. If not, see <http://www.gnu.org/licenses/>.
*/
/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int maxn = 5e2 + 15;
const int P = 998244353;
const int inf = 0x3f3f3f3f;
int T, m, k, sqr, C[maxn][maxn], S[maxn][maxn], V, ans, fac[maxn], ifac[maxn];
ll l, r, n, N;
inline ll read() {
char ch = getchar(); ll u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}
struct Complex {
int x, y;
Complex(int a = 0, int b = 0) { x = a; y = b; }
Complex operator + (const Complex &t) const { return Complex((x + t.x) % P, (y + t.y) % P); }
Complex operator - (const Complex &t) const { return Complex((x - t.x + P) % P, (y - t.y + P) % P); }
Complex operator * (const Complex &t) const { return Complex((1ll * x * t.x % P + 1ll * V * y % P * t.y % P) % P, (1ll * x * t.y % P + 1ll * y * t.x % P) % P); }
Complex operator * (const int &t) const { return Complex(1ll * x * t % P, 1ll * y * t % P); }
} A, B, alpha, beta;
inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int ksm(int x, ll k, int rnt = 1) {
for(ll i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}
inline Complex ksm(Complex x, ll k, Complex rnt = Complex(1, 0)) {
for(ll i = k; i; i >>= 1, x = x * x) if(i & 1) rnt = rnt * x;
return rnt;
}
inline Complex Inv(Complex a) { return Complex(a.x, P - a.y) * inv((1ll * a.x * a.x % P - 1ll * V * a.y % P * a.y % P + P) % P); }
const int inv2 = inv(2), inv10 = inv(10), inv6 = inv(6);
int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
T = read(); m = read(); V = (m == 2) ? 5 : 3; S[1][1] = 1;
rep(i, 0, maxn - 1) C[i][0] = 1;
rep(i, 1, maxn - 1) rep(j, 1, i) C[i][j] = pls(C[i - 1][j - 1], C[i - 1][j]);
rep(i, 2, maxn - 1) rep(j, 1, i) S[i][j] = dec(S[i - 1][j - 1], mul(i - 1, S[i - 1][j]));
fac[0] = 1;
rep(i, 1, maxn - 1) fac[i] = 1ll * fac[i - 1] * i % P;
ifac[maxn - 1] = inv(fac[maxn - 1]);
dep(i, maxn - 2, 0) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
while(T--) {
l = read(); r = read(); k = read(); ans = 0; N = r - l + 1;
if(m == 2) {
A = Complex(inv2, inv10); B = Complex(inv2, P - inv10);
alpha = Complex(inv2, inv2); beta = Complex(inv2, P - inv2);
} else {
// l -= !(l & 1); r += (r & 1);
// l = l + 1 >> 1; r >>= 1;
l = l + 1 >> 1; r >>= 1;
A = Complex(inv2, inv6); B = Complex(inv2, P - inv6);
alpha = Complex(2, 1); beta = Complex(2, P - 1);
} n = r - l + 1;
// cerr << (A * ksm(alpha, 3) + B * ksm(beta, 3)).x << endl;
// cerr << l << " " << r << " " << n << endl;
rep(i, 1, k) {
Complex tmp(0, 0);
rep(j, 0, i) {
Complex c = ksm(A, j) * ksm(B, i - j);
Complex q = ksm(alpha, j) * ksm(beta, i - j);
Complex goal = (ksm(q, n + 1) - q) * Inv(q - Complex(1, 0));
if(q.x == 1 && q.y == 0) goal = q * (n % P);
tmp = tmp + c * goal * C[i][j] * ksm(q, l - 1);
}
// cerr << tmp.x << " " << tmp.y << " " << S[k][i] << endl;
ans = (ans + 1ll * S[k][i] * tmp.x % P) % P;
}
printf("%d\n", 1ll * ans * inv(N % P) % P * ifac[k] % P);
}
return 0;
}
/*
1 2 3 5
1 + 3 + 10
14 / 3
x
x(x-1)=-x+x^2
x(x-1)(x-2)=(x^2-x)(x-2)=2x-3x^2+x^3
(x^3-3x^2+2x)(x-3)=-6x+11x^2-6x^3+x^4
0 0 0 0 0 0 0 0 1 -1
0 0 0 0 0 0 0 1 -3 2
0 0 0 0 0 0 1 -6 11 -6
0 0 0 0 0 1 -10 35 -50 24
f[1]
f[2]
f[3] = f[1] * f[2]
f[4] = f[1] * f[2] ^ 2
f[5] = f[1] ^ 2 * f[2] ^ 3
f[6] = f[1] ^ 3 * f[2] ^ 5
f[7] = f[1] ^ 5 * f[2] ^ 8
f[n] = f[n - 1] * f[n - 2]
f[n] = f[1] ^ fib[n - 2] * f[2] ^ fib[n - 1];
1 1 2 3 5 8 13
*/
```