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 F implements Runnable {
	public static void main (String[] args) {new Thread(null, new F(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");

		char[] pat = fs.next().toCharArray();
		int n = pat.length;
		int res = 0, MOD = 998244353;
		int max = 2020;
		
		int[] pow2 = new int[max];
		pow2[0] = 1;
		for(int i = 1; i < max; i++) {
			pow2[i] = 2*pow2[i-1];
			while(pow2[i] >= MOD) pow2[i] -= MOD;
		}
		
		Edge[][] adj = new Edge[max][max];
		for(int i = 0; i < max; i++)
			for(int j = 0; j < adj[i].length; j++)
				adj[i][j] = new Edge();
		int[] deg = new int[max];
		int[] colors = new int[max];
		boolean[] vis = new boolean[max];
		int[] queue = new int[max];
		
		checks: for(int i = 1; i < n; i++) {
			Arrays.fill(deg, 0);
			int num = n+n-i;
			Arrays.fill(colors, -1);
			
			addEdge(num, num+1, 1, deg, adj);
			
			for(int j = 0; j < i; j++) {
				if(pat[j] == '?') continue;
				int v = num+pat[j]-'0';
				colors[j] = pat[j]-'0';
				addEdge(j, v, 0, deg, adj);
			}
			for(int j = 0; j < n/2; j++) {
				int other = n-j-1;
				if(other == j) continue;
				addEdge(j, other, 0, deg, adj);
			}
			for(int j = i, k = n-1; j < k; j++, k--) {
				int u = n + j-i;
				int v = n + k-i;
				addEdge(u, v, 0, deg, adj);
			}
			for(int j = i; j < n; j++) {
				if(pat[j] == '?') continue;
				int tp = pat[j] == '0' ? 0 : 1;
				int u = j;
				int v = n+j-i;
				addEdge(u, v, tp, deg, adj);
			}
			
			addEdge(n, num+1, 0, deg, adj);
			addEdge(num-1, num+1, 0, deg, adj);
			
			Arrays.fill(vis, false);
			colors[n] = colors[num-1] = 1;
			colors[num] = 0; colors[num+1] = 1;
			int numC = 0;
			for(int j = 0; j < num+2; j++) {
				if(vis[j]) continue;
				if(colors[j] == -1) continue;
				numC++;
				int tail = 0;
				queue[tail++] = j;
				vis[j] = true;
				for(int ii = 0; ii < tail; ii++) {
					int u = queue[ii];
					for(int e = 0; e < deg[u]; e++) {
						int v = adj[u][e].to;
						int type = adj[u][e].type;
						if(colors[v] == -1) {
							colors[v] = type == 0 ? colors[u] : colors[u]^1;
						}
						else {
							if(type == 0 && colors[v] != colors[u]) continue checks;
							if(type == 1 && colors[v] == colors[u]) continue checks;
						}
						if(vis[v]) continue;
						vis[v] = true;
						queue[tail++] = v;
					}
				}
			}
			
			for(int j = 1; j < num; j++) {
				if(vis[j]) continue;
				int tail = 0;
				queue[tail++] = j;
				numC++;
				for(int ii = 0; ii < tail; ii++) {
					int u = queue[ii];
					for(int e = 0; e < deg[u]; e++) {
						int v = adj[u][e].to;
						if(v >= num) continue;
						if(vis[v]) continue;
						vis[v] = true;
						queue[tail++] = v;
					}
				}
			}
			
			if(numC == 0) continue;
			res += pow2[numC-1];
			while(res >= MOD) res -= MOD;
		}
		
		out.println(res);
		
		out.close();
	}
	
	void addEdge(int u, int v, int type, int[] deg, Edge[][] adj) {
		adj[u][deg[u]].to = v; adj[u][deg[u]].type = type;
		adj[v][deg[v]].to = u; adj[v][deg[v]].type = type;
		deg[u]++; deg[v]++;
	}
	
	class Edge {
		int to, type;
		Edge() { to = type = -1; }
	}

	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}