Problem: Given a string s, find the number of ways to split s to substrings such that if there are k substrings (p1, p2, p3, ..., pk) in partition, then pi = pk - i + 1 for all i (1 ≤ i ≤ k) and k is even.

Since the number of ways can be large, print it modulo 109 + 7.

Input

The only line of input contains a string s (2 ≤ |s| ≤ 106) of even length consisting of lowercase Latin letters. 

Output

Print one integer, the number of ways of partitioning the string modulo 109 + 7.

Examples

Input

abcdcdab


Output

1

Input

abbababababbab


Output

3

Note

In the first case, the only way to partition the string is ab|cd|cd|ab.

In the second case, the string can be partitioned as ab|b|ab|ab|ab|ab|b|ab or ab|b|abab|abab|b|ab or abbab|ab|ab|abbab.

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class PalindromePartition {

	static int N;
	static char c[];
	static long dpS[];
	static long res[];
	static long mod = 1_000_000_007;
	public static void main(String[] args) {
		FS in = new FS();
		char s[] = in.next().toCharArray();
		N = s.length;
		c = new char[N];
		int idd = 0;
		for(int i = 0; i < N/2; i++) {
			c[idd] = s[i];
			idd += 2;
		}
		idd = 1;
		for(int i = N-1; i >= N/2; i--) {
			c[idd] = s[i];
			idd += 2;
		}

// Series link DP optimization:
res = new long[N+1]; //Actual DP
// res[i] is answer if at index (i-1) in the string (res[0] is base case)
dpS = new long[N+2]; //DP for the eetree
//Initialize the eertree and fill dpS with -1.
//Fill res[baseCase] with the answer for base case
Eertree et = new Eertree(N);
Arrays.fill(dpS, -1);
res[0] = 1;
for(int i = 1; i <= N; i++) { //Loop over the palindromes ending at index (i-1)
	//Add the character to the eertree and now et.last is the
	// node of the longest suffix ending at index (i-1)
	et.addLetter(c[i-1]);
	//get res[i] by looping through the suffix links
	for(int j = et.last; et.len[j] > 0; j = et.slink[j]) {
		dpS[j] = 0; // Starting value
		dpS[j] = update(dpS[j], res[i-(et.len[et.slink[j]] + et.diff[j])]);
		if(et.diff[j] == et.diff[et.link[j]]) { // Non trivial series
			dpS[j] = update(dpS[j], dpS[et.link[j]]);
		}
		// In sample problem we only want palindromes ending at even indeces
		if((i&1) == 0) {
			res[i] = update(res[i], dpS[j]);
		}
	}
}
		System.out.println(res[N]);
	}
	
	static long update(long a, long b){ return (a+b)%mod;}
	
	
//Nodes 0 and 1 are dummy nodes. Not actual palindromes in the string
//link[i] is suffix link, slink[i] is series link
static class Eertree {
	int[] s, len, link, slink, diff;
	int[][] to;
	int sz, last, n;
	long pCnt;
	public Eertree(int nn) {
		s = new int[nn+2];
		len = new int[nn+2];
		link = new int[nn+2];
		to = new int[26][nn+2];
		slink = new int[nn+2];
		diff = new int[nn+2];
		s[n++] = -1;
		link[0] = link[1] = 1;
		len[1] = -1;
		sz = 2;
	}
	int getLink(int v) {
		while(s[n-len[v]-2] != s[n-1]) v = link[v];
		return v;
	}
	void addLetter(char ch) {
		int c = ch-'a';
		s[n++] = c;
		last = getLink(last);
		if(to[c][last] == 0) {
			len[sz] = len[last]+2;
			link[sz] = to[c][getLink(link[last])];
			diff[sz] = len[sz]-len[link[sz]];
			if(diff[sz] == diff[link[sz]]) slink[sz] = slink[link[sz]];
			else slink[sz] = link[sz];
			to[c][last] = sz++;
		}
		last = to[c][last];
	}
/*
// Series link DP optimization:
res = new long[N+1]; //Actual DP
// res[i] is answer if at index (i-1) in the string (res[0] is base case)
dpS = new long[N+2]; //DP for the eetree
//Initialize the eertree and fill dpS with -1.
//Fill res[baseCase] with the answer for base case
Eertree et = new Eertree(N);
Arrays.fill(dpS, -1);
res[0] = 1;
for(int i = 1; i <= N; i++) { //Loop over the palindromes ending at index (i-1)
	//Add the character to the eertree and now et.last is the node of the longest suffix ending at index (i-1)
	et.addLetter(c[i-1]);
	//get res[i] by looping through the suffix links
	for(int j = et.last; et.len[j] > 0; j = et.slink[j]) {
		dpS[j] = 0; // Starting value
		// Update nodes DP
		dpS[j] = update(dpS[j], res[i-(et.len[et.slink[j]] + et.diff[j])];)
		
		if(et.diff[j] == et.diff[et.link[j]]) { // Non trivial series
			dpS[j] = update(dpS[j], dpS[et.link[j]];)
		}
		// In sample problem we only want palindromes ending at even indeces (1-based)
		if((i&1) == 0) {
			res[i] = update(res[i], dpS[j]);
		}
	}
}
// update(a, b): returns new value if a is current dp value and b is 
long update(long a, long b){ return (a+b)%mod;}
*/
}


	
	static class FS{
		BufferedReader br;
		StringTokenizer st;
		public FS() { br = new BufferedReader(new InputStreamReader(System.in));}
		public String next() {
			while(st == null || !st.hasMoreElements()) {
				try { st = new StringTokenizer(br.readLine());}
				catch(Exception e) { throw null;}
			}
			return st.nextToken();
		}
	}
}