P11957 「ZHQOI R1」Power Sum

Given integers $ n, x, k $, compute the value of the following expression: $$ \sum_{i=0}^n (-1)^{\text{popcnt}(i)} (i + x)^k $$ where the result is taken modulo $ 998244353 $. **Special Note**: $ 0^0 $ is defined as $ 1 $. Here, $ \text{popcnt}(x) $ denotes the number of $1$'s in the binary representation of $ x $.

A single line containing three integers $ n, x, k $.

Output a single integer representing the answer.

**Constraints** **This problem uses subtask scoring.** For all test cases: - $ 0 \leq n \leq 10^{12} $, - $ 0 \leq x \leq 10^9 $, - $ 0 \leq k \leq 10^5 $. | Subtask | $ n \leq $ | $ k \leq $ | Score | | :-----: | :---------------: | :----------: | :----: | | 1 | $ 10^6 $ | $ 10^5 $ | $ 7 $ | | 2 | $ 10^8 $ | $ 10^5 $ | $ 8 $ | | 3 | $ 10^{12} $ | $ 0 $ | $ 5 $ | | 4 | $ 10^{12} $ | $ 1 $ | $ 10 $ | | 5 | $ 10^{12} $ | $ 2 $ | $ 10 $ | | 6 | $ 10^{12} $ | $ 100 $ | $ 10 $ | | 7 | $ 10^{12} $ | $ 10^3 $ | $ 15 $ | | 8 | $ 10^{12} $ | $ 10^4 $ | $ 15 $ | | 9 | $ 10^{12} $ | $ 10^5 $ | $ 20 $ |