Вам дано целое положительно число \(n\). Так как \(n\) может быть большим, вам дано его представление в двоичной системе счисления.
Вычислите количество троек целых чисел \((a,b,c)\) таких, что \(0 \leq a,b,c \leq n\), и значение \(a \oplus b\), \(b \oplus c\) и \(a \oplus c\) образуют стороны невырожденного треугольника.
Здесь \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Выведите ответ по модулю \(998\,244\,353\).
Три положительных числа \(x\), \(y\) и \(z\) образуют стороны невырожденного треугольника, если и только если \(x+y>z\), \(x+z>y\) и \(y+z>x\).
Выходные данные
Выведите одно число — количество троек \((a,b,c)\), удовлетворяющих условию, по модулю \(998\,244\,353\).
Примечание
В первом примере \(101_2=5\).
- Тройка \((a, b, c) = (0, 3, 5)\) подходит, потому что \((a\oplus b, b\oplus c, c\oplus a) = (3, 6, 5)\) образуют стороны невырожденного треугольника.
- Тройка \((a, b, c) = (1, 2, 4)\) подходит, потому что \((a\oplus b, b\oplus c, c\oplus a) = (3, 6, 5)\) образуют стороны невырожденного треугольника.
\(6\) перестановок каждой из этих двух троек тоже подходят, поэтому ответ \(12\).
В третьем примере \(11\,011\,111\,101\,010\,010_2=114\,514\). Полный ответ (без взятия по модулю) равен \(1\,466\,408\,118\,808\,164\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
101
|
12
|
|
2
|
1110
|
780
|
|
3
|
11011111101010010
|
141427753
|