幽香这几天学习了魔法，准备建造一个大型的时空传送阵。
幽香现在可以在幻想乡的 $n$ 个地点建造一些传送门，如果她建造了从地点 $a$ 与地点 $b$ 之间的传送门，那么从 $a$ 到 $b$ 和从 $b$ 到 $a$ 都只需要单位 $1$ 的时间。
同时这些地点之间在地理上是非常遥远的，因此来往他们必须使用传送门。
现在幽香想要问你，有多少种建造传送门的方案，使得地点 $1$ 和地点 $n$ 之间的最短距离恰好为 $k$ ？两个方案不同当且仅当建造的传送门的集合不同。不能建造节点到自身的传送门，两个点之间也最多造一个传送门。
$n,k\leq 100$ 。
最近看dls讲的一道题，因为hihocoder可能要凉凉了，写个文章记录一下。
点 $1$ 和 $n$ 之间距离为 $k$ 说明：如果从点 $1$ 出发进行BFS，那么搜到点 $n$ 一定是第 $k$ 轮，这意味着我们可以将整张图根据从点 $1$ 开始BFS被搜到的轮数划分成一个分层图，然后在这张分层图上就可以dp了。
设 $dp[i][j][k]$ 表示分层图前 $i-1$ 层已经用了 $j$ 个点，第 $i-1$ 层用了 $k$ 个点的方案数，那么前 $k-1$ 层的转移方程如下（枚举第 $i$ 层有 $x$ 个点）：
$$
dp[i][j+x][x]+=dp[i-1][j][k]\times 2^\binom{x}{2}\times (2^k-1)^{x}\times \binom{n-j-1}{x}
$$
解释如下，从第 $i-1$ 层到第 $i$ 层需要考虑的有：
- 连边方式
连边方式分两类：两层之间的连边和第 $i$ 层内部的连边。第 $i-1$ 层的点数为 $k$ ，而第 $i$ 层的点数为 $x$ ，对于第 $i$ 层中的每个点而言，至少有一个前一层的点与它相邻，因此一共有 $2^{k}-1$ 种方案，同时由于第 $i$ 层的每个点独立，因此方案数为 $(2^k-1)^x$ 。第 $i$ 层内部的连边则比较简单，$x$ 个点之间一共 $\binom{x}{2}$ 条边，每条边都可以连或不连。 - 点的编号
每层可以选择的点的方案数为 $\binom{n-j-1}{x}$ ，需要注意我们不能选择 $n$ 号点。
然后是第 $k$ 层的方案数，第 $k$ 层的不同点在于这一层必定有 $n$ 号点，因此该层可以选择的点的方案数为 $\binom{n-j-1}{x-1}$ 。（前 $i-1$ 层已经用了 $j$ 个点，第 $k$ 层有 $x$ 个点）
最后将所有剩余的点考虑进来，一共还剩下 $n-j-x$ 个点，这些点内部可以任意连边，并且这些点和第 $k$ 层的点也可以任意连边，方案数为 $2^{\binom{n-j-x}{2}}\times 2^{( n-j-x )x}$ 。
最后附赠一份不知道正确性的代码（hihocoder暂时无法提交。。。）：
#include <bits/stdc++.h>
using namespace std;
constexpr int P = 1e9 + 7;
constexpr int N = 110;
// assume -P <= x < 2P
int norm(int x) {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
template<class T>
T power(T a, int b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct Z {
int x;
Z(int x = 0) : x(norm(x)) {}
int val() const {
return x;
}
Z operator-() const {
return Z(norm(P - x));
}
Z inv() const {
assert(x != 0);
return power(*this, P - 2);
}
Z& operator*=(const Z& rhs) {
x = 1LL * x * rhs.x % P;
return *this;
}
Z& operator+=(const Z& rhs) {
x = norm(x + rhs.x);
return *this;
}
Z& operator-=(const Z& rhs) {
x = norm(x - rhs.x);
return *this;
}
Z& operator/=(const Z& rhs) {
return *this *= rhs.inv();
}
friend Z operator*(const Z& lhs, const Z& rhs) {
Z res = lhs;
res *= rhs;
return res;
}
friend Z operator+(const Z& lhs, const Z& rhs) {
Z res = lhs;
res += rhs;
return res;
}
friend Z operator-(const Z& lhs, const Z& rhs) {
Z res = lhs;
res -= rhs;
return res;
}
friend Z operator/(const Z& lhs, const Z& rhs) {
Z res = lhs;
res /= rhs;
return res;
}
};
// dp[i][j][k] 表示前i层一共用了j个点，最后一层用了k个点的方案数
Z dp[N][N][N];
vector<Z> fac, ifac, two;
void prepareFac(int n) {
fac.resize(n + 1);
two.resize(n + 1);
ifac.resize(n + 1);
two[0] = fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * Z(i);
two[i] = two[i - 1] * Z(2);
}
// 1/(i + 1)! * (i+1) = 1/i!
ifac[n] = fac[n].inv();
for (int i = n - 1; i >= 0; i--) {
ifac[i] = ifac[i + 1] * Z(i + 1);
}
}
Z binom(int n, int m) {
if (n < 0 || m < 0 || n < m) return 0;
return fac[n] * ifac[m] * ifac[n - m];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, k;
cin >> n >> k;
prepareFac(n * n);
Z inverse = Z(n - 1).inv(), res = 0;
dp[0][1][1] = Z(1);
for (int i = 1; i <= k; i++) { // 枚举第i层
for (int j = i; j <= n; j++) { // 枚举当前一共已经用了j个点
for (int x = 1; x <= j; x++) { // 枚举第i - 1层用了x个点
for (int y = 1; y + j <= n; y++) { // 枚举第i层要加入y个点
// dp[i-1][j][x] -> dp[i][j+y][y]
Z val = dp[i - 1][j][x] * power((two[x] - Z(1)), y) * two[y * (y - 1) / 2] * binom(n - j - 1, y - (i == k));
if (i == k) { // 最后一层的特判
// 剩下(n - j - y)个点和最后一层之间随意连边 * 这些点内部随意连边
int m = n - j - y;
val *= two[m * (m - 1) / 2 + y * m];
res += val;
} else {
dp[i][j + y][y] += val;
}
}
}
}
}
cout << res.val() << "\n";
return 0;
}