If there is no edge going to vertex \(1\)

We first consider the case without an edge going to vertex \(1\); that is, \(D_n = 0\) and \(A_1 = 0\). Let

• \(\mathrm{dp}_{n, m} : \) (the number of \(m\)-edge walks from vertex \(1\) to vertex \(n\)),

then \(\mathrm{dp}_{n,m}\) is expressed as follows. (DP stands for Dynamic Programming.) (\([\mathrm{cond}]\) is a function that takes \(1\) if \(\mathrm{cond}\) is true and \(0\) if it is false.) What we want is \(\mathrm{dp}_{N, K}\).

\[ \begin{aligned} \mathrm{dp}_{0, 0} &= 1 \\ \mathrm{dp}_{n,m} &= \mathrm{dp}_{n-1,m}[A_n = 1] \\ &+ \mathrm{dp}_{n-1,m-1}[B_{n-1} = 1] \\ &+ \mathrm{dp}_{n-1,m-2} [C_{n-2} = 1] \end{aligned} \]

We express it as a generating function. \(F_n(x) = \sum_{m} \mathrm{dp}_{n,m} x^m\) satisfies the following equation. (Note that \(A_1 = 0\).)

\[ \begin{aligned} F_1(x) &= 1 \\ F_n(x) &= x F_n(x) [A_n=1] \\ &+ x F_{n-1}(x) [B_{n-1} = 1] \\ &+ x F_{n-2}(x) [C_{n-2} = 1] \\ \iff F_n(x) &= \left(\frac{1}{1-x [A_n = 1]}\right) \\ & \times(x F_{n-1}(x) [B_{n-1} = 1]+ x F_{n-2}(x) [C_{n-2} = 1]) \end{aligned} \]

We define \(P_i(x), Q_i(x)\), and \(R_i(x)\) by

\[ \begin{aligned} P_n(x) &= \frac{1}{1-x [A_n = 1]} \\ Q_n(x) &= x [B_{n-1} = 1] \\ R_n(x) &= x [C_{n-2} = 1] \end{aligned} \]

to simplify the expression as follows:

\[ \begin{aligned} F_1(x) &= 1 \\ F_n(x) &= P_n(x) \times(Q_n(x) F_{n-1} (x) + R_n(x) F_{n-2}(x)). \end{aligned} \]

This recurrence relations enable to find \(\mathrm{dp}_{N, K} = \lbrack x^K \rbrack F_N(x)\). While naively evaluating the recurrence relation costs \(\Omega(N^2)\) time, we notice the following matrix representation:

\[ \left( \begin{array}{c} F_{n+1} \\ F_{n} \end{array} \right) = \left( \begin{array}{cc} P_n Q_n & P_n R_n \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} F_n \\ F_{n-1} \end{array} \right) \]

\[ \left( \begin{array}{c} F_{N} \\ F_{N-1} \end{array} \right) = \left( \begin{array}{cc} P_N Q_N & P_N R_N \\ 1 & 0 \end{array} \right) \cdots \left( \begin{array}{cc} P_2 Q_2 & P_2 R_2 \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} F_{1} \\ 0 \end{array} \right), \]

where the components of the matrix are represented by rational functions whose numerator and denominator are of degree one or less, so we can find \(F_N\) in a total of \(\mathrm{O}(N \log^2 N)\) by merging (multiplying) the matrices in a binary-tree-ish way. (Alternatively, we can multiply by \((1 - x)\) the matrix containing \(\frac{1}{1-x}\) and divide the total product by the power of \((1-x)\), so that it boils down to finding the total product of polynomial-coefficient matrices, which is easy to implement because it does not require operations on rational functions.)

If it contains an edge going to vertex \(1\)

We first consider the case with an edge going to vertex \(1\).

In such case, a walk is in the following form:

\[1 \to \dots \to 1 \to \dots \to 1 \to \dots \to N,\]

where it goes back to \(1\) several times before heading to \(N\).
We exploit this structure to express it as a generating function. The generating function of the numbers of \(m\)-edge walks starting from and ending at vertex \(1\) that does not visit vertex \(1\) halfway is expressed as

\[\left(\sum_{ \lbrace n \vert D_n = 1 \rbrace } F_n\right) \times x = x \sum_{1 \leq n \leq N} D_n F_n,\]

by considering the last vertex before the endpoint. With

\[G_n = \sum_{1 \leq m \leq n} {D_m F_m},\]

the aforementioned generating function is expressed as \(x G_N\).

Next, we consider the generating function of the numbers of \(m\)-edge walks starting from and ending at vertex \(1\). The count equals the number of \(0\)-or-more repetitions of walks from and to vertex \(1\) without visiting vertex \(1\) halfway, whose total lengths amount to \(m\), so the sought generating function is

\[1 + xG_N + x^2 G_N^2 + \dots = \frac{1}{1 - x G_N}.\]

Therefore, the generating function of the sought answer is obtained by multiplying it by \(F_N\), the number of \(m\)-edge walks from vertex \(1\) to vertex \(N\) without visiting vertex \(1\) halfway:

\[\frac{F_N(x)}{1 - x G_N(x)}.\]

\(G_N(x)\) can be computed by maintaining additional parameters in the matrix product while computing \(F_N(x)\), as described in the following equation:

\[ \left( \begin{array}{c} F_{n+1} \\ F_{n} \\ G_{n+1} \end{array} \right) = \left( \begin{array}{ccc} P_n Q_n & P_n R_n & 0\\ 1 & 0 & 0 \\ D_n P_n Q_n & D_n P_n R_n & 1\\ \end{array} \right) \left( \begin{array}{c} F_n \\ F_{n-1} \\ G_n \end{array} \right) \]

Therefore, \(F_N(x)\) and \(G_N(x)\) has been computed in a total of \(\mathrm{O}(N \log^2 N)\) time. Also, one can find \(\lbrack x^K \rbrack \frac{F_N(x)}{1 - x G_N(x)}\) in a total of \(\mathrm{O}(K \log^2 K)\) time with divide-and-conquer, or \(\mathrm{O}(K \log K)\) time with the method introduced at the end of the editorial of ABC260Ex.
Hence, the problem has been solved in a total of \(\mathrm{O}(N \log^2 N + K \log K)\) time, which is fast enough. (While the term dependent on \(N\) has a constant coefficient \(27\), the one on \(K\) does not have such a coefficient, we think that \(\mathrm{O}(N \log^2 N + K \log^2 K)\) is still fast enough.)