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

public class Solution {
	
	public static long two[] = new long[1000];
	public static final long MOD = 998244353;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		String str = in.next();
		int n = str.length();
		long res = 0;
		init();
		for(int k = 1; k < n; k++) {
			Node a[] = new Node[(n + 1) / 2], b[] = new Node[(k + 1) / 2];
			for(int i = 0; i < a.length; i++)
				a[i] = new Node();
			for(int i = 0; i < b.length; i++)
				b[i] = new Node();
			Node p[] = new Node[2];
			p[0] = new Node();
			p[1] = new Node();
			addEdge(p[0], p[1], 1);
			addEdge(p[1], b[0], 0);
			for(int i = -1; i >= -k; i--) {
				char ch = str.charAt(n + i);
				if(ch != '?')
					addEdge(a[index(n + i, n)], b[index(k + i, k)], ch - '0');
			}
			for(int i = 0; i < n - k; i++) {
				char ch = str.charAt(i);
				if(ch != '?')
					addEdge(a[index(i, n)], p[ch - '0'], 0);
			}
			List<Node> l = new ArrayList<Node>();
			l.addAll(Arrays.asList(a));
			l.addAll(Arrays.asList(b));
			l.addAll(Arrays.asList(p));
			int comp = 0;
			while(comp > -1 && !l.isEmpty()) {
				if(collapse(l, l.get(0)))
					comp++;
				else
					comp = -1;
			}
			if(comp != -1)
				res = (res + two[comp - 1]) % MOD;
		}
		System.out.println(res);
		in.close();

	}
	
	private static void init() {
		two[0] = 1;
		for(int i = 1; i < two.length; i++) {
			two[i] = (2 * two[i - 1]) % MOD;
		}
	}

	private static boolean collapse(List<Node> l, Node node) {
		List<Node> zero = new ArrayList<Node>(), one = new ArrayList<Node>();
		return addNode(l, node, zero, one);
	}

	private static boolean addNode(List<Node> l, Node node, List<Node> zero, List<Node> one) {
		if(zero.contains(node))
			return true;
		if(one.contains(node))
			return false;
		zero.add(node);
		l.remove(node);
		for(Node i : node.zero)
			if(!addNode(l, i, zero, one))
				return false;
		for(Node i : node.one)
			if(!addNode(l, i, one, zero))
				return false;
		return true;
	}
	
	public static void addEdge(Node a, Node b, int type) {
		if(type == 0) {
			a.zero.add(b);
			b.zero.add(a);
		} else {
			a.one.add(b);
			b.one.add(a);
		}
	}
	
	private static int index(int i, int n) {
		return Math.min(i, n - 1 - i);
	}

	public static class Node {
		
		public List<Node> zero, one;
		
		public Node() {
			zero = new ArrayList<Node>();
			one = new ArrayList<Node>();
		}
		
	}
	
}