题目：https://loj.ac/problem/3090
题解：https://www.luogu.org/blog/rqy/solution-p5320
1.用斯特林数把下降幂化为普通的幂次求和
2.找出通项公式，使得幂次变成二项式，进而将 [ l , r ] 的部分变成等比数列求和
3.模 998244353 下没有 \( \sqrt{5} \) ，所以“扩域”，就是把数表示成 \( a+b*\sqrt{5} \) ；\( \sqrt{3} \) 也同理
注意扩域之后，不满足费马小定理，所以快速幂的指数不能对 ( mod-1 ) 取模！！！
还是不太知道怎么求的通项。为什么是 \( f[n]=A*x_{1}^{n}+B*x_{2}^{n} \) 的形式呢？如果不是二阶怎么推？
UPD:
设特征根是 x1,x2,...,xk，因为 x^n 是通解，又有线性性（？），所以通项可以写成 \( f(i)=A*x_1^i + B*x_2^i + ... \)
但是有重根的话就不是这样。 k 重根的系数是次数界为 k 的多项式。这里的次数指的是 i 的几次幂。
（k重根是针对根而言的，比如一个六次方程，x1=x2=2 , x3=5 , x4=x5=x6=1，那么 2 是2重根，5是单根，1是3重根）
比如，\( f_i = 2*f_{i-1} - f_{i-2} \)，\( f_0 = 1 , f_1 = 2 \)
解出特征根是 x1=x2=1 ，那么可以设通项公式为 \( f(i)=(A*i+B)x^i \) ，解得 A=B=1 。
又如，\( f_i = 4*f_{i-1} - f_{i-2} \) ， \( f_0 = 1 , f_1 = 7 \)
解出特征根是 x1=x2=2 ，设通项是 \( f(i)=(A*i+B)x^i \) ，解得 \( A=\frac{5}{2} , B=1 \)
^ ^
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll rdn()
{
ll ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
const int N=,mod=;
int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;}
int pw(int x,ll k)
{int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;} int k,s1[N][N],c[N][N],bs,tlen2,ans;ll tl,tlen;
struct Node{
int x,y;
Node(int x=,int y=):x(x),y(y) {}
Node operator+ (const Node &b)const
{ return Node(upt(x+b.x),upt(y+b.y));}
Node operator- (const Node &b)const
{ return Node(upt(x-b.x),upt(y-b.y));}
Node operator* (const Node &b)const
{ return Node(((ll)x*b.x+(ll)bs*y%mod*b.y)%mod,((ll)y*b.x+(ll)x*b.y)%mod);}
}A[N],B[N],x1[N],x2[N],one;
Node pw(Node x,ll k)
{ Node ret=Node(,);
while(k){if(k&)ret=ret*x;x=x*x;k>>=;}return ret;}
Node Inv(Node u)
{
int tp=upt(((ll)u.x*u.x-(ll)bs*u.y%mod*u.y)%mod);
tp=pw(tp,mod-);
return Node((ll)u.x*tp%mod,upt(-(ll)u.y*tp%mod));
}
void init(int lx)
{
s1[][]=;
for(int i=;i<=k;i++)
for(int j=;j<=i;j++)
s1[i][j]=(s1[i-][j-]+(ll)s1[i-][j]*(i-))%mod;
for(int i=;i<=k;i++)c[i][]=;
for(int i=;i<=k;i++)
for(int j=;j<=i;j++)
c[i][j]=upt(c[i-][j-]+c[i-][j]); one=Node(,);
if(lx==)
{
int tp=pw(,mod-); A[]=Node(,tp); B[]=Node(,upt(-tp));
tp=pw(,mod-); x1[]=Node(tp,tp); x2[]=Node(tp,upt(-tp));
}
else
{
int tp=pw(,mod-); A[]=Node((ll)*tp%mod,tp);
B[]=Node((ll)*tp%mod,upt(-tp));
x1[]=Node(,); x2[]=Node(,upt(-));
}
A[]=one; for(int i=;i<=k;i++)A[i]=A[i-]*A[];
B[]=one; for(int i=;i<=k;i++)B[i]=B[i-]*B[];
x1[]=one; for(int i=;i<=k;i++)x1[i]=x1[i-]*x1[];
x2[]=one; for(int i=;i<=k;i++)x2[i]=x2[i-]*x2[];
}
Node cal(Node x)
{
if(x.x==&&x.y==)return Node(tlen2,);//tlen2 not tlen!!!
Node d=Inv(one-x);
d=d*pw(x,tl)*(one-pw(x,tlen));
return d;
}
void solve2()
{
ll l=rdn(),r=rdn(); k=rdn(); bs=; init();
int iv=pw((r-l+)%mod,mod-); l++; r++;
tl=l; tlen=(r-l+); tlen2=(r-l+)%mod;
for(int i=,fx=((k&)?upt(-):);i<=k;i++,fx=upt(-fx))
{
int tp=;
for(int j=;j<=i;j++)
{
Node tmp=x1[j]*x2[i-j];
Node d=cal(tmp)*A[j]*B[i-j];
tp=(tp+(ll)c[i][j]*d.x)%mod;
}
ans=(ans+(ll)s1[k][i]*fx%mod*tp)%mod;
}
ans=(ll)ans*iv%mod;
int ml=; for(int i=;i<=k;i++)ml=(ll)ml*i%mod;
ans=(ll)ans*pw(ml,mod-)%mod;
}
void solve3()
{
ll l=rdn(),r=rdn(); k=rdn(); bs=; init();
int iv=pw((r-l+)%mod,mod-); l=(l+)>>; r=r>>;
tl=l; tlen=(r-l+); tlen2=(r-l+)%mod;
for(int i=,fx=((k&)?upt(-):);i<=k;i++,fx=upt(-fx))
{
int tp=;
for(int j=;j<=i;j++)
{
Node tmp=x1[j]*x2[i-j];
Node d=cal(tmp)*A[j]*B[i-j];
tp=(tp+(ll)c[i][j]*d.x)%mod;
}
ans=(ans+(ll)s1[k][i]*fx%mod*tp)%mod;
}
ans=(ll)ans*iv%mod;
int ml=; for(int i=;i<=k;i++)ml=(ll)ml*i%mod;
ans=(ll)ans*pw(ml,mod-)%mod;
}
int main()
{
int op=rdn(); op=rdn();
if(op==)solve2(); else solve3();
printf("%d\n",ans);
return ;
}