1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
using namespace std;
typedef long long ll;
ll mod;
struct
{
ll a[2][2];
void init()
{
a[0][0] = 0;
a[1][0] = 0;
a[1][1] = 0;
a[0][1] = 0;
}
inline ll* operator [] (int i)
{
return a[i];
}
};
inline matrix mult(matrix a, matrix b)
{
matrix ans;
ans.init();
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
ans[i][j] = (ans[i][j] + a[i][k] * b[k][j] % mod) % mod;
return ans;
}
char s[1000005];
inline matrix Pow_q(matrix a, ll b)
{
matrix ans;
ans.init();
ans[0][0] = 1;
ans[1][1] = 1;
while (b)
{
if (b & 1)
ans = mult(ans, a);
a = mult(a, a);
b >>= 1;
}
return ans;
}
matrix base[15];
int main()
{
ll x0, x1, a, b;
scanf("%lld%lld%lld%lld", &x0, &x1, &a, &b);
ll n;
scanf("%s%lld", s, &mod);
int len = strlen(s);
if (len == 1 && s[0] == '0')
{
printf("%lldn", x0);
return 0;
}
if (len == 1 && s[0] == '1')
{
printf("%lldn", x1);
return 0;
}
s[len - 1]--;
int i;
for (i = len - 1; i >= 0; i--)
if (s[i] < '0')
s[i] = '9', s[i - 1]--;
else
break;
if (s[0] == '0')
{
for (int i = 0; i < len - 1; i++)
s[i] = s[i + 1];
s[len - 1] = 0;
}
matrix lcy;
lcy[0][0] = a;
lcy[0][1] = b;
lcy[1][0] = 1ll;
lcy[1][1] = 0;
len = strlen(s);
matrix ans;
ans.init();
ans[0][0] = 1;
ans[1][1] = 1;
base[0].init();
base[0][0][0] = 1;
base[0][1][1] = 1;
for (int i = 1; i <= 9; i++)
base[i] = mult(base[i - 1], lcy);
for (int i = 0; i < len; i++)
{
ans = Pow_q(ans, 10);
if (s[i] != '0')
{
ans = mult(ans, base[s[i] - '0']);
}
}
ll ret = x1 * ans[0][0] % mod + x0 * ans[0][1] % mod;
ret %= mod;
printf("%lldn", ret);
return 0;
}
|
近期评论