题目描述

已知数列 \(A\) ,他的长度为 \(n\) ,第 \(i\) 个数在 \(B^C+C^A-i!\sum^i_{k=0}\frac{(A+C)^k(B+C)^{i-k}}{k!(i-k)!}+A^B \)
和 \( A^B+B^C+C^A+(A+B+2C)^i \)的两个解间完全随机。

对于随机数 \(X\) , \(Y\) ,令 \( L=min(X,Y) \) , \( R=max(X,Y) \) ,求 \( A_L+A_{L+1}+ \dots + A_{R-1}+A_R \) 的期望值。

输入格式

第一行一个数字 \(T\) 表示询问个数

每个询问输入四个整数,分别表示 \( n \) , \( A \) , \( B \) , \( C \) 。

输出格式

对于每个询问,输出一行表示答案。

样例

样例输入 1

5
3 1 1 1
3 2 2 2
5 5 2 3
6 1 2 3
114 514 1919 810

样例输出 1

818000003
817999978
736185537
409000013
1080997123

提示说明

数据编号	\(n,A,B,C\le\)	\(T\le\)
\(0-4\)	\(10\)	\(10\)
\(5-9\)	\(10^3\)	\(10\)
\(10-19\)	\(10^6\)	\(10\)
\(20-49\)	\(10^9\)	\(10^4\)

~~下次再有人弄这么多测试点就踢出团队~~