hdu 3509

推导公式的题目，矩阵幂关键就在于构造系数矩阵
备忘：
S(n, k) - S(n - 1, k) = Fn ^ k
当Fn能够线性表示的时候，S(n, k) = S(n - 1, k) + Fn ^ k 不也是线性表示嘛!

Fn ^ k = sigma( C(k, i) * a^i * b^(k-i) * Fn-1^i * Fn-2^(k-i) ) 其中0 <= i <= k

备忘2：
构造矩阵系数的时候，要用 += 把相应的项的系数加上去，而不是直接 =

备忘3：
快速幂的复杂度很低，所以基本不用考虑常数

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v << ": " << (v) << endl
using namespace std;
typedef long long LL;

LL f1[52], f2[52], a[52], b[52], k, n, m;

LL C[52][52];
void make1() {
	C[0][0] = 1;
	for (int i = 1; i <= 50; ++i) {
		C[i][0] = C[i][i] = 1;
		for (int j = 1; j < i; ++j)
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % m;
	}
	a[0] = 1;
	for (int i = 2; i <= 50; ++i) a[i] = (a[i - 1] * a[1]) % m;
	b[0] = 1;
	for (int i = 2; i <= 50; ++i) b[i] = (b[i - 1] * b[1]) % m;
	f1[0] = 1;
	for (int i = 2; i <= 50; ++i) f1[i] = (f1[i - 1] * f1[1]) % m;
	f2[0] = 1;
	for (int i = 2; i <= 50; ++i) f2[i] = (f2[i - 1] * f2[1]) % m;
}

typedef LL matrix[52][52];
void copy(int size, matrix X, matrix Y) {
	for (int i = 0; i < size; ++i)
		for (int j = 0; j < size; ++j)
			Y[i][j] = X[i][j];
}
void mutiply(int size, matrix _X, matrix _Y, matrix Z) {
	matrix X, Y;
	copy(size, _X, X); copy(size, _Y, Y);
	for (int i = 0; i < size; ++i)
		for (int j = 0; j < size; ++j) {
			Z[i][j] = 0;
			for (int k = 0; k < size; ++k)
				Z[i][j] = (Z[i][j] + X[i][k] * Y[k][j]) % m;
		}
}
void ident(int size, matrix X) {
	for (int i = 0; i < size; ++i)
		for (int j = 0; j < size; ++j)
			X[i][j] = (i == j ? 1 : 0);
}
void power(int size, matrix _X, LL n, matrix Y)
{
	ident(size, Y);
	matrix X; copy(size, _X, X);
	while (n) {
		if (n & 1) mutiply(size, Y, X, Y);
		n >>= 1;
		if (n) mutiply(size, X, X, X);
	}
}
void print(int size, matrix X) {
	for (int i = 0; i < size; ++i) { 
		for (int j = 0; j < size; ++j)
			cout << X[i][j] << " ";
		cout << endl;
	}
}
void clear(int size, matrix X) {
	for (int i = 0; i < size; ++i)
		for (int j = 0; j < size; ++j)
			X[i][j] = 0;
}

matrix A;
void make2() {
	clear(k + 2, A);
	for (int i = 0; i <= k; ++i)
		for (int j = 0; j <= i; ++j)
			A[i][k - (i - j)] = (A[i][k - (i - j)] + C[i][j] * a[j] % m * b[i - j]) % m;
	for (int j = 0; j <= k; ++j)
		A[k + 1][j] = (A[k + 1][j] + C[k][j] * a[j] % m * b[k - j]) % m;
	A[k + 1][k + 1] = 1;
	
	//cout << "A" << endl; print(k + 2, A);
}

int main()
{
	int T;
	cin >> T;
	while (T--) {
		cin >> f1[1] >> f2[1] >> a[1] >> b[1] >> k >> n >> m;
		make1();
		make2();
		if (n == 1) {
			cout << f1[k] % m << endl;
			continue;
		} else if (n == 2) {
			cout << (f1[k] + f2[k]) % m << endl;
			continue;
		}
		
		LL p[52];
		for (int i = 0; i <= k; ++i)
			p[i] = f2[i] * f1[k - i] % m;
		p[k + 1] = (f2[k] + f1[k]) % m;
		matrix D;
		power(k + 2, A, n - 2, D);
		//cout << "D" << endl; print(k + 2, D);
		LL ans = 0;
		for (int j = 0; j <= k + 1; ++j)
			ans = (ans + D[k + 1][j] * p[j] % m) % m;
		cout << ans << endl;
	}
	return 0;
}