UVa 12045 - Fun with Strings

// UVa 12045 - Fun with Strings

#include <stdio.h>
#include <vector>
using namespace std;

#define ll long

ll P = 1000000007;

#define MAX_N 2
struct SquareMatrix {
	ll mat[MAX_N][MAX_N];
};

SquareMatrix matMult(SquareMatrix a, SquareMatrix b) {
	// Matrix multiplication of two square matrices (N x N)
	SquareMatrix ans;
	int k, n = MAX_N;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (ans.mat[i][j] = k = 0; k < n; k++) {
				ans.mat[i][j] += a.mat[i][k] * b.mat[k][j];
				//if necessary do modulo arithmetic here:
				ans.mat[i][j] %= P;
			}
	return ans;
}

SquareMatrix matPow(SquareMatrix base, int p) {
	// Finds base^p in O(n^3 log p) where base is a square matrix of dimensions n by n
	SquareMatrix ans;
	// prepare identity matrix
	int n = MAX_N;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			ans.mat[i][j] = (i == j) ? 1 : 0;

	// exponentiation
	while (p) {
		if (p & 1)
			ans = matMult(ans, base);
		base = matMult(base, base);
		p >>= 1;
	}
	return ans;
}

pair<ll, ll> findFibs(int n) {
	// Returns Fibonacci n-1 and n
	SquareMatrix a;
	a.mat[0][0] = 1;
	a.mat[0][1] = 1;
	a.mat[1][0] = 1;
	a.mat[1][1] = 0;
	SquareMatrix sol = matPow(a, n);
	return pair<ll, ll>(sol.mat[1][1], sol.mat[0][1]);
}

ll modMult(ll a, ll b) {
	return (a * b) % P;
}
ll modSum(ll a, ll b) {
	return (a + b) % P;
}
ll modSubst(ll a, ll b) {
	return (a + (P - b)) % P;
}
ll modPow(ll base, ll exponent) {
	if (exponent == 0)
		return 1;
	ll root = modPow(base, exponent / 2);
	if (exponent & 1)
		return modMult(modMult(root, root), base);
	else
		return modMult(root, root);
}
ll modDiv(ll a, ll b) {
	return modMult(a, modPow(b, P - 2));
}

pair<ll, ll> solve(int n, int m, int x, int y) {
	pair<ll, ll> p = findFibs(n);
	ll Fn = p.second, Fn1 = (p.second + p.first) % P;
	p = findFibs(m);
	ll Fm = p.second, Fm1 = (p.second + p.first) % P;

	ll b1 = modSubst(modMult(x, Fm), modMult(y, Fn));
	ll b2 = modSubst(modMult(Fn1, Fm), modMult(Fm1, Fn));
	ll b = modDiv(b1, b2);

	ll a = modDiv(modSubst(y, modMult(Fm1, b)), Fm);

	return pair<ll, ll>(a, b);
}

ll lengthOf(ll k, ll a, ll b) {
	pair<ll, ll> p = findFibs(k);
	ll Fk = p.second, Fk1 = (p.second + p.first) % P;
	return modSum(modMult(a, Fk), modMult(b, Fk1));
}

int noModLengthOf(int k, int a, int b) {
	pair<ll, ll> p = findFibs(k);
	ll Fk = p.second, Fk1 = p.second + p.first;
	return a * Fk + b * Fk1;
}

bool satisfy(int a, int b, int n, int x) {
	ll xx = noModLengthOf(n, a, b);
	return xx == x;
}

int main() {

	int cases;
	scanf("%d", &cases);
	for (; cases; cases--) {
		int n, x, m, y, k;
		scanf("%d %d %d %d %d", &n, &x, &m, &y, &k);

		pair<ll, ll> ab = solve(n, m, x, y);

		ll a = ab.first, b = ab.second;

		if (satisfy(a, b, n, x) && satisfy(a, b, m, y))
			printf("%lld\n", lengthOf(k, ab.first, ab.second));
		else
			printf("Impossible\n");
	}

	return 0;
}