Problem: You are given a string s consisting of characters "1", "0", and "?". The first character of s is guaranteed to be "1". Let m be the number of characters in s.

Count the number of ways we can choose a pair of integers a, b that satisfies the following: 

  * 1 ≤ a < b < 2^m 
  * When written without leading zeros, the base-2 representations of a and b are both palindromes. 
  * The base-2 representation of bitwise XOR of a and b matches the pattern s. We say that t matches s if the lengths of t and s are the same and for every i, the i-th character of t is equal to the i-th character of s, or the i-th character of s is "?". 



Compute this count modulo 998244353. 

Input

The first line contains a single string s (1 ≤ |s| ≤ 1 000). s consists only of characters "1", "0" and "?". It is guaranteed that the first character of s is a "1".

Output

Print a single integer, the count of pairs that satisfy the conditions modulo 998244353.

Examples

Input


10110


Output


3


Input


1?0???10


Output


44


Input


1?????????????????????????????????????


Output


519569202


Input


1


Output


0

Note

For the first example, the pairs in base-2 are (111, 10001), (11, 10101), (1001, 11111).

Solution (in JAVA):

Solution:
//package com.company;
// Always comment out package when submitting.


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

public class Main {
    public static class Task {
        int mod = 998244353;
        public boolean dfsAndColor(int u, int[] color, boolean[] visit, int c, List<int[]>[] edges) {
            if (color[u] != -1 && color[u] != c) {
                return false;
            }
            color[u] = c;
            visit[u] = true;
            for (int[] edge: edges[u]) {
                int v = edge[0];
                int cc = c ^ edge[1];
                if (color[v] != -1 && color[v] != cc) return false;
                if (!visit[v]) {
                    if (!dfsAndColor(v, color, visit, cc, edges)) return false;
                }
            }
            return true;
        }
        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            char[] str = sc.next().toCharArray();
            int n = str.length;
            int tot = 0;
            for (int i = 0; i < n; i++) {
                int[] colors = new int[2 * n];
                Arrays.fill(colors, -1);
                colors[0] = 1;
                for (int j = n; j < n + i; j++) {
                    colors[j] = 0;
                }
                colors[n + i] = 1;
                List<int[]>[] edges = new List[n * 2];
                for (int j = 0; j < edges.length; j++) {
                    edges[j] = new ArrayList<>();
                }
                for (int j = 0; j < n; j++) {
                    edges[j].add(new int[]{n - 1 - j, 0});
                }
                for (int j = n + i; j < 2 * n; j++) {
                    int ot = 2 * n - 1 - (j - n - i);
                    edges[j].add(new int[]{ot, 0});
                }
                for (int j = 0; j < n; j++) {
                    if (str[j] == '1') {
                        edges[j].add(new int[]{n + j, 1});
                        edges[n + j].add(new int[]{j, 1});
                    } else if (str[j] == '0') {
                        edges[j].add(new int[]{n + j, 0});
                        edges[n + j].add(new int[]{j, 0});
                    }
                }
                boolean[] visit = new boolean[n * 2];
                int sum = 1;
                boolean bad = false;
                for (int j = n; j <= n + i; j++) {
                    if (!visit[j]) {
                        if (!dfsAndColor(j, colors, visit, colors[j], edges)) {
                            bad = true;
                        }
                    }
                }
                if (!visit[0]) {
                    if (!dfsAndColor(0, colors, visit, colors[0], edges)) {
                        bad = true;
                    }
                }
                for (int j = 0; j < 2 * n; j++) {
                    if (!visit[j]) {
                        if (!dfsAndColor(j, colors, visit, 0, edges)) {
                            bad = true;
                        }
                        sum = sum * 2 % mod;
                    }
                }
                if (bad) continue;
                tot = (tot + sum) % mod;
            }
            pw.println(tot);
        }
    }

    // template, actual code is in class Task.
    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("Test.in"));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.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) + ".");
    }

    // Faster IO with BufferedReader wrapped with Scanner
    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();
        }
    }
}