Description：

$F[1][1]=1,F[i][j]=a\times F[i][j-1]+b (j\ne1)F[i][1]=c\times F[i-1][m]+d (i\ne1)$ ，求 $F[n][m]$ 。

$1\leqslant n,m\leqslant 10^{1000000}$

Solution：

$$ \begin{align} f[n][m]&=a^{m-1}\times f[n][1]+\frac{a^{m-1}-1}{a-1}\times b\\ &=a^{m-1}\times c\times f[n-1][m]+d\times a^{m-1}+\frac{a^{m-1}-1}{a-1}\times b \end{align} $$

设 $x=a^{m-1}\times c,y=d\times a^{m-1}+\frac{a^{m-1}-1}{a-1}\times b$ 。 $$ \begin{align} f[n][m]&=x\times f[n-1][m]+y\\ &=x^{n-1}\times f[1][m]+\frac{x^{n-1}-1}{x-1}\times y\\ &=x^{n-1}\times (a^{m-1}\times f[1][1]+\frac{a^{m-1}-1}{a-1}\times b)+\frac{x^{n-1}-1}{x-1}\times y \end{align} $$ 注意 $a$ 或 $c=1$ 时的特判。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

pair<ll,ll> n,m;

int a,b,c,d;

#define MOD 1000000007

#define fi first

#define se second

inline pair<ll,ll> read()

{

	register pair<ll,ll> res;

	res.fi = res.se = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res.fi = ((res.fi << 1) + (res.fi << 3) + c - '0') % MOD;

		res.se = ((res.se << 1) + (res.se << 3) + c - '0') % (MOD - 1);

		c = getchar();

	}

	return res;

}

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % MOD;

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int main()

{

	n = read();m = read();

	cin >> a >> b >> c >> d;

	int f11 = 1;

	int f1m;

	if(a == 1)f1m = (1ll * power(a,int(m.se) - 1) * f11 % MOD + 1ll * (m.fi - 1 + MOD) * b % MOD) % MOD;

	else f1m = (1ll * power(a,int(m.se) - 1) * f11 % MOD + 1ll * (power(a,int(m.se) - 1) - 1 + MOD) * power(a - 1,MOD - 2) % MOD * b) % MOD;

	int x = 1ll * power(a,int(m.se) - 1) * c % MOD;

	int y;

	if(a == 1)y = (1ll * d * power(a,int(m.se) - 1) % MOD + 1ll * (m.fi - 1 + MOD) * b % MOD) % MOD;

	else y = (1ll * d * power(a,int(m.se) - 1) % MOD + 1ll * (power(a,int(m.se) - 1) - 1 + MOD) * power(a - 1,MOD - 2) % MOD * b) % MOD;

	int fnm;

	if(a == 1 && c == 1)fnm = (1ll * power(x,int(n.se) - 1) * f1m % MOD + 1ll * (n.fi - 1 + MOD) * y % MOD) % MOD;

	else fnm = (1ll * power(x,int(n.se) - 1) * f1m % MOD + 1ll * (power(x,int(n.se) - 1) - 1 + MOD) * power(x - 1,MOD - 2) % MOD * y) % MOD;

	cout << fnm << endl;

	return 0;

}