//g++ command
g++ filename.cpp -o exe && ./exe < input.txt > output.txt
// regular code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

const int inf = 2e9;
const ll infll = 1e18;
const int M = 1000000007;
const int N = 1e5;
//Fenwick Tree
ll bit[N+1];
void add(int i, int val){
    for(; i <= n; i += i&-i) bit[i] += val;
}
ll get(int i){
    ll ret = 0;
    for(; i; i -= i&-i) ret += bit[i];
    return ret;
}
// LCA
for (int k = 1; k < 20; ++k){
    for (int i = 0; i < n; ++i){
        if((1<<k)>depth[i])continue;
        dp[i][k]=dp[dp[i][k-1]][k-1];
        sparse[i][k]=max(sparse[dp[i][k-1]][k-1],sparse[i][k-1]);
    }
}
int LCA(int u,int v){
    if(depth[u] < depth[v])swap(u,v);
    for (int k = 19; k >= 0; --k){
        if(dp[u][k] != -1 && depth[u]-(1<<k) >= depth[v]){
            u=dp[u][k];
        }
    }
    if(u == v)return u;
    for (int k = 19; k >= 0; --k){
        if(dp[u][k] != dp[v][k]){
            u=dp[u][k];
            v=dp[v][k];
        }
    }
    return dp[u][0];
}
//Matrices
//matrices
struct mat{
	
	// check for integer limits before starting
	vector<vector<int>> cell;
	int sz;


	//constructor, also gives zero matrix 
	mat(int x){
		sz = x;
		cell.resize(sz , vector<int>(sz , 0));
	}


	//identity matrix
	void I(){
		for (int i = 0; i < sz; ++i){
			cell[i][i] = 1;
		}
	}


	// check if we want to take mod after multiplication 
	mat operator *(const mat& x){
		mat ret = mat(sz);
		for (int i = 0; i < sz; ++i){
			for (int j = 0; j < sz; ++j){
				for (int k = 0; k < sz; ++k){
					ret.cell[i][j] += cell[i][k] * x.cell[k][j];
				}
			}
		}
		return ret;
	}


	// check limits for "b" it might be long long sometimes
	mat operator^(int b){
		mat ret = mat(this->sz) , x = *this;
		ret.I();
		while(b){
			if(b&1) ret = ret * x;
			b >>= 1;
			x = x * x;
		}
		return ret;
	}


	void print(){
		for (int i = 0; i < sz; ++i){
			for (int j = 0; j < sz; ++j){
				printf("%d ", cell[i][j]);
			}
			puts("");
		}
	}
};
int main(){
	mat A = mat(5);
	for (int i = 0; i < 5; ++i){
		A.cell[0][i] = 1;
	}
	for (int i = 1; i < 5; ++i){
		A.cell[i][i-1] = 1;
	}
	A = A^4;
	//A = A^(4);
	A.print();

}
//trie
struct node{
	int nxt[2] , fr;
	node(){
		memset(nxt , -1 , sizeof nxt);
		fr = 0;
	}
};

vector<node> trie(1 , node());

void add(int x){
	int cur = 0;
	for (int i = 30; i >= 0; --i){
		int d = (x >> i & 1);
		if(trie[cur].nxt[d] == -1){
			trie[cur].nxt[d] = trie.size();
			trie.pb(node());
		}
		cur = trie[cur].nxt[d];
		trie[cur].fr++;
	}
}

void remove(int x){
	int cur = 0;
	for (int i = 30; i >= 0; --i){
		int d = (x >> i & 1);
		cur = trie[cur].nxt[d];
		trie[cur].fr--;
	}
}
//kmp
string s;
cin >> s;
vector<int> f(s.size());
//failure array only, I will write the string matching myself
for(int i = 1, len = 0; i < s.size(); ++i){
    while(len && s[i] != s[len]) len = f[len-1];
    if(s[i] == s[len]) ++len;
    f[i] = len;
}