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

public class Solution {

    static ArrayList<ArrayList<Pair>> adjLst;
    static int m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        m = s.length();
        long numWays = 0;
        for (int i = 1; i <= m - 1; i++) { // For every possible length of A
            adjLst = new ArrayList<>();
            for (int k = 0; k < m + 2; k++) { // Graph containing m + 2 nodes
                adjLst.add(new ArrayList<Pair>());
            }
            adjLst.get(0).add(new Pair(1, 1));
            adjLst.get(1).add(new Pair(0, 1));
            int q;
            for (q = 2; q <= (m + 2) / 2; q++) { // Construct edges between B bits
                adjLst.get(q).add(new Pair(m - q + 3, 0));
                adjLst.get(m - q + 3).add(new Pair(q, 0));
            }
            for (int j = 0; j < i; j++) {
                adjLst.add(new ArrayList<>());
            }
            for (q = 0; q < i / 2; q++) { // Construct edges between A bits
                adjLst.get(2 + m + q).add(new Pair(1 + m + i - q, 0));
                adjLst.get(1 + m + i - q).add(new Pair(2 + m + q, 0));
            }

            for (int j = 0; j < m; j++) {
                if (j == m - i) {
                    adjLst.get(i + j + 2).add(new Pair(1, 0)); // Changes made here
                    adjLst.get(1).add(new Pair(i + j + 2, 0));
                }
                if (s.charAt(j) == '1') {
                    if (m - j > i) {
                        adjLst.get(j + 2).add(new Pair(1, 0)); // Changes made here
                        adjLst.get(1).add(new Pair(j + 2, 0)); // From 1-edge to 0-edge
                    } else {
                        adjLst.get(j + 2).add(new Pair(j + i + 2, 1));
                        adjLst.get(j + i + 2).add(new Pair(j + 2, 1));
                    }
                } else if (s.charAt(j) == '0') {
                    if (m - j > i) {
                        adjLst.get(j + 2).add(new Pair(0, 0));
                        adjLst.get(0).add(new Pair(j + 2, 0));
                    } else {    
                        adjLst.get(j + 2).add(new Pair(i + j + 2, 0));
                        adjLst.get(i + j + 2).add(new Pair(j + 2, 0));
                    }
                } else { // if '?'

                }
            }

            // for (int k = 0; k < adjLst.size(); k++) { // Debugging
            //     System.out.println("Node: " + k);
            //     for (Pair p : adjLst.get(k)) {
            //         System.out.print(p.node + ", " + p.type + " ");
            //     }
            //     System.out.println();
            // }

            if (isBipartite(adjLst)) {
                numWays += myPowerMod998244353(2, getNumComponents(adjLst) - 1);
                // System.out.println("i: " + i + " numWays: " + numWays); // Debugging
            } else {
                continue;
            }
        }
        System.out.println(numWays % 998244353);
    }

    public static long myPowerMod998244353(long a, long b) {
        long res = 1;
        for (int i = 0; i < b; i++) {
            res = (res * a) % 998244353;
        }
        return res;
    }

    public static boolean isBipartite(ArrayList<ArrayList<Pair>> adjLst) {
        int[] colorArr = new int[adjLst.size()]; // 0 for unvisited, 1 and -1 for the colors
        for (int i = 0; i < adjLst.size(); i++) {
            if (colorArr[i] == 0) {
                boolean temp = isBipartite(adjLst, colorArr, i);
                if (!temp) return false;
            }
        }
        return true;
    }

    public static boolean isBipartite(ArrayList<ArrayList<Pair>> adjLst,
        int[] colorArr, int i) {
        colorArr[i] = 1;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i);
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (Pair p : adjLst.get(curr)) {
                if (p.type == 1) {
                    if (colorArr[p.node] == 0) {
                        colorArr[p.node] = -1*colorArr[curr];
                        queue.add(p.node);
                    } else {
                        if (colorArr[p.node] == colorArr[curr]) return false;
                    } 
                } else { // if p.type == 0
                    if (colorArr[p.node] == 0) {
                        colorArr[p.node] = colorArr[curr];
                        queue.add(p.node);
                    } else {
                        if (colorArr[p.node] != colorArr[curr]) return false;
                    } 
                }
            }
        }
        return true;
    }

    public static long getNumComponents(ArrayList<ArrayList<Pair>> adjLst) {
        boolean[] visited = new boolean[adjLst.size()];
        long numComponents = 0;
        for (int i = 0; i < adjLst.size(); i++) {
            if (!visited[i]) {
                numComponents++;
                dfs(adjLst, visited, i);
            }
        }
        return numComponents;
    }

    public static void dfs(ArrayList<ArrayList<Pair>> adjLst,
        boolean[] visited, int i) {
        visited[i] = true;
        for (Pair p : adjLst.get(i)) {
            if (!visited[p.node]) dfs(adjLst, visited, p.node);
        }
    }

}

class Pair {

    int node;
    int type;

    public Pair(int node, int type) {
        this.node = node;
        this.type = type;
    }

}