点 $u$ 在 $1 \rightarrow n$ 的路径上等价于同时存在路径 $1\rightarrow u$ 和 $u\rightarrow n$。故把点按照到 $1,n$ 的连通性分类。

A 类点：既可以从 $1$ 到达，又可以到达 $n$ 的点，即合法点；B 类点：可以从 $1$ 到达但不可达 $n$ 的点；C 类点：不可从 $1$ 到达的点。

这样分类的原因是，我们可以按照 ABC 的顺序依次往图中插入该类点并且对前面点之间的连边没有任何影响故可以乘法原理直接相乘方案数。

考察 A 类点。直接 dp 是 $O(n^3)$ 的，在此不再赘述。考虑容斥，注意到只考察这些点，每个点都在 $1\rightarrow n$ 的路径上当且仅当每个点都有出度和入度（点 $1$ 和 点 $n$ 只有出度或只有入度）。故从前往后 dp 强制让所有点都有入度，钦定若干点没有出度，其他点任意。记 $f_{i,j}$ 表示考察前 $i$ 个点，钦定 $[2,i-1]$ 中有 $j$ 个点无出度，方案数。转移考虑是否钦定 $i-1$ 无出度，乘以连边方案数：$f_{i,j}=(f_{i-1,j}+f_{i-1,j-1})(2^{i-j-1}-1)$。容斥记 $F_i$ 表示总 A 类点数为 $i$ 的答案，$F_i=\sum (-1)^j f_{i,j}$。

考察在 A 类点的基础上插入 B 类点，B 类点的要求是和 $1$ 相连且不连接 $n$，换言之 B 类点的前驱一定是 A 或 B 类点并且不能没有前驱。记 $g_{i,j}$ 表示考察前 $i$ 个 AB 类点里面有 $j$ 个 A 类点的方案数，转移 $g_{i,j}=g_{i-1,j-1}+g_{i-1,j}(2^{i-1}-1)$。

最后考虑插入 C 类点，C 类点发现可以任意后继，因为 AB 类点的后继一定不是 C 类点所以 C 类点不论如何都不会从 $1$ 可达。所以连一个位于 $i$ 的 C 类点的贡献是 $2^{n-i}$，记 $h_{i,j}$ 表示前 $i$ 个点里面有 $j$ 个 C 类点的贡献，转移 $h_{i,j}=h_{i-1,j}+2^{n-i} \times h_{i-1,j-1}$。

上述所有转移均需要注意 $1,n$ 必须是 A 类点。最后枚举一下 AB 两类点的个数把 $F,g,h$ 三者做个类似卷积状物算答案即可。复杂度 $O(n^2)$。

显然 $k=0$ 的方案数等于 $k=2$ 的方案数。