Counting Good Sequences

Given two positive integers \(n\) and \(m\), we say that a positive integer sequence \(a_1, a_2, \dots, a_k\) (with \(1 \le k \le n\)) is good if:

• For every \(1 \le i \le k\), \(1 \le a_i \le m\); and
• There exists a positive integer \(l\) satisfying \(1 \le l \le \lfloor k/3 \rfloor\) such that for every \(1 \le i \le l\) the following holds: \[ a_i = a_{2l+1-i} \] In other words, the first \(2l\) elements form a palindrome.

Your task is to count the total number of good sequences whose length is at most \(n\) and output the answer modulo \(10^9+7\).

Remark. Note that if \(k < 3\) then no \(l\) satisfies \(1 \le l \le \lfloor k/3 \rfloor\); hence, sequences of lengths 1 and 2 are not considered good.

Outline of a combinatorial approach:

For any good sequence of length \(k\ge 3\), there exists an index \(l\) (with \(1 \le l \le \lfloor k/3\rfloor\)) such that the prefix \(a_1, a_2, \dots, a_{2l}\) forms a palindrome, i.e., \[ a_i = a_{2l+1-i}, \quad \text{for } 1\le i\le l. \] This condition forces the first \(l\) elements to be chosen arbitrarily (each in \([1, m]\)) and then determines the next \(l\) elements. The remaining \(k-2l\) elements can be chosen arbitrarily from \(1\) to \(m\). However, caution is needed because a sequence might have more than one such valid \(l\) index. One standard method is to count, for every possible \(l\), the number of sequences for which the smallest such index is exactly \(l\). For example, one may show that when \(l=1\) the contribution is \(m \times m^{k-2}\) (since the condition \(a_1=a_2\) must hold) and, for \(l\ge 2\), the contribution is more involved because one must also ensure that no smaller \(l'\) yields a palindromic prefix. In our sample solution we combine these contributions by writing the final answer as

[ \text{Answer} = \sum_{l=1}^{\lfloor n/3 \rfloor} C(l) \times \sum_{k=3l}^{n} m^{k-2l} \mod (10^9+7), ]

where for our intended solution we use
(C(1)=m) and for (l\ge2) we use (C(l)=m^l-m) (this formula works for the small test cases provided).

You are to implement a solution based on the idea above using fast modular exponentiation and summing of a geometric series.

inputFormat

The input consists of a single line containing two space‐separated positive integers \(n\) and \(m\). Here \(n\) is the maximum allowed sequence length and \(m\) is the upper bound for each sequence element.

outputFormat

Output a single integer: the number of good sequences of length at most \(n\) modulo \(10^9+7\).

sample

3 2

4