记录编号	162128	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2013]矩阵游戏	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.105 s
提交时间	2015-05-14 09:46:29	内存使用	12.69 MiB

/*****************************************************************************/
/******************************Designed By Asm.Def****************************/
/*****************************************************************************/
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <ctime>
#define SetFile(x) (freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) )
#define FREAD
#define FREADLENTH 5000000
#ifdef FREAD
char *fread_ptr = (char*)malloc(FREADLENTH);
#define getc() (*(fread_ptr++))
#else
#define getc() getchar()
#endif
using namespace std;
template<class T>inline void getd(T &x){
	int ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')neg = true, ch = getc();
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/*******************************************************************************/
const int maxn = 1000005, mod = 1000000007, PhiP = 1000000006;
#define inv(x) powmod(x, 1000000005)
typedef long long LL;

inline int powmod(int a, int n){
	int Ans = 1;
	while(n){
		if(n & 1)Ans = (LL)Ans * a % mod;
		a = (LL)a * a % mod;
		n >>= 1;
	}
	return Ans;
}

int N[maxn], M[maxn], lenN, lenM;

inline void getnum(int *N, int &len){
	char ch;while(!isdigit(ch = getc()));
	while(isdigit(ch)){
		N[len++] = ch - '0';
		ch = getc();
	}
}

inline int Mod(int *N, int len, int m){
	int i;
	LL Ans = 0;
	for(i = 0;i < len;++i){
		Ans = Ans * 10 + N[i];
		if((i & 7) == 7)Ans = Ans % m;
	}
	return (int)(Ans % m);
}

inline void work(){
	int a, b, c, d, t1, k1, b1, t2, k2, b2, n, m;
	getnum(N, lenN);getnum(M, lenM);
	getd(a), getd(b), getd(c), getd(d);
	if(a == 1)k1 = 1, b1 = ((LL)b * (Mod(M, lenM, mod) + PhiP)) % mod;
	else{
		m = Mod(M, lenM, PhiP);
		t1 = (LL)b * inv(a-1) % mod;
		k1 = powmod(a, m + PhiP - 1);
		b1 = (LL)(k1-1) * t1 % mod;
	}
	d = ((LL)c * b1 + d) % mod;
	c = (LL)c * k1 % mod;
	if(c == 1)k2 = 1, b2 = ((LL)d * (Mod(N, lenN, mod) + PhiP)) % mod;
	else{
		n = Mod(N, lenN, PhiP);
		t2 = (LL)d * inv(c-1) % mod;
		k2 = powmod(c, n + PhiP - 1);
		b2 = (LL)(k2-1) * t2 % mod;
	}
	int x = ((LL)(k2 + b2) * k1 + b1) % mod;
	printf("%d\n", x); 
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#else
	SetFile(matrixb);
#endif
#ifdef FREAD
	fread(fread_ptr, 1, FREADLENTH, stdin);
#endif
	work();

#ifdef DEBUG
	printf("\n%.3lf sec\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}