#P7988. Pty loves SegmentTree

    ID: 8000 传统题 15000ms 512MiB 尝试: 6 已通过: 2 难度: 9 上传者: 标签>难度分类省选/NOI-多项式与生成函数普通生成函数导数积分转化生成函数求系数组合数学递推计数Catalan 数数论逆元线性递推排序与序列处理一维前缀和CF2700

Pty loves SegmentTree

Pty loves SegmentTree

题目描述

Consider rooted interval trees. A node represents an interval [l,r][l,r]. If l=rl=r, it is a leaf; otherwise choose any integer mid∈[l,r−1]\mathrm{mid}\in[l,r-1], with left child [l,mid][l,\mathrm{mid}] and right child [mid+1,r][\mathrm{mid}+1,r].

Assign weight 1 to each leaf. An internal node has weight AA if its right child's interval contains exactly kk integers, and weight BB otherwise. The weight of a tree is the product of all its node weights.

Let fnf_n be the sum of the weights of all such trees rooted at [1,n][1,n]. Different ordered tree shapes count separately.

For each query L,RL,R, compute

∑i=LR(fi)2(mod998244353).\sum_{i=L}^{R}(f_i)^2\pmod{998244353}.

输入格式

The first line contains TT (1≤T≤51\le T\le5).

For each case, the first line contains Q,k,A,BQ,k,A,B, where 1≤Q≤5×1041\le Q\le5\times10^4, 1≤k≤1071\le k\le10^7, and 0≤A,B<9982443530\le A,B<998244353.

The next QQ lines each contain L,RL,R (1≤L≤R≤1071\le L\le R\le10^7).

输出格式

For each query, print the answer on one line.

样例输入1

1
1 1 3 1
4 4

样例输出1

3249

样例说明

For n=4n=4, the five ordered shapes have weights 3,9,9,9,273,9,9,9,27. Thus f4=3+3×9+27=57f_4=3+3\times9+27=57, and the answer is 572=324957^2=3249.