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 NN and KK. A string SS is constructed using the first NN distinct characters of that imaginary language. Another string TT is obtained by concatenating SS, KK times. How many distinct substrings are there in the string TT where at least one character has occurred more than once?”

Input

The single line of input contains two integers NN and KK (Here NN represents the number of distinct characters that are used to construct string SS. KK represents how many times string SS is concatenated to obtain string TT )

1<=N,K<=10151 <= N, K <= 10^{15}


Output

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

Samples

InputOutput
3 2
6

N=3N = 3, consider the first 33 characters are a,b,ca,b,c. So string S=S = “abc” and K=2K = 2. Initially, string TT is empty after concatenating SS two times - T=T = “abcabc”.

Now in string TT, there are 2121 substrings (size of TT, n=6n = 6, total substring =n×(n+1)2=21= \frac{n \times (n+1)}{2} = 21. From all 2121 substrings only 1515 substrings are distinct - a, ab, abc, abca, abcab, abcabc, b, bc, bca, bcab, bcabc, c, ca, cab, cabc.

Out of 1515 substrings, only 66 distinct substring has at least one character that appears more than once.

InputOutput
1000 1000
256147

Submit

Login to submit.

Statistics

71% Solution Ratio
steinumEarliest, Dec '22
Sourav1234Fastest, 0.0s
nusuBotLightest, 4.9 MB
steinumShortest, 96B
Toph uses cookies. By continuing you agree to our Cookie Policy.