Sequence Weight Sum

Given two integers \(n\) and \(m\), consider all sequences of integers of length \(L\) where \(0 \le L \le m\) and each element is chosen from the set \([1, n]\). The weight of a sequence is defined as:

\[ w(S) = (\text{number of distinct elements in } S) + 1, \]

For example, the empty sequence (\(L=0\)) has weight \(1\), and a sequence like [1, 9, 2, 6, 8, 1, 7] has weight \(7\) (since it has 6 distinct elements plus 1).

Your task is to calculate the sum of weights of all possible sequences (of all lengths from \(0\) to \(m\)) modulo \(10^9+7\). That is, compute:

\[ \sum_{L=0}^{m} \;\sum_{S \in [1, n]^L} \Bigl(\bigl|\{{\rm elements~in~} S\}\bigr| + 1\Bigr) \mod (10^9+7). \]

Hint: Notice that the weight of a sequence \(S\) can be expressed as 1 + (number of distinct elements in \(S\)). The problem can be approached by linearity of expectation: for every number between 1 and \(n\), count the number of sequences in which that number appears at least once.

inputFormat

The input consists of a single line with two space‐separated integers \(n\) and \(m\), where \(n\) is the maximum number in the sequence (each element is chosen from 1 to \(n\)) and \(m\) is the maximum length of the sequence. Sequences of all lengths from 0 to \(m\) (inclusive) should be considered.

outputFormat

Output a single integer: the sum of weights of all sequences modulo \(10^9+7\).

sample

1 1

3