Let x be a string of length at least 1. We will call x a good string, if for any string y and any integer k (k \geq 2), the string obtained by concatenating k copies of y is different from x. For example, `a`, `bbc` and `cdcdc` are good strings, while `aa`, `bbbb` and `cdcdcd` are not.

Let w be a string of length at least 1. For a sequence F=(\,f_1,\,f_2,\,...,\,f_m) consisting of m elements, we will call F a good representation of w, if the following conditions are both satisfied:

* For any i \, (1 \leq i \leq m), f_i is a good string.
* The string obtained by concatenating f_1,\,f_2,\,...,\,f_m in this order, is w.



For example, when w=`aabb`, there are five good representations of w:

* (`aabb`)
* (`a`,`abb`)
* (`aab`,`b`)
* (`a`,`ab`,`b`)
* (`a`,`a`,`b`,`b`)



Among the good representations of w, the ones with the smallest number of elements are called the best representations of w. For example, there are only one best representation of w=`aabb`: (`aabb`).

You are given a string w. Find the following:

* the number of elements of a best representation of w
* the number of the best representations of w, modulo 1000000007 \, (=10^9+7)



(It is guaranteed that a good representation of w always exists.)

Constraints

* 1 \leq |w| \leq 500000 \, (=5 \times 10^5)
* w consists of lowercase letters (`a`-`z`).

Input

The input is given from Standard Input in the following format:


w


Output

Print 2 lines.

* In the first line, print the number of elements of a best representation of w.
* In the second line, print the number of the best representations of w, modulo 1000000007.

Examples

Input

aab


Output

1
1


Input

bcbc


Output

2
3


Input

ddd


Output

3
1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[32;1m" << #x << "->" ; err(x);} while(0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T,typename t,typename... A>
void err(T<t> a,A... x){for (auto v:a) cout << v << ' '; err(x...);}
template<typename T,typename... A>
void err(T a,A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
const int mod=998244353;
const int INF=0x3f3f3f3f;
ll quick(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1)
			ret=ret*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ret;
}
ll inv(ll a){return quick(a,mod-2);}
const int maxn=5e5+7;
void getfail(char *t,int *fail)
{
    int len = strlen(t);
    int j = 0, k = fail[0] = -1;
    while (j < len)
    {
        while (k != -1 && t[j] != t[k])
            k = fail[k];
        fail[++j] = ++k;
    }
}
bool isloop(int *fail,int i)
{
	return fail[i]*2>=i&&i%(i-fail[i])==0;
}
char t2[maxn];
char t[maxn];
int fail[maxn];
int f2[maxn];
int main()
{
	scanf("%s",t);
	getfail(t,fail);
	int len=strlen(t);
	if(!isloop(fail,len))
		puts("1\n1");
	else if(len-fail[len]==1)
		printf("%d\n%d\n",len,1);
	else{
		int ans=0;
		for(int i=0;i<len;i++)
			t2[i]=t[len-1-i];
		t2[len]='\0';
		getfail(t2,f2);
		for(int i=1;i<len;i++)
		{
			if(!isloop(fail,i)&&!isloop(f2,len-i))
				 ans++;
		}
		printf("%d\n%d\n",2,ans);
	}

}
