[Codeforces] 475C Alternating Sum

題目連結：http://codeforces.com/contest/964/problem/C
　　我最近DEBUG能力明顯下降，思緒不清晰......。
　　以ｋ個做為一個循環，用1+x+x^2+...甚麼的那個公式，然後亂做就好了。

#include<bits/stdc++.h>
#define int long long
#define MOD 1000000009ll
using namespace std;
int n,a,b,k;
string s;
inline int add(int aa,int bb)
{
    aa += bb; aa %= MOD;
    if(aa<0) aa += MOD;
    return aa;
}
inline int mul(int aa,int bb)
{
    aa *= bb; aa %= MOD;
    return add(aa,0);
}
inline int fast(int a,int b=MOD-2)
{
    int res = 1;
    while(b)
    {
        if(b&1) res = mul(res,a);
        b >>= 1;
        a = mul(a,a);
    }
    return res;
}
signed main()
{
    cin >> n >> a >> b >> k >> s;
    int ans = 0, neg = 0;
    for(int i = 0; i < k; i++)
    {
        neg = (s[i] == '+')?1:-1;
        ans = add(ans,neg*fast(a,n-i)*fast(b,i));
    }
    int inv_a = fast(a);
    a = mul(fast(inv_a,k),fast(b,k));
    int _ = (n+1)/k;
    if(a == 1) ans = mul(ans,_);    
    else ans = mul(ans,mul(fast(a,_)-1,fast(a-1)));
    cout << ans << endl;
}