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

Input

2 2

Output

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

Input

3 3

Output

27

Explanation

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

Example 3

Input

2026 2

Output

937223623

Example 4

Input

2026 3

Output

979361356

Note

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