Cerință
În fiecare vară, Stelinuța merge în Cipru pentru o tabără de programare de 11 zile, iar în timpul petrecut acolo, îi place să meargă la înot și să facă snorkeling în mare.
Într-o zi, în timp ce făcea snorkeling, a găsit un colier de perle foarte interesant: un fir drept (neciclic) cu perle pe el. Inițial, toate perlele trebuiau să fie fie negre, fie albe. Totuși, unele perle erau atât de deteriorate încât nu mai putea distinge nici măcar culoarea lor originală.
Din această întâmplare, Stelinuța a avut o idee: imaginează-ți că poți elimina oricare două perle adiacente care au aceeași culoare de pe colier. Ea este curioasă să știe în câte moduri diferite ar fi putut arăta colierul original, astfel încât, după aplicarea acelei operațiuni de oricâte ori, să rămână fără nici o perlă pe colier. Deoarece răspunsul poate fi foarte mare, este suficient să-l găsească modulo $998.244.353$.
Date de intrare
Prima linie conține un șir format din caracterele “$0$”, “$1$” și “$?$”, descriind colierul pe care Stelinuța l-a găsit. Fiecare perlă este reprezentată astfel:
- ”$1$”: perla este neagră,
- ”$0$”: perla este albă,
- ”$?$”: culoarea originală este necunoscută.
Lungimea șirului va fi cel puțin $1$ și de cel mult $2 \cdot 10^{5}$.
Date de ieșire
Să se afișeze un singur număr: Numărul de moduri în care putea să arate colierul modulo $998.244.353$.
Exemple
Intrare
01?1??
Ieșire
1
Statement
Every summer Stelinuța goes to Cyprus for an 11-day programming camp, and while being there, she loves to go swimming and snorkeling in the sea.
One day, when she was snorkeling, she found a very interesting pearl necklace: a straight (non-cyclic) thread with pearls on it. Originally, all the pearls had to be either black or white. However, some pearls were so damaged that she couldn’t even distinguish their original color.
From that, Stelinuța came up with an idea: imagine that you can remove any two adjacent pearls that have the same color from the necklace. She is curious to know in how many different ways the original necklace could have looked so that, after applying that operation any number of times, she could end up with an empty necklace. As the answer may be very large, it is sufficient to find it modulo $998.244.353$.
Input
The first line contains a string containing “$0$”, “$1$” and “$?$”, describing the necklace Stelinuța found.
Each pearl is represented as follows:
- ”$1$”: the pearl is black,
- ”$0$”: the pearl is white,
- ”$?$”: the original color is unknown.
The length of the string will be at least $1$ and at most $2 \cdot 10^{5}$.
Output
Output a single integer: the number of different ways the necklace could have looked like modulo $998.244.353$.
Examples
Intrare
01?1??
Ieșire
1