Expected Number of Queries in the Hidden Sequence Game

This is a traditional problem.

An interactive library has a hidden sequence \(a=[a_1,a_2,\ldots,a_n]\) of length \(n\) with each \(a_i\) an integer in \([1,k]\). Each query consists of submitting a sequence \(b=[b_1,b_2,\ldots,b_n]\) (with each \(b_i\in[1,k]\)). The library then returns a binary sequence \(s\) of length \(n\) where \(s_i=1\) if \(b_i=a_i\) and \(s_i=0\) otherwise.

The library is non‐adaptive so the hidden sequence is fixed in advance. Let \(f(a)\) be the minimum number of queries (using an optimal strategy) required to determine \(a\). Note that even if you have determined \(a\) by deduction, you must still submit one more query that exactly matches \(a\) (i.e. when the answer returned is \([1,1,\ldots,1]\)) in order to "guess" the sequence.

It can be shown that an optimal strategy is to query the sequence in a fixed order: first try all \(1\)'s, then for every position that was not confirmed, try \(2\) and so on. In this way, if the maximum element in \(a\) is \(m\), then \(f(a)=m+1\). Therefore, the expected value (over all \(k^n\) sequences chosen uniformly) is

[ E[f(a)] = \frac{\sum_{m=1}^{k} m\Bigl(m^n-(m-1)^n\Bigr)+k^n}{k^n} \pmod{10^9+7}. ]

Your task is: given \(n\) and \(k\), compute \(E[f(a)]\) modulo \(10^9+7\).

inputFormat

The input consists of a single line containing two integers \(n\) and \(k\) separated by a space.

outputFormat

Output a single integer: the expected number of queries \(E[f(a)]\) modulo \(10^9+7\).

sample

1 1

2