题目背景
墓园的骷髅海!
要塞的禁魔球!
塔楼的三后排!
据点的破甲比蒙!
地下城的满魔抗黑龙!

塔楼↑
燊队来打英雄无敌 3 了。
题目描述
招魂术是墓园阵营的核心法术。
拥有招魂术的英雄,在每场战争结束后,能根据消灭的敌军数目来获得一定数量的骷髅。我们可以用整数 A,B 来描述招魂术。设 FA,B(i) 表示消灭 i 个敌人所能获得的骷髅数量,有:
FA,B(1)=A,FA,B(2)=B,FA,B(x)=⌊FA,B(x−2)FA,B(x−1)⌋+1(x≥3)现在燊队要在酒馆招募一个英雄,英雄甲招魂术的属性为 A,B,英雄乙招魂术的属性为 X,Y。为了比较两个英雄招魂术的强弱,请你计算以下式子的值:
i=1∏nFX,Y(i)−FA,B(i)
燊队当然知道怎么做,但他想考考你。
输入格式
第一行一个整数 T,表示询问组数。
接下来 T 行,每行五个整数 n,A,B,X,Y。
输出格式
输出为 T 行,即每组询问答案对 998244353 取模的结果。
建议使用 sqrtl
和 long double
进行开平方。
提示
样例说明
在样例说明中,设 FA,B 为 f,FX,Y 为 g。
对于第一组询问:
-
f 的前 n 位为 f={2,10,5,8,7}。
-
g 的前 n 位为 g={1,8,3,5,4}。
所以最终的答案为 (1−2)×(8−10)×(3−5)×(5−8)×(4−7)=−36,对 998244353 取模后的结果是 998244317。
数据范围
对于 40% 的数据,n≤100。
对于另外 10% 的数据,每组询问满足 A=B,X=Y。
对于另外 10% 的数据,T=1。
对于 100% 的数据,1≤A,B,X,Y,n≤109,1≤T≤5×104。