---
tags: 卓越盃程式競賽
---

# pE. Steal A Safe

## 題目敘述 :
宜中偷分大師現在想偷點不同的東西了，為了證明自己的實力，他決定偷裡面僅有一個寫著卓岳的馬克杯的保險箱，這個保險箱是一個正方體，大致如下。

<img src="https://live.staticflickr.com/65535/51845741175_f109a92952_o.png" width="696" height="564" alt="pic1">

上面有一個密碼鎖(請原諒我畫不出來)，卻沒有重置密碼的按鈕，因此他認為此保險箱的密碼是固定的。這時，他發現保險箱側邊有一個類似金字塔的東西，用的是不同的金屬。用電子顯微鏡一看，竟發現上面有規律地排列。然而以他薄弱的計算能力，他認為他一定會算錯。而且金字塔的層數過多，增長又很快，更是讓他打消手算的念頭。然而他不會寫程式，因而請你幫忙。

為了避免讓你花太多時間(後面還有題目)，他已經幫你把他們的遞迴關係式列出來了，如下。

$$
\begin{cases}
S_1=x_1, \, S_2=x_2\\
S_n=a \times S_{n-1} + b \times S_{n-2} + cn^2 + d \times 2^n\\
\end{cases}
$$

很明顯這個數字會很大，因此他猜想可能要對某數取餘。且因保險箱的設計者是一個常年在 $ICPC$ 破台的高手，因此他猜模數 $(M)$ 應該是 $10^9+7$ 或是 $998244353$ 。請算出 $n$ 層的原子數(記得對 $M$ 取餘)。

## 輸入說明 :

第一行輸入 $t$。
接著輸入 $t$ 行，每行 $8$ 個數字，分別為 $x_1 \; x_2 \; a \; b \; c \; d \; n \; M$ ，其意義如上所述。

$t \le 10^3$
$x_1, \; x_2 \le 10^3$
$a, \; b, \; c, \; d \le 100$
$n \le 10^{12}$
$M \in \{\, 10^9+7,998244353 \,\}$

## 輸出說明 :

輸出 $t$ 個數字 $S_n$ (記得對 $M$ 取餘)，數字間要換行。

## 範例輸入1 :

1
1 1 1 1 0 0 3 1000000007

## 範例輸出1 :

2

## 範例輸入2 :

2
727 434 77 62 32 82 977211338887 1000000007
1 1 2 3 2 1 3 1000000007

## 範例輸出2 :

857215810
31

## 子題組與配分

- 第一子題組 : $n \le 10^5, \; t\le10$ $\;\;\;\;\;\;\;\;\;\;\;\;\;\;15\%$
- 第二子題組 : $x_1,x_2,a,b=1, \; c,d=0 \;\;\; 25\%$
- 第三子題組 : 無其他限制$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;60\%$