Bogocubic играет в игру с amenotiomoi. Сначала Bogocubic фиксировал целое число \(n\), затем он дал amenotiomoi целое число \(x\), изначально равное \(1\).
За один ход amenotiomoi выполняет одну из следующих операций с равной вероятностью:
- увеличить \(x\) на \(1\);
- умножить \(x\) на \(2\).
Bogocubic хочет узнать, чему равно математическое ожидание числа шагов, которое должен сделать amenotiomoi, чтобы сделать \(x\) больше или равным \(n\). Найдите эту величину по модулю \(998\,244\,353\).
Формально, пусть \(M = 998\,244\,353\). Можно показать, что ответ может быть представлен в виде несократимой дроби \(\frac{p}{q}\), где \(p\) и \(q\) — целые числа, и \(q \not \equiv 0 \pmod{M}\). Выведите целое число, равное \(p \cdot q^{-1} \bmod M\). Другими словами, выведите такое целое число \(y\), что \(0 \le y < M\) и \(y \cdot q \equiv p \pmod{M}\).
Выходные данные
Для каждого набора входных данных выведите одно число — математическое ожидание числа шагов по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных \(n\le x\) без выполнения каких-либо операций, так что ответ равен \(0\).
Во втором наборе входных данных, для \(n = 4\), ниже указан список всех возможных последовательностей операций вместе с вероятностями их реализации:
- \(1\stackrel{+1}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{+1}{\longrightarrow}4\), вероятность равна \(\frac{1}{8}\);
- \(1\stackrel{\times 2}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{+1}{\longrightarrow}4\), вероятность равна \(\frac{1}{8}\);
- \(1\stackrel{+1}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{\times 2}{\longrightarrow}6\), вероятность равна \(\frac{1}{8}\);
- \(1\stackrel{\times 2}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{\times 2}{\longrightarrow}6\), вероятность равна \(\frac{1}{8}\);
- \(1\stackrel{+1}{\longrightarrow}2\stackrel{\times 2}{\longrightarrow}4\), вероятность равна \(\frac{1}{4}\);
- \(1\stackrel{\times 2}{\longrightarrow}2\stackrel{\times 2}{\longrightarrow}4\), вероятность равна \(\frac{1}{4}\).
Значит, математическое ожидание числа шагов равно \(4 \cdot \left(3 \cdot \frac{1}{8}\right) + 2 \cdot \left(2 \cdot \frac{1}{4} \right) =\frac{5}{2} \equiv 499122179 \pmod{998244353}\). В третьем наборе входных данных, для \(n = 8\), математическое ожидание числа шагов равно \(\frac{137}{32}\equiv 717488133\pmod{998244353}\).
В четвёртом наборе входных данных, для \(n = 15\), математическое ожидание числа шагов равно \(\frac{24977}{4096} \equiv 900515847 \pmod{998244353}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1
4
8
15
998244353
296574916252563317
494288321850420024
|
0
499122179
717488133
900515847
93715054
44488799
520723508
|