Tính hàm

Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử $1$ và $1$, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử bằng tổng hai phần tử trước nó. Công thức truy hồi của dãy Fibonacci như sau:

$$Fibonacci(n)=\{\begin{array}{cc}1\hfill & \text{nếu }n=1\hfill \\ 1\hfill & \text{nếu }n=2\hfill \\ Fibonacci(n-1)+Fibonacci(n-2)\hfill & \text{nếu }n>2\hfill \end{array}$$

Xét hàm $f(x,y)$ sau:

$$f(x,y)=\{\begin{array}{cc}y\hfill & \text{nếu }x=0\hfill \\ x\hfill & \text{nếu }y=0\hfill \\ \alpha \times f(x-1,y)+\beta \times f(x,y-1)+g(x,y)\hfill & \text{nếu }x\ne 0\text{ và }y\ne 0\hfill \end{array}$$

Trong đó, $g(x,y)$ là ước số chung lớn nhất của $Fibonacci(x)$ và $Fibonacci(y)$.

Yêu cầu: Cho $4$ số nguyên không âm $x,y,\alpha ,\beta$ và số nguyên dương $B$, hãy tính $f(x,y)modB$ (phần dư của $f(x,y)$ khi chia cho $B$, kể cả khi $x=0$ hoặc $y=0$).

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương $K$ là số lượng bộ dữ liệu.
• Tiếp đến là $K$ dòng, mỗi dòng chứa $5$ số nguyên $x,y,\alpha ,\beta ,B$ tương ứng với một bộ dữ liệu.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra

Gồm $K$ dòng, mỗi dòng ghi một số nguyên là giá trị $f(x,y)modB$ tính được tương ứng với bộ dữ liệu.

Ràng buộc

• $1\le K\le 10$.
• $0\le x,y\le 500$.
• $0\le \alpha ,\beta \le {10}^{18}$; $1\le B\le {10}^{18}$.

Subtasks

• Subtask 1 ($20$ điểm): $x,y\le 10$; $\alpha ,\beta ,B\le {10}^6$.
• Subtask 2 ($20$ điểm): $x,y\le 50$; $\alpha ,\beta ,B\le {10}^9$.
• Subtask 3 ($15$ điểm): $x,y\le 50$; $\alpha ,\beta ,B\le {10}^{18}$.
• Subtask 4 ($15$ điểm): $x,y\le 500$; $\alpha ,\beta ,B\le {10}^{18}$.

Ví dụ