Consider the case the graph is a tree. For a fixed set of vertices with odd degrees, there are \(0\) spanning subgraphs if the size of that set is odd, and \(1\) spanning subgraph otherwise. (Proof: when \(N = 1\), we have \(1\) subgraph when there are \(0\) vertices with odd degrees and \(0\) subgraphs when there is \(1\) such vertex. When \(N > 1\), if we take some leaf and choose whether we keep the edge incident to that leaf according to the desired degree of that leaf, the problem is reduced to the case with \(N - 1\) vertices. Here, the reduction does not change the parity of the size of the set of vertices with odd degrees, so the answer is still \(1\) when there is an even number of vertices with odd degrees and \(0\) if there is an odd number of such vertices.) Thus, the answer is \(0\) if \(K\) is odd and \(_NC_K\) if \(K\) is even.

Consider the case the graph is connected. If we take some spanning tree of the graph and arbitrarily choose whether we keep each of the edges not contained in that spanning tree, the problem is reduced to the case the graph is a tree. Thus, the answer is \(0\) if \(K\) is odd and \(2^{M-N+1} \times _NC_K \) if \(K\) is even.

For a disconnected graph, we separately solve the problem for each connected component and combine the results with dynamic programming or multiplication of polynomials to find the final answer.

The complexity of this solution is \(O(N^2)\) or \(O(N \log^2 N)\).