Huge Grid (Hard Version)

**This is the hard version of the problem. Here your task is to count the number of different paths that achieve the minimum possible path sum.** Given a binary sequence $A$ of length $N$, we construct an $N \times N$ matrix $B$ as follows: - If $i \leq j$, then $B_{i,j} = \sum_{k=i}^j A_k$. - Otherwise, $B_{i,j} = B_{j,i}$. Define a path from $(1,1)$ to $(N, N)$ as a sequence of pairs: $$ P =