Небанальні послідовності
Limits: 2 sec., 256 MiB
Задано три цілі числа \(n\), \(m\) та \(k\).
Цілочислова послідовність \(a\) називається небанальною, якщо виконуються такі умови.
Послідовність містить \(n\) елементів.
\(0 \le a_i < m\) для всіх \(1 \le i \le n\).
\(a_i + a_{i + 1} \not\equiv 0 \pmod k\) для всіх \(1 \le i \le n - 1\).
Порахуйте кількість небанальних послідовностей. Оскільки це число може бути дуже великим, виведіть остачу від його ділення на просте число \(988244353\).
Input
В першому рядку задано одне ціле число \(t\) — кількість тестів.
В кожному з \(t\) наступних рядків задано по три цілі числа \(n\), \(m\) та \(k\).
Output
В \(t\) рядках виведіть по одному цілому числу — остачу від ділення кількості небанальних послідовностей на \(988244353\).
Constraints
\(1 \le t \le 10^4\),
\(1 \le n, m, k \le 10^{18}\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 7 2 5 7 1 1 1 7 2 2 2 4 7 1 4 7 4 1 7 4 7 1 | 22 1 2 15 4 0 0 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|