Score : 1000 points
Consider the following game:
For a sequence a of length N, let f(a) be the minimum score that can be obtained when the game is played on a.
Find the sum of f(a) over all sequences a of length N where each element is between 0 and K (inclusive). Since it can be extremely large, find the answer modulo 1000000007 (= 10^9+7).
Input is given from Standard Input in the following format:
N K
Print the sum of f(a) modulo 1000000007 (= 10^9+7).
2 2
10
There are nine sequences of length 2 where each element is between 0 and 2. For each of them, the value of f(a) and how to achieve it is as follows:
20 17
983853488