Description

Recently, Xiao Dong has made amazing progress in counting the number of spanning trees in undirected connected graphs. He discovered:

• The number of spanning trees of a cycle with $n$ vertices is $n$.
• The number of spanning trees of a complete graph with $n$ vertices is $n^{n-2}$.

These two discoveries made him ecstatic and strengthened his determination to keep counting spanning trees for various graphs.

One day, during a class reunion, everyone sat around a large round table. Xiao Dong looked around and immediately thought of the spanning tree problem. If each classmate is a vertex and edges are added between adjacent seats (distance between vertices is $1$), the graph becomes a cycle. However, Xiao Dong was already very proficient at counting spanning trees of cycles and lost interest. So, he modified the graph: he not only added edges between adjacent seats, but also between classmates with one seat in between (distance between vertices is $2$). We collectively call these cases directly connected by an edge; see Figure 1.

Xiao Dong had not counted spanning trees for this type of graph before, but he remembered a general method taught by his teacher for counting spanning trees of any graph: construct an $n\times n$ matrix $A=\{ a_{i,j}\}$, where:

$$a_{i,j}=\begin{cases} d_i & i=j \\ -1 & \text{$i, j$ 之间有边直接相连} \\ 0 & \text{其他情况} \end{cases}$$

The matrix $A$ corresponding to Figure 1 is shown below. To compute the number of spanning trees for the graph in Figure 1, remove the last row and last column of matrix $A$ to obtain an $(n-1)\times(n-1)$ matrix $B$. The number of spanning trees equals the determinant of $B$.

$$A=\begin{bmatrix} 4 & -1 & -1 & 0 & 0 & 0 & -1 & -1 \\ -1 & 4 & -1 & -1 & 0 & 0 & 0 & -1 \\ -1 & -1 & 4 & -1 & -1 & 0 & 0 & 0 \\ 0 & -1 & -1 & 4 & -1 & -1 & 0 & 0 \\ 0 & 0 & -1 & -1 & 4 & -1 & -1 & 0 \\ 0 & 0 & 0 & -1 & -1 & 4 & -1 & -1 \\ -1 & 0 & 0 & 0 & -1 & -1 & 4 & -1 \\ -1 & -1 & 0 & 0 & 0 & -1 & -1 & 4 \\ \end{bmatrix},\\ B=\begin{bmatrix} 4 & -1 & -1 & 0 & 0 & 0 & -1 \\ -1 & 4 & -1 & -1 & 0 & 0 & 0 \\ -1 & -1 & 4 & -1 & -1 & 0 & 0 \\ 0 & -1 & -1 & 4 & -1 & -1 & 0 \\ 0 & 0 & -1 & -1 & 4 & -1 & -1 \\ 0 & 0 & 0 & -1 & -1 & 4 & -1 \\ -1 & 0 & 0 & 0 & -1 & -1 & 4 \\ \end{bmatrix},$$

Hence the number of spanning trees is $\det B =3528$. Xiao Dong found that using the general method was too complicated to compute, and it was also hard to find a simpler closed form by other means. So, he simplified the graph: he split the round table at one point, turning all classmates into a chain, and connected vertices at distance $1$ and distance $2$. For example, the case with eight vertices is as follows:

This greatly reduces the total number of spanning trees. Xiao Dong kept thinking until the party was over and finally found a quick method to compute the number of spanning trees of this graph. However, if vertices at distance $3$ are also connected, he did not know how to compute it quickly. Now, please help Xiao Dong count the number of spanning trees for this type of graph.

Input Format

The input contains two integers $k, n$ separated by a space. Here, $k$ means all pairs of vertices whose distance is at most $k$ (inclusive) along the chain are connected by an edge, and $n$ means there are $n$ vertices.

Output Format

Output a single integer: the number of spanning trees. Since the answer may be large, output the answer modulo $65521$.

3 5

75

Hint

Sample corresponds to the following graph:

$$A = \begin{bmatrix} 3 & -1 & -1 & -1 & 0 \\ -1 & 4 & -1 & -1 & -1 \\ -1 & -1 & 4 & -1 & -1 \\ -1 & -1 & -1 & 4 & -1 \\ 0 & -1 & -1 & -1 & 3 \\ \end{bmatrix}, B = \begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 4 & -1 & -1 \\ -1 & -1 & 4 & -1 \\ -1 & -1 & -1 & 4 \\ \end{bmatrix}, \det B = 75$$

Constraints

Test point id	$k$	$n$
1	$=2$	$\le 10$
2	$=3$	$=5$
3	$=4$	$\le 10$
4	$=5$	$=10$
5	$\le 3$	$\le 100$
6	$\le 5$
7	$\le 3$	$\le 2000$
8	$\le 5$	$\le 10000$
9	$\le 3$	$\le 10^{15}$
10	$\le 5$

Additionally, for all testdata, $2\le k\le n$.

Further hint

One way to compute a determinant is as follows. Let $\sigma(\bm P)$ denote the number of inversions in the permutation $\bm P$. Then the determinant of matrix $B$ can be computed by:

$$\det B=\sum_{\bm P=[p_1,p_2,\cdots,p_n]} (-1)^{\sigma(\bm P)} \prod_{i=1}^n b_{i,p_i}$$

For example, for $B=\begin{bmatrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 0\end{bmatrix}$, its determinant is computed as:

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|}\hline \bm P & \sigma(\bm P) & b_{1,p_1} & b_{2,p_2} & b_{3,p_3} & (-1)^{\sigma(\bm P)}\prod_{i=1}^n b_{i,p_i} \\ \hline [1, 2, 3] & 0 & 1 & 5 & 0 & 0 \\ \hline [1, 3, 2] & 1 & 1 & 6 & 8 & -48 \\\hline [2, 1, 3] & 1 & 2 & 4 & 0 & 0 \\\hline [2, 3, 1] & 2 & 2 & 6 & 7 & 84 \\\hline [3, 1, 2] & 2 & 3 & 4 & 8 & 96 \\\hline [3, 2, 1] & 3 & 3 & 5 & 7 & -105 \\\hline \end{array}$$

So the determinant of $B$ is $0-48+0+84+96-105=27$.

Translated by ChatGPT 5