Counting Palindromes

Bob works at the Cookie Factory, where cookies are baked in flavours numbered $1$ to $n$. Every evening, a conveyor belt carries a sequence of $n$ cookies past him.

Alice's birthday is coming, and so Bob wants to sneak her a gift, a palindromic cookie box.

A palindromic box of cookies is a subsequence (not necessarily continuous) of cookies chosen from the belt (in order) whose flavour sequence reads the same forwards and backwards.

Alice is picky though: she won't accept a box unless it contains at least $x$ cookies.

Bob doesn't want to get fired, so he'll pack the smallest valid palindromic box possible so he's less likely to get caught.

Formally, for a given conveyor belt arrangement $a$, define $f(a)$ as the length of the shortest palindromic subsequence of length at least $x$. If no such subsequence exists, $f(a) = 0$.

Since the factory runs many different arrangements over many nights, Bob wants to know the sum of $f(a)$ over all possible conveyor belt arrangements of $n$ cookies where each cookie can have a flavour from $1$ to $n$. That is, there are $n^n$ possible conveyor belt arrangements.

Help Bob figure out the sum (modulo $10^9 + 7$) before Alice's birthday.

Input

A single line containing two integers $n$ and $x$.

Output

A single integer, the answer modulo $10^9 + 7$.

Constraints

• $1 \leq n \leq 10^6$
• $x \in \{2, 3\}$

Example 1

2 2

4

Explanation

There are $4$ possible conveyor belt arrangements.

• $[1, 1]: f([1, 1]) = 2$
• $[1, 2]: f([1, 2]) = 0$
• $[2, 1]: f([2, 1]) = 0$
• $[2, 2]: f([2, 2]) = 2$

So the sum is $2 + 0 + 0 + 2 = 4$.

Example 2

3 3

27

Explanation

There are $27$ possible conveyor belts, $9$ of which have $f(a) = 3$ and the rest have $f(a) = 0$.

Example 3

2026 2

937223623

Example 4

2026 3

979361356

Note

• $n$ represents both the number of flavours and the number of cookies on the conveyor belt.