Limits
1s, 32 MB

Team **Depuradores** and Team **Resolvers** represented their university in the **ICPC world finals 2021**. Depuradores and Resolvers both teams solved four problems in the world final.

Depuradores was hoping to become the **Asia West Champion** as they were in the first position from Asia West before the **freezing of standings.** But in the freezing time, another Asia west team solved one more problem which increased their solve count than Depuradores. So, in the prize-giving ceremony, Depuradores was able to know that they became **Second in the Asia West Region.**

After returning back to their university both teams went to meet their coaches and other teams. Team **Sedulous** was asking them for the problem set of the World final. After getting the problem set Team Sedulous found a very interesting problem. Team Sedulous **was not that strong; they were struggling to solve that problem.** One of the members of Sedulous got to know that you have a very strong zone in problem-solving. Now he is asking for your help to solve the problem. The problem description is —

**Aliban** lives in an imaginary world where everyone uses **imaginary language**. That language has an **infinite number of characters.** One day **Aliban’s** friend **Uban** came to her and asked her — “You are given two integers $N$ and $K$. A string $S$ is constructed using the first $N$ distinct characters of that imaginary language. Another string $T$ is obtained by concatenating $S$, $K$ times. How many distinct substrings are there in the string $T$ where at least one character has occurred more than once?”

The single line of input contains two integers $N$ and $K$ (Here $N$ represents the number of distinct characters that are used to construct string $S$. $K$ represents how many times string $S$ is concatenated to obtain string $T$ )

**$1 <= N, K <= 10^{15}$**

In the output, have to print a single integer $X$. Here $X$ is the number of distinct substrings in the string $T$ where **at least one character has occurred more than once**. Since the answer can be very large, **print it modulo** $998244353$**.**

Input | Output |
---|---|

3 2 | 6 |

$N = 3$, consider the first $3$ characters are $a,b,c$. So string $S =$ “abc” and $K = 2$. Initially, string $T$ is empty after concatenating $S$ two times - $T =$ “abcabc”. Now in string $T$ Out of $15$ substrings, only $6$ distinct substring has at least one character that appears more than once. |

Input | Output |
---|---|

1000 1000 | 256147 |

Login to submit.

62%
Solution Ratio

steinumEarliest,

Sourav1234Fastest, 0.0s

nusuBotLightest, 4.9 MB

steinumShortest, 96B

Toph uses cookies. By continuing you agree to our Cookie Policy.