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;
		}

		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]) {
				//Keep this line the same
				dpS[j] = res[i-(et.len[et.slink[j]] + et.diff[j])];
				
				if(et.diff[j] == et.diff[et.link[j]]) {
					dpS[j] += dpS[et.link[j]]; // <- Function of curRes = eval(curRes, dpS[et.link[j]])
					if(dpS[j] >= mod) dpS[j] -= mod;
				}
				if((i&1) == 0) {
					res[i] += dpS[j]; // <- Same function above. curRes = eval(curRes, dpS[j]);
					if(res[i] >= mod) res[i] -= mod;
				}
			}
		}
		System.out.println(res[N]);
	}
	
	
	static class Eertree {
		int[] s, len, link, slink, diff;
		int[][] to;
		int sz, last, n;
		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] = 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];
		}
	}
	
	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();
		}
	}
}