Consider the problem where the number of white stones on each edge is specified. That is, we will solve for each \(k=0,1,\ldots,D+1\) the following problem: how many ways are there to place stones so that every edge has exactly \(k\) white stones?

Consider the following process: first, place a stone on a vertex. Then, repeatedly decide the next \(D\) stones to place. This can be boiled down to DP (Dynamic Programming) as follows:

\({\rm DP}_c[i][j]=\text{The number of ways to place stones to the first }i\text{ edges, so that the colors of first and the last stone are }c \text{ and }j \text{, respecitvely}\)

The desired answer equals \({\rm DP}_{\rm white}[N][{\rm white}]+{\rm DP}_{\rm black}[N][{\rm black}]\).
The transition of the DP is independent of \(i\), so we can use fast matrix exponent trick to find \({\rm DP}_{*}[N][*]\) in an \(O(\log N)\) time.

Therefore, the problem has been solved in a total of \(O(D\log N)\) time.

Sample code (C++)
(* while this code runs in \(O(D\log N+D\log {\rm MOD})\) time, it can be reduced to \(O(D\log N)\) with a proper implementation)