Truth or Lie

In the game Truth or Lie, you are given n sentences. The i‑th sentence is of the form [ \text{Sentence } x_i \text{ is } \begin{cases} \text{true} &\text{ if } s_i=1,\[6pt] \text{false} &\text{ if } s_i=0, \end{cases} ] where each (x_i) is an integer chosen uniformly at random from (1) to (n) and the bit (s_i) is fixed (given as a character in a 01–string). When you click “Good” you are allowed to set the truth values (t_1,t_2,\dots,t_n) (each either true or false) arbitrarily with the aim to make every sentence’s statement correct. For the i‑th sentence the rule is:

• If you decide the sentence is true then its content must be true, i.e. it requires that (t_{x_i}) equals the value indicated by (s_i) ((1) means true, (0) means false).
• If you decide the sentence is false then its content must be false, i.e. it requires that (t_{x_i}) is the opposite of the value indicated by (s_i).

A short calculation shows that if we write the truth values (t_i) as (0) (for false) or (1) (for true) then the condition imposed by the i‑th sentence can be written as follows:

• If (s_i=1) then [ t_{x_i} = t_i; ]
• If (s_i=0) then [ t_{x_i} = 1-t_i. ]

A key observation is that the only freedom you have is in choosing the (x_i)’s (the target indices in the sentences). Once these are fixed, one may show that there exists an assignment (t_1,\dots,t_n) making all sentences true if and only if in every cycle of the functional digraph defined by (f(i)=x_i) the parity of indices (i) with (s_i=0) (i.e. where the sentence contains “false”) is even.

More precisely, a function (f:{1,2,\dots,n}\to{1,2,\dots,n}) (where every (f(i)=x_i)) gives rise to a directed graph which decomposes into disjoint cycles with trees attached. In each cycle, for every sentence (i) one has a constraint: if (s_i=1) then the truth value of sentence (i) equals that of (f(i)), and if (s_i=0) then the truth value of sentence (i) is the opposite of that of (f(i)). A valid assignment (making “Good” the correct choice) exists if and only if every cycle has an even number of sentences with (s_i=0).

Suppose you are given the fixed (01)–sequence (s = s_1s_2\cdots s_n) (with 1 indicating “true” and 0 indicating “false”). Your task is to count the number of ways to choose (x_1,x_2,\dots,x_n) (each from (1) to (n)) so that the resulting function (f(i)=x_i) has the property that every cycle contains an even number of indices (i) with (s_i=0). Since the answer might be huge, output it modulo (998244353).

Note: It can be shown that if the set of cyclic points is \(R\subseteq\{1,2,\dots,n\}\) and if the permutation induced on \(R\) satisfies the condition, then the assignments of truth values to all sentences exist and even have exactly \(2^{C}\) solutions (where \(C\) is the number of cycles). In this problem you only need to count the number of ways to choose the \(x_i\)’s to make clicking “Good” correct.

inputFormat

The input consists of a single line containing a non‐empty 01–string s of length n (1 ≤ n ≤ 15). The i–th character of s indicates whether the i–th sentence contains the word true (1) or false (0).

outputFormat

Output a single integer, the number of ways to choose \(x_1,x_2,\dots,x_n\) (each between 1 and n) such that there exists an assignment of truth values making all sentences correct. Since the number may be large, output it modulo 998244353.

sample

1

1