Let's calculate the number of strings consisting of (, ) and X (( is Alice's win, ) is Bob's win and X is a draw) satisfying the conditions from the statement. Let $T(a, b, k)$ be the number of bracket sequences having $a$ opening brackets, $b$ closing brackets and $k$ occurences of (( and )) in total, such that on each prefix the balance is nonnegative. Afterwards, to get the answer from $T$, we have to insert X between all $k$ occurences of (( and )), and then to distribute the remaining $(N - A - B - k)$ Xs among the string which can be done with stars and bars, $\binom{N - (A + B + k) + (A + B)}{A + B}$ ways to be exact.

Now $T$ can be neatly obtained from generalized Narayana numbers. If we have a bracket sequence with $k$ occurences of (), then it has either $a + b - (2k - 1)$ or $a + b - 2k$ occurences of (( and )) depending on the last symbol in the sequence. In particular, if the last symbol is (, then there are $a + b - 2k$ occurences, and the number of such sequences is $N_{a - b - 1}(a - 1, k)$ since we can simply remove the last bracket and calculate the number of remaining strings. If the last symbol is ), there are $a + b - (2k - 1)$ occurences, and by exclusion principle the number of such sequences is $N_{a - b}(a, k) - N_{a - b - 1}(a - 1, k)$. Thus,

and

so all that's left is to enumerate $k$ in $\mathcal O(N)$ time. 61236174