Description

给定正整数$n,p$和非负整数$a,b$，求 ，例如当$n=1$时，该结果等于$a+b$。由于答案可能很大，请对$p$取模。

Input Format

多组数据。

第一行，一个正整数$T$，表示数据组数。

接下来$T$行，每行四个整数$n,a,b,p$，表示一组数据，相邻两个数之间有空格隔开。

Output Format

共$T$行，每行一个非负整数，表示一组数据的答案。

Sample

【样例输入】

3
2 3 3 233
5 1 2 100
1000 233 666 998244353

【样例输出】

27
63
952904376

另一组见附加文件（如果有）

Hint

对于30%的数据，满足$T \le 10$，$n,a,b \le 10^6$，$p=10^9+7$。

对于60%的数据，满足$T \le 10,000$，$n,a,b \le 10^9$，$p=10^9+7$。

另有10%的数据，满足$a=0$。

另有10%的数据，满足$a=1$。

对于100%的数据，满足$T \le 30,000$，$n,a,b,p \le 10^{12}$。