#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pn putchar('\n')
#define maxint 2147483647
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define int ll
#define mod 1000000009
#define Mod 1000000008
using namespace std;
int a,b,c,k,ans,lim,len;
string s;
il int ksm(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1)ret=ret*x%mod;
        x=x*x%mod,y>>=1;
    }
    return ret;
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    scanf("%lld%lld%lld",&a,&b,&c);
    cin>>s;
    len=s.size()-1;
    s[len]++;
    k=len;
    while(k&&s[k]>'9')
        s[k-1]++,s[k]='0',k--;
    if(s[0]>'9')
        s[0]='0',s='1'+s,len++;
    k=0;
    for(int i=0,len=s.size();i<len;i++)
        k=(k*10+s[i]-'0')%Mod;
    if(!a)
        return printf("%lld\n",ksm(2,k)+1),0;
    int x=c-b*b/4/a;
    if(len<=2&&s[0]<='4'&&x>(1LL<<k))
        return puts("0"),0;
    if(b*b==4*a*(c-x))
        ans=-1;
    if(x<=0)
        return printf("%lld",(ans+(ksm(2,k)+1)*2)%mod),0;
    printf("%lld",((ans+(ksm(2,k)-x+1)*2)%mod+mod)%mod);
    return 0;
}