//I_love_coding...
//I_will_win
//I_can_win
//I_must_win
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

long long int me(long long int x,long long int n,long long int M)
{//(__int128) when needed....
 long long int result=1;
    while(n>0)
    {
        if(n%2==1)
            result=(result*x)%M;  
        x=(x*x)%M;
        n=n/2;
    }
    return result;
}


//calculates : (1/(a^b))%M;
ll modInverse(ll A,ll B,ll M)
{
    ll k=B*(M-2);
    return me(A,k,M);
}


int main()
{
	ios_base::sync_with_stdio(false) ; 
	cin.tie(NULL);
    cout.tie(NULL);	
    string s;
    cin>>s;
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    int n = s.length();
    int hash[n];
    long long p_pow = 1;
    int i=0;
    for (char c : s) 
    {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
        hash[i] = hash_value ; 
        cout<<hash[i]<<"\n";
    i++;
    }
    int i1,j1;
    //s[i1......j1]...
    i1=2;
    j1=4;
    int ans = (hash[j1]%m -hash[i1-1]%m +m)%m;
    int final = (modInverse(p,i1,m) * ans)%m ;     
    cout<<final ;     
        cout<<"\n";
        i1=6;
    j1=8;
     ans = (hash[j1]%m -hash[i1-1]%m +m)%m;
     final = (modInverse(p,i1,m) * ans)%m ;     
    cout<<final ;
        
        
	return 0;
}