题目描述

若若最近学会了常系数齐次线性递推！他非常开心，每天对着各种数列算啊算。

不过这一天，他遇到了两个奇怪的数列：

$$A_i = (a - 1) \cdot A_{i - 1} + a \cdot B_{i - 1}$$

$$B_i = b \cdot A_{i - 1} + (b - 1) \cdot B_{i - 1}$$

现在，若若已经知道一个数字 $n$，以及常数 $a$ 和 $b$，还有数列 $A$ 和 $B$ 的初值（$A_0$，$B_0$），他想请你帮忙算出 $A_n$。

输入格式

输入由多组数据构成。

第一行一个正整数 $T$ ($1 \leq T \leq 10^5$)，表示共有 $T$ 组数据。

对于每组数据：

第一行三个整数 $n$ ($0 \leq n \leq 10^9$)，$a$ ($1 \leq a \leq 10^9$)，$b$ ($1 \leq b \leq 10^9$)，用一个空格隔开，含义如题目描述所示。

第二行两个正整数 $A_0$ ($1 \leq A_0 \leq 10^9$) 和 $B_0$ ($1 \leq B_0 \leq 10^9$)，用一个空格隔开，表示数列 $A$ 和 $B$ 的初值。

输出格式

对于每组数据，输出一行一个非负整数 $x$，表示 $A_n$ 对 $10^9 + 7$ 取模的值。

样例

样例输入

1
1 5 7
2 3

样例输出

23