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:
//package com.company;

import java.io.*;
import java.util.*;

public class Main {
    public static class Task {

//        public class SegmentTree { // minimum
//            int n;
//            int[] values;
//            int MM = Integer.MAX_VALUE / 2;
//            public SegmentTree(int n) {
//                this.n = n;
//                values = new int[n * 4];
//            }
//            public void set(int l, int r, int idx, int I, int v) {
//                if (l == I && r == I + 1) {
//                    values[idx] = v;
//                    return;
//                }
//                int mid = (l + r) / 2;
//                if (I < mid) set(l, mid, idx << 1, I, v);
//                else set(mid, r, idx << 1 | 1, I, v);
//                values[idx] = Math.min(values[idx << 1], values[idx << 1 | 1]);
//            }
//            public int min(int l, int r, int idx, int L, int R) {
//                if (L <= l && r <= R) {
//                    return values[idx];
//                }
//                if (l >= R || r <= L) return MM;
//                int mid = (l + r) / 2;
//                return Math.min(min(l, mid, idx << 1, L, R), min(mid, r, idx << 1 | 1, L, R));
//            }
//            void set(int I, int v) {
//                set(0, n, 1, I, v);
//            }
//            int min(int L, int R) {
//                return min(0, n, 1, L, R);
//            }
//        }

        public class EerTree {
            int n, cur; // length of current string, index of current suffix-palindrome
            int N; // good if we know the final size.
            int[] len;
            int[] suflink;
            int[] diff;
            int[] slink;
            int[][] next;
            int[] string;
            int[] quicklink;
            public EerTree(int[] string) {
                this.string = string;
                this.N = string.length;
                len = new int[N + 2];
                suflink = new int[N + 2];
                diff = new int[N + 2];
                slink = new int[N + 2];
                quicklink = new int[N + 2];
                next = new int[N + 2][26];
                for (int i = 0; i < N + 2; i++) {
                    Arrays.fill(next[i], -1);
                }
                len[0] = -1;
                cur = 0;
                n = 2;
            }

            int getPrevMatch(int cur, int index) {
                if (index - len[cur] - 1 < 0) {
                    cur = suflink[cur];
                }
                while (true) {
                    if (string[index - len[cur] - 1] == string[index]) return cur;
                    if (string[index - len[suflink[cur]] - 1] == string[index]) return suflink[cur];
                    cur = quicklink[cur];
                }
            }

            void add(int index) {
                cur = getPrevMatch(cur, index);

                if (next[cur][string[index]] != -1) {
                    cur = next[cur][string[index]];
                } else {
                    next[cur][string[index]] = n;
                    len[n] = len[cur] + 2;
                    if (len[n] == 1) {
                        suflink[n] = diff[n] = slink[n] = quicklink[n] = 1;
                    } else {
                        suflink[n] = next[getPrevMatch(suflink[cur], index)][string[index]];
                        diff[n] = len[n] - len[suflink[n]];
                        if (diff[n] == diff[suflink[n]]) {
                            slink[n] = slink[suflink[n]];
                        } else {
                            slink[n] = suflink[n];
                        }
                        if (string[index - len[suflink[n]]] == string[index - len[suflink[suflink[n]]]]) {
                            quicklink[n] = quicklink[suflink[n]];
                        } else {
                            quicklink[n] = suflink[suflink[n]];
                        }
                    }
                    cur = n++;
                }
            }
        }
        int mod = 1_000_000_007;
        int add(int a, int b) {
            int c = a + b;
            if (c >= mod) return c - mod;
            if (c < 0) return c + mod;
            return c;
        }

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            String s = sc.next();
            int[] string = new int[s.length()];
            for (int i = 0; i < s.length() / 2; i++) {
                string[i * 2] = s.charAt(i) - 'a';
                string[i * 2 + 1] = s.charAt(s.length() - i - 1) - 'a';
            }
            EerTree eerTree = new EerTree(string);
            int[] ans = new int[string.length + 1];
            ans[0] = 1;
            int[] dp = new int[string.length + 2];
            for (int i = 1; i <= string.length; i++) {
                eerTree.add(i - 1);
                for (int j = eerTree.cur; j > 1; j = eerTree.slink[j]) {
                    dp[j] = ans[i - eerTree.len[eerTree.slink[j]] - eerTree.diff[j]];
                    if (eerTree.diff[j] == eerTree.diff[eerTree.suflink[j]]) {
                        dp[j] = add(dp[j], dp[eerTree.suflink[j]]);
                    }
                    ans[i] = add(ans[i], dp[j]);
                }
                if (i % 2 != 0) ans[i] = 0;
            }
            pw.println(ans[s.length()]);
        }
    }
    static long TIME_START, TIME_END;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("joker.in"));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("joker.out"));

        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
        System.err.println("Memory increased: " + (usedMemoryAfter - usedMemoryBefore) / 1000000);
        System.err.println("Time used: " + (TIME_END - TIME_START) + ".");
    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;
        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }
        public Scanner(FileReader s) throws FileNotFoundException {
            br = new BufferedReader(s);
        }
        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
        public String nextLine() throws IOException {
            return br.readLine();
        }
        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
        public boolean ready() throws IOException {
            return br.ready();
        }
    }
}