No.3462 Buttons
タグ : / 解いたユーザー数 44
作問者 :
sepa38
くらげ
hikikomori
Problem Statement
There are a red button and a blue button. MMA-kun has decided to play by pressing these buttons.
MMA-kun has a number called the score, which is initially $0$.
Pressing the red button increases MMA-kun's score by $A$.
Pressing the blue button multiplies MMA-kun's score by $B$.
Given that he can press the buttons at most $K$ times, find the maximum score MMA-kun can achieve.
Since the answer can be very large, output it modulo $998244353$.
You are given $T$ test cases; solve each of them.
Constraints
- $1 \leq T \leq 2 \times 10^{5}$
- $|A|, |B| \leq 10^{9}$
- $1 \leq K \leq 10^{9}$
- All input values are integers.
Input
The input is given from Standard Input in the following format.
$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$
Each test case is given in the following format.
$A$ $B$ $K$
Output
Output $T$ lines.
On the $i$-th line, output the answer to the $i$-th test case modulo $998244353$.
Sample
Sample 1
Input
2 4 2 3 23 57 38
Output
16 343383691
For the $1$st test case, a score of $16$ can be achieved by pressing the buttons as follows.
- Press the red button. The score becomes $0 + 4 = 4$.
- Press the red button. The score becomes $4 + 4 = 8$.
- Press the blue button. The score becomes $8 \times 2 = 16$.
No score greater than $16$ can be achieved, so output $16$.
For the $2$nd test case, note that you should output the maximum achievable score modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。