Most of the properties in the village of Chavo in Mexico belong to Mr. Barriga, who charges high rental values. Kiko, the lover of square balls, is interested in buying a property with equal sides, but not in the real world, but in the metaverse!

Mr. Barriga follows an unconventional procedure to sell properties in the metaverse: First of all, the metaverse could be a $$$k$$$-dimensional universe. For a three-dimensional metaverse, that is, when $$$k$$$ equals 3, the sale is described as follows: Let a simple cube be a cube with faces parallel to the coordinate axes and with vertices of integer coordinates. Mr. Barriga owns a simple cube $$$A$$$ with side $$$n$$$, defined by the vertices at the origin and $$$(n,n,n)$$$. A simple cube $$$B$$$ entirely contained within $$$A$$$ will be chosen randomly for sale. All distinct valid cubes $$$B$$$ have the same probability of being chosen. Two cubes are distinct if they are defined by different vertices. Note that, for example, it is more likely that cube $$$B$$$ has side of 1 rather than 2, as there are more cubes with a side of 1 inside $$$A$$$ than there are with side of 2. The selling procedure can be extrapolated from the 3-dimensional case to the $$$k$$$-dimensional one. The hypercube $$$B$$$ to be sold has the same number of dimensions: $$$k$$$.

Given $$$n$$$, the side of the hypercube $$$A$$$, and $$$k$$$, the number of dimensions of the metaverse, help Kiko to determine the expected hipervolume of the cube $$$B$$$ to be sold. The answer can be represented as an irreducible fraction $$$p/q$$$. Print the fraction modulo $$$10^9+7$$$. Formally print $$$x$$$ such that $$$0 \leq x < 10^9+7$$$ and $$$x \cdot q \equiv p \mod (10^9+7)$$$. It is guaranteed that the fraction can be represented in this way. In particular, it is guaranteed that the number of distinct cubes $$$B$$$ is not congruent to $$$10^9+7$$$.