Codeforces Round #475 (Div. 2) C. Alternating Sum（等比数列+逆元）_综合

You are given two integers $a$ and $b$ . Moreover, you are given a sequence $s_{0}, s_{1}, \dots, s_{n}$ . All values in $s$ are integers $1$ or $? 1$ . It's known that sequence is $k$ -periodic and $k$ divides $n + 1$ . In other words, for each $k \leq i \leq n$ it's satisfied that $s_{i} = s_{i ? k}$ .

Find out the non-negative remainder of division of $n \sum i = 0 s_{i} a^{n ? i} b^{i}$ by $10^{9} + 9$ .

Note that the modulo is unusual!

Input

The first line contains four integers $n, a, b$ and $k$ $(1 \leq n \leq 10^{9}, 1 \leq a, b \leq 10^{9}, 1 \leq k \leq 10^{5})$ .

The second line contains a sequence of length $k$ consisting of characters '+' and '-'.

If the $i$ -th character (0-indexed) is '+', then $s_{i} = 1$ , otherwise $s_{i} = ? 1$ .

Note that only the first $k$ members of the sequence are given, the rest can be obtained using the periodicity property.

Output

Output a single integer — value of given expression modulo $10^{9} + 9$ .

   Examples
  
     input
     
      Copy
     
2 2 3 3
+-+

     output
     
      Copy
     
7

     input
     
      Copy
     
4 1 5 1
-

     output
     
      Copy
     
999999228

Note

In the first example:

$(n \sum i = 0 s_{i} a^{n ? i} b^{i})$ = $2^{2} 3^{0} ? 2^{1} 3^{1} + 2^{0} 3^{2}$ = 7

In the second example:

$(n \sum i = 0 s_{i} a^{n ? i} b^{i}) = ? 1^{4} 5^{0} ? 1^{3} 5^{1} ? 1^{2} 5^{2} ? 1^{1} 5^{3} ? 1^{0} 5^{4} = ? 781 \equiv 999999228 (mod 10^{9} + 9)$ .

$题意: 求解(n \sum i = 0 s_{i} a^{n ? i} b^{i})$ ， $s_{i} {要么是-要么是+，给出1-k的si, 对于 k\leqi\leqnk\leqi\leqn 则有si=si?ksi=si?k。}$

对于i, i+k, i + 2 *k.....可发现公比是(b/a)^k的等比数列，因为求和公式为a1(1-q^n)/（1-q）,(1-q^x)/（1-q）是一样的，所以计算出

1-k的(k∑i=0sian?ibi)在乘以(1-q^x)/（1-q）即可，项数x = (n+1)/k, 取模的时候，除法要逆元，用费马小定理即可。

#include <bits/stdc++.h>
#include <ext/hash_map>
#include <ext/hash_set>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define XINF INT_MAX
#define INF 0x3F3F3F3F
#define MP(X,Y) make_pair(X,Y)
#define PB(X) push_back(X)
#define REP(X,N) for(int X=0;X<N;X++)
#define REP2(X,L,R) for(int X=L;X<=R;X++)
#define DEP(X,R,L) for(int X=R;X>=L;X--)
#define CLR(A,X) memset(A,X,sizeof(A))
#define IT iterator
#define RIT reverse_iterator
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<PII> VII;
typedef vector<int> VI;
typedef tree<PII, null_type, greater<PII>, rb_tree_tag, tree_order_statistics_node_update > rb_tree_set;
typedef tree<PII, PII, greater<PII>, rb_tree_tag, tree_order_statistics_node_update > rb_tree;
#define PQ std::priority_queue
#define HEAP __gnu_pbds::priority_queue
#define X first
#define Y second
#define lson(X) ((X)<<1)
#define rson(X) ((X)<<1|1)
#define N 110
#define M 200010
const ll  mod = 1e9 + 9;
ll q_pow(ll a, ll b)
{ll ans = 1;while(b) {if(b & 1)ans = ans * a % mod;a = a * a %mod;b >>= 1;}return ans;
}
int main()
{ll sum = 0, ans  = 0;ll a, b, k, n;scanf("%lld%lld%lld%lld", &n, &a, &b, &k);getchar();char ch;ll head = q_pow(a, n);ll ni_a = q_pow(a, mod-2);REP(i, k) {scanf("%c", &ch);if(ch == '+')ans = (ans + head) % mod;elseans = (ans - head + mod) % mod;head = head * ni_a % mod * b % mod;}ll x = (n+1) / k;//ll q = q_pow(q_pow(a, k), mod-2) * q_pow(b, k) % mod;ll q = q_pow(b*ni_a%mod, k);if(q == 1) {printf("%lld\n", ans * x % mod);}else {sum = (1 - q_pow(q, x) + mod) % mod;    //负数取模.sum = sum * q_pow((1-q+mod)%mod, mod-2) % mod;printf("%lld\n", ans * sum % mod);}return 0;
}