input:seq.in output:seq.out

Time Limits: 1500 ms Memory Limits: 524288 KB

Description

Input

一行两个整数n和k。

之后1行k个正整数b1…bk。

之后1行k个正整数f1…fk。

Output

输出一个整数表示fn

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
【样例输入1】

5 4

1 2 3 4

4 3 2 1

【样例输入2】

100000 4

1 2 3 4

12 23 34 45

Sample Output

1
2
3
4
5
6
7
8
【样例输出1】

27648

样例输出2】

33508797

Data Constraint

对于30%的数据，n≤10000.

对于另外20%的数据，bi=1,n≤1000000.

对于另外20%的数据，f[1]…f[k-1]=1.

对于另外20%的数据，k≤30.

对于100%的数据，1≤k≤200,1≤n≤40000000,1≤bi,fi≤998244352.

Hint

样例解释：122333444*4=27648

Code

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
#include <bits/stdc++.h>
#define mod 998244353
#define ll long long
ll n, k;
ll b[205], f[1000005];
ll A[205][205];
ll B[205][205];
ll C[205][205];

void cf () {
    memset (C, 0, sizeof (C));
    for (ll i = 1;i <= k;i++) {
        for (ll j = 1;j <= k;j++) {
            for (ll l = 1;l <= k;l++) {
                C[i][j] += A[l][j] * B[i][l];
                C[i][j] %= (mod - 1);
            }
        }
    }
    for (ll i = 1;i <= k;i++) {
        for (ll j = 1;j <= k;j++) {
            B[i][j] = C[i][j];
        }
    }
    return;
}
void pf () {
    memset (C, 0, sizeof (C));
    for (ll i = 1;i <= k;i++) {
        for (ll j = 1;j <= k;j++) {
            for (ll l = 1;l <= k;l++) {
                C[i][j] += A[l][j] * A[i][l];
                C[i][j] %= (mod - 1);
            }
        }
    }
    for (ll i = 1;i <= k;i++) {
        for (ll j = 1;j <= k;j++) {
            A[i][j] = C[i][j];
        }
    }
    return;
}
void ksm (ll y) {
    while (y) {
        if (y % 2 != 0) {
            cf ();
        }
        pf ();
        y >>= 1;
    }
    return;
}
ll ksm2 (ll x, ll y) {
    ll sum = 1;
    while (y) {
        if (y % 2 > 0) {
            sum *= x;
            sum %= mod;
        }
        x *= x;
        x %= mod;
        y >>= 1;
    }
    return sum;
}
int main () {
    freopen ("seq.in", "r", stdin);
    freopen ("seq.out", "w", stdout);
    scanf ("%lld %lld", &n, &k);
    for (ll i = 1;i <= k;i++) {
        scanf ("%lld", &b[i]);
    }
    for (ll i = 1;i <= k;i++) {
        scanf ("%lld", &f[i]);
    }
    if (n * k <= 100000000) {
        for (ll i = k + 1;i <= n;i++) {
            f[i] = 1;
            for (ll j = 1;j <= k;j++) {
                f[i] *= ksm2 (f[i - j], b[j]);
                f[i] %= mod;
            }
        }
        printf ("%lld", f[n]);
        return 0;
    }
    memset (A, 0, sizeof (A));
    for (ll i = 1;i <= k;i++) {
        A[1][i] = b[i];
        B[1][i] = b[i];
    }
    for (ll i = 2;i <= k;i++) {
        A[i][i - 1] = 1;
        B[i][i - 1] = 1;
    }
    ksm (n - k - 1);
    ll ans = 1;
    for (ll i = 1;i <= k;i++) {
        ans *= ksm2 (f[k - i + 1], B[1][i]);
        ans %= mod;
    }
    printf ("%lld", ans);
    return 0;
}