As a journalist, Bobo was asked to write a report about Boboland of length . Bobo initially wanted to write a report that was both complimentary and critical, but he was afraid that malicious people might take his words out of context and turn it into a critique of Boboland. A report of length can be seen as a sequence of integers where represents a statement with a praise degree of . If there are consecutive statements in the report that have a total praise degree less than and satisfy , then these statements may be taken out of context by malicious people to attack Bobo. Bobo does not want this to happen and wants to know how many different reports he can write without being taken out of context.

Formally, you need to calculate the number of integer sequences of length that satisfy:

• For all , it holds that .
•  For all , it holds that .

Since the answer may be large, you need to output it modulo .

The first line contains two positive integers  and  , denoting the length of the report and the range of statements in the report, respectively.

Output an integer in one line, denoting the answer modulo .

3 3

130

5 1

64

To aid understanding, we have provided graphical illustrations for the first example test case. We use the following seven emoji symbols from left to right to indicate the decreasing level of praise degree in the statements in the article, ranging from  to .



The following two articles meet the condition of not being taken out of context because the sum of the praise degrees of any consecutive statement segment containing more than one statement is at least .



The following two articles may be taken out of context, and the potentially out-of-context statements or paragraphs have been highlighted in red boxes.