#P5166. 「长乐国庆集训2018ROUND3」2.国家
「长乐国庆集训2018ROUND3」2.国家
Description
给定正整数和非负整数,求 ,例如当时,该结果等于。由于答案可能很大,请对取模。
Input Format
多组数据。
第一行,一个正整数,表示数据组数。
接下来行,每行四个整数,表示一组数据,相邻两个数之间有空格隔开。
Output Format
共行,每行一个非负整数,表示一组数据的答案。
Sample
【样例输入】
3
2 3 3 233
5 1 2 100
1000 233 666 998244353
【样例输出】
27
63
952904376
另一组见附加文件(如果有)
Hint
对于30%的数据,满足,,。
对于60%的数据,满足,,。
另有10%的数据,满足。
另有10%的数据,满足。
对于100%的数据,满足,。