#P18086. Unreachable Land

Unreachable Land

Unreachable Land

题目描述

给定三个整数 a,b,ma,b,m,进行 mm 轮操作。第 ii 轮,你可以选择执行

a←a mod (m−i+1),a\leftarrow a\bmod(m-i+1),

也可以选择不修改 aa。求所有操作结束后 a=ba=b 的方案数,对 998244353998244353 取模。

若两个方案在至少一轮是否选择执行取模操作上不同,就视为不同方案。即使取模前后数值相同,执行取模和不执行仍是两种不同的选择。

输入格式

第一行一个整数 tt,表示测试组数。接下来每组一行,包含三个整数 a,b,ma,b,m。

1≤t≤1051\le t\le10^5,0≤b<m≤a≤2⋅1050\le b<m\le a\le2\cdot10^5;所有组的 aa 之和不超过 2⋅1052\cdot10^5。

输出格式

每组输出一行,表示方案数对 998244353998244353 取模的结果。

样例输入

5
5 0 5
5 2 3
10 1 7
10 6 10
100000 114 514

样例输出

25
1
14
0
837481226