Задано два длинных двоичных натуральных числа \(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\).
Выходные данные
Выведите ответ в десятичном представлении по модулю \(998244353\).
Примечание
Алгоритм для первого тестового примера:
- добавить к ответу \(1010_2~ \&~ 1101_2 = 1000_2 = 8_{10}\) и присвоить \(b := 110\);
- добавить к ответу \(1010_2~ \&~ 110_2 = 10_2 = 2_{10}\) и присвоить \(b := 11\);
- добавить к ответу \(1010_2~ \&~ 11_2 = 10_2 = 2_{10}\) и присвоить \(b := 1\);
- добавить к ответу \(1010_2~ \&~ 1_2 = 0_2 = 0_{10}\) и присвоить \(b := 0\).
Таким образом, ответ равен \(8 + 2 + 2 + 0 = 12\).
Алгоритм для второго тестового примера:
- добавить к ответу \(1001_2~ \&~ 10101_2 = 1_2 = 1_{10}\) и присвоить \(b := 1010\);
- добавить к ответу \(1001_2~ \&~ 1010_2 = 1000_2 = 8_{10}\) и присвоить \(b := 101\);
- добавить к ответу \(1001_2~ \&~ 101_2 = 1_2 = 1_{10}\) и присвоить \(b := 10\);
- добавить к ответу \(1001_2~ \&~ 10_2 = 0_2 = 0_{10}\) и присвоить \(b := 1\);
- добавить к ответу \(1001_2~ \&~ 1_2 = 1_2 = 1_{10}\) и присвоить \(b := 0\).
Таким образом, ответ равен \(1 + 8 + 1 + 0 + 1 = 11\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1010
1101
|
12
|
|
2
|
4 5
1001
10101
|
11
|