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 and . A string is constructed using the first distinct characters of that imaginary language. Another string is obtained by concatenating , times. How many distinct substrings are there in the string where at least one character has occurred more than once?”
The single line of input contains two integers and (Here represents the number of distinct characters that are used to construct string . represents how many times string is concatenated to obtain string )
In the output, have to print a single integer . Here is the number of distinct substrings in the string where at least one character has occurred more than once. Since the answer can be very large, print it modulo .
, consider the first characters are . So string “abc” and . Initially, string is empty after concatenating two times - “abcabc”.
Now in string , there are substrings (size of , , total substring . From all substrings only substrings are distinct - a, ab, abc, abca, abcab, abcabc, b, bc, bca, bcab, bcabc, c, ca, cab, cabc.
Out of substrings, only distinct substring has at least one character that appears more than once.