Halting Assembly

If we compress all blocks of ‘N’ then for the assembly to halt, the program jumps from one block to another (never repeating) and goes to last block. If the program goes to a block of length k then last jump had k possible targets, so for this sequence the count of assignments is product of block lengths * last block length * (count of N)^(count of remaining J).

so if block lengths are $S =$$b_1, \\cdots b_k$(first block is ignored) then answer is

$\sum \limits_{T \subseteq S, b_k \in T} (|T|-1)! \cdot \left( \prod \limits_{b_i \in T} b_i \right) {cnt_N}^{cnt_J-|T|+1}$

If we consider the polynomial $(1+b_1x)(1+b_2x)\cdots(1+b_{k-1}x)b_k$ then coefficient of $x^i$ in this polynomial is exactly the $\sum \limits_{\substack{|T| -1 = i \\ T \subseteq S , b_k \in T}} \left( \prod \limits_{b_i \in T} b_i \right)$. We can compute this polynomial in time $O(n \log^2 n)$ with NTT and divide and conquer. Then by multiplying appropriate factorial and powers, the answer can be computed.