/
963A.go
51 lines (47 loc) · 947 Bytes
/
963A.go
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
package main
import (
"bufio"
. "fmt"
"io"
)
// github.com/EndlessCheng/codeforces-go
func CF963A(_r io.Reader, _w io.Writer) {
in := bufio.NewReader(_r)
out := bufio.NewWriter(_w)
defer out.Flush()
const mod int64 = 1e9 + 9
pow := func(x int64, n int64) int64 {
res := int64(1)
for ; n > 0; n >>= 1 {
if n&1 == 1 {
res = res * x % mod
}
x = x * x % mod
}
return res
}
inv := func(a int64) int64 { return pow(a, mod-2) }
frac := func(a, b int64) int64 { return a * inv(b) % mod }
var n, a, b, k, ans int64
var s []byte
Fscan(in, &n, &a, &b, &k, &s)
q := frac(b, a)
for i := len(s) - 1; i >= 0; i-- {
ans *= q
if s[i] == '+' {
ans++
} else {
ans += mod - 1
}
ans %= mod
}
ans = ans * pow(a, n) % mod
n = (n + 1) / k
if q = pow(q, k); q == 1 {
ans = ans * n % mod
} else {
ans = ans * frac(pow(q, n)-1, q-1) % mod
}
Fprint(out, ans)
}
//func main() { CF963A(os.Stdin, os.Stdout) }