Number of $k$-cuts of grid graphs
Consider this variation: we want to find number of paths which goes from $(1,1)-&gt;(n-2,n)$ in $(n-2)\times n$ solid grid, this can be done in almost $2^{n(n-2)}$ possible ways. Then is simple to convert it to your case. Just go up one step, then go left $n$ steps, again up one step and then right $n$ steps. That path covers all of that $k$ edges, and these are just restricted versions, that means independent to $k$, the upperbound is big : $2^{O(n^2)}$.