时间限制： 1.5 秒

空间限制： 512 MB

题目描述

小明的后院种了 $n$ 行 $n$ 列的树，养了 $k$ 只鸽子。由于小明有强迫症，他在第 $i$ 行 $j$ 列的树上恰好安置了 $i\times j$ 个鸽子窝。

每个鸽子窝都能容纳无穷多的鸽子，每天鸽子们都会选择住在同一棵树上，在这棵树上鸽子们会任意挑选一个鸽子窝入住。请问一天里所有的鸽子有多少种入住分布的情况？两种分布情况不同，当且仅当至少一只鸽子居住在不同的鸽子窝当中。

由于输出的结果可能很大，你需要输出取模 $10^9+7$ 的结果。

输入格式

从标准输入读入数据。

输入两个整数 $n, k$。

输出格式

输出到标准输出。

一个整数，表示答案对 $10^9+7$ 取模的结果。

2 2

25

样例 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$。

1000 10

688984829

子任务

对于所有数据，保证 $1\le n\le 10^9+6, ~1\le k<10^7$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$n\le$	$k<$
1	20	$10^6$	$50$
2	30	$10^7$	$100$
3		$10^8$	$10^3$
4	10		$10^5$
5	5	$10^9+6$	$10^6$
6			$10^7$

提示 0

猜猜为什么子任务 1 就设置了这么大的 $n$ 呢？不妨动手推一下方案数是否满足什么规律？

提示 1

当你想求一个 $k$ 阶多项式的各项系数时，其实你只需要知道这个多项式在 $k+1$ 个点处的值时，就可以确定这个多项式的唯一形式了（也就是各项系数均有唯一解）。解线性方程组的话，可以使用高斯消元来完成。

提示 2

主播主播，你的高斯消元确实强，但太吃复杂度了，有没有更加简单又强势的算法推荐一下？

有的兄弟，有的。这么强的英雄还有一个。

当给定了 $k$ 阶多项式 $f$ 以及其 $k+1$ 个点对应的值 $f(x_0),...,f(x_k)$ 时，我们求出 $x$ 处的值可以用以下公式：

$$f(x)=\sum_{i=0}^n f(x_i)\prod_{j\ne i} \dfrac{x-x_j}{x_i-x_j} $$

提示 3

主播主播，你这个还只是 T0.5 算法啊，我想要 T0 级别的算法怎么办？

我知道你很急，但是你先别急。试试看如果上面式子当中，$x_i=i$ 的话，再操作一下试试看，上面这个式子有没有出现一些可以优化时间复杂度的关键点？

提示 4

主播主播，我用了你推荐的算法还是打过不去，怎么办捏？

不妨想想看，怎么更快速地求出所有的 $f(x_i)$ 呢？

提示 5

如果还是过不去的话，请尽量避免使用 long long 进行数据的存储与运算，同时在预处理逆元时避免多余的除法和取模运算。这是成为卡常带师的关键修行！

最后几个子任务分数较少，性价比很低，主播这边建议大家合理规划做题时间呢~