Alternating Sum
Problem - 963A - Codeforces
处理式子
显然中间式子是等比数列
// Problem: A. Alternating Sum
// Contest: Codeforces - Tinkoff Internship Warmup Round 2018 and Codeforces Round 475 (Div. 1)
// URL: https://codeforces.com/problemset/problem/963/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
using namespace std;
typedef long long ll;
const int mod=1e9+9;
ll qmi(ll a,ll b){ll res=1;while(b){if(b&1){res=res*a%mod;}b>>=1;a=a*a%mod;}return res;
}
ll inv(ll x){return qmi(x,mod-2)%mod;}
ll sn(ll a1,ll q,ll num){ll res=a1;res*=(1-qmi(q,num));res%=mod;res*=inv(1-q);res%=mod;return res;
}
int main(){ll n,a,b,k;cin>>n>>a>>b>>k;string s;cin>>s;ll t1=qmi(a,n);t1%=mod;a=inv(a)%mod;ll q=qmi(a,k)%mod*qmi(b,k)%mod;ll t2=0;if(q==1){t2=(n+1)/k;}else{t2=sn(1,q,(n+1)/k); }t2%=mod;ll t3=0;for(int i=0;i<k;i++){if(s[i]=='+'){t3+=qmi(b,i)%mod*qmi(a,i)%mod;}else{t3-=qmi(b,i)%mod*qmi(a,i)%mod;}if(t3<0){t3+=mod;}t3%=mod;}t3%=mod;ll ans=t1;ans*=t2;ans%=mod;ans*=t3;ans%=mod;cout<<(ans+mod)%mod<<'\n';return 0;
}