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.util.*;
import java.io.*;
/*

aaaa

 */
public class tester {
	public static void main(String[] arg) {
		Scanner in = new Scanner(System.in);
		String s = in.next();
		int n = s.length();
		char[] v = new char[n];
		for(int i = 0; i < n/2; i++) {
			v[2*i] = s.charAt(i);
			v[2*i+1] = s.charAt(s.length()-1-i);
		}
		int mod = 1_000_000_007;
		int[] dp = new int[n+1];
		int[] sdp = new int[n+2];
		dp[0] = 1;
		Eertree tree = new Eertree(n);
		for(int i = 1; i <= n; i++) {
			tree.addLetter(v[i-1]);
			for(int cur = tree.last; tree.len[cur] > 0; cur = tree.slink[cur]) {
				sdp[cur] = dp[i-(tree.len[tree.slink[cur]]+tree.diff[cur])];
				if(tree.diff[cur] == tree.diff[tree.link[cur]]) {
					sdp[cur] += sdp[tree.link[cur]];
					sdp[cur] %= mod;
				}
				if(i%2 == 0) {
					dp[i] += sdp[cur];
					dp[i] %= mod;
				}
			}
		}
		System.out.println(dp[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];
		}
	}

}