U531066 鸽子窝

**时间限制：** 1.2 秒 **空间限制：** 512 MB

小明的后院种了 $n$ 行 $n$ 列的树，养了 $k$ 只鸽子。由于小明有强迫症，他在第 $i$ 行 $j$ 列的树上恰好安置了 $i\times j$ 个鸽子窝。 每个鸽子窝都能容纳无穷多的鸽子，每天鸽子们都会选择住在同一棵树上，在这棵树上鸽子们会任意挑选一个鸽子窝入住。请问一天里所有的鸽子有多少种入住分布的情况？两种分布情况不同，当且仅当至少一只鸽子居住在不同的鸽子窝当中。 由于输出的结果可能很大，你需要输出取模 $10^9+7$ 的结果。

无

无

### 样例 1 解释 我们设 $f(i,j)$ 表示第 $i$ 行第 $j$ 列的树上会有多少种鸽子居住的情况。$f(1,1)=1^2=1,f(1,2)=f(2,1)=(2\times 1)^2=4,f(2,2)=(2\times 2)^2=16$，所以总方案数是 $25$ 。 ### 数据范围 对于所有数据，保证 $1\le n\le 10^9+6, ~1\le k