Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Сумма AND двоичных чисел
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано два длинных двоичных натуральных числа $$$a$$$ и $$$b$$$ длин $$$n$$$ и $$$m$$$ соответственно. Вы собираетесь повторять следующий процесс: если $$$b > 0$$$, тогда добавить к ответу значение $$$a~ \&~ b$$$ и поделить $$$b$$$ на $$$2$$$ с округлением вниз (то есть удалить последнюю цифру $$$b$$$) и продолжить процесс, иначе прекратить процесс.

Значение $$$a~ \&~ b$$$ означает побитовый AND $$$a$$$ и $$$b$$$. Ваша задача — посчитать ответ по модулю $$$998244353$$$.

Заметим, что вам необходимо добавлять значение $$$a~ \&~ b$$$ к ответу в десятичном представлении, не в двоичном. Таким образом, ваша задача заключается в том, чтобы посчитать ответ в десятичном представлении. Например, если $$$a = 1010_2~ (10_{10})$$$ и $$$b = 1000_2~ (8_{10})$$$, тогда значение $$$a~ \&~ b$$$ будет равно $$$8$$$, а не $$$1000$$$.

Входные данные

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — длина $$$a$$$ и длина $$$b$$$ соответственно.

Вторая строка входных данных содержит одно длинное число $$$a$$$. Гарантируется, что это число состоит ровно из $$$n$$$ нулей и единиц, а первая цифра всегда равна $$$1$$$.

Третья строка входных данных содержит одно длинное число $$$b$$$. Гарантируется, что это число состоит ровно из $$$m$$$ нулей и единиц, а первая цифра всегда равна $$$1$$$.

Выходные данные

Выведите ответ в десятичном представлении по модулю $$$998244353$$$.

Примеры
Входные данные
4 4
1010
1101
Выходные данные
12
Входные данные
4 5
1001
10101
Выходные данные
11
Примечание

Алгоритм для первого тестового примера:

  1. добавить к ответу $$$1010_2~ \&~ 1101_2 = 1000_2 = 8_{10}$$$ и присвоить $$$b := 110$$$;
  2. добавить к ответу $$$1010_2~ \&~ 110_2 = 10_2 = 2_{10}$$$ и присвоить $$$b := 11$$$;
  3. добавить к ответу $$$1010_2~ \&~ 11_2 = 10_2 = 2_{10}$$$ и присвоить $$$b := 1$$$;
  4. добавить к ответу $$$1010_2~ \&~ 1_2 = 0_2 = 0_{10}$$$ и присвоить $$$b := 0$$$.

Таким образом, ответ равен $$$8 + 2 + 2 + 0 = 12$$$.

Алгоритм для второго тестового примера:

  1. добавить к ответу $$$1001_2~ \&~ 10101_2 = 1_2 = 1_{10}$$$ и присвоить $$$b := 1010$$$;
  2. добавить к ответу $$$1001_2~ \&~ 1010_2 = 1000_2 = 8_{10}$$$ и присвоить $$$b := 101$$$;
  3. добавить к ответу $$$1001_2~ \&~ 101_2 = 1_2 = 1_{10}$$$ и присвоить $$$b := 10$$$;
  4. добавить к ответу $$$1001_2~ \&~ 10_2 = 0_2 = 0_{10}$$$ и присвоить $$$b := 1$$$;
  5. добавить к ответу $$$1001_2~ \&~ 1_2 = 1_2 = 1_{10}$$$ и присвоить $$$b := 0$$$.

Таким образом, ответ равен $$$1 + 8 + 1 + 0 + 1 = 11$$$.