Вам дана строка \(s\), состоящая из символов «1», «0» и «?». Гарантируется, что первый символ в \(s\) будет «1». Пусть \(m\) будет количеством символов в \(s\).
Подсчитайте количество способов выбрать пару целых чисел \(a, b\), которые удовлетворяют следующему:
Посчитайте это по модулю \(998244353\).
Первая строка содержит строку \(s\) (\(1 \leq |s| \leq 1\,000\)). \(s\) состоит только из «1», «0» and «?». Гарантируется, что первый символ в \(s\) — это «1».
Выведите одно целое число — количество пар, удовлетворяющих условиям, по модулю \(998244353\).
В первом примере, нам подходят \((111, 10001), (11, 10101), (1001, 11111)\).
10110
3
1?0???10
44
1?????????????????????????????????????
519569202
1
0
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач