The problem can be transformed to a more formal one: how many vertices will a trie (data structure) contain, if we add all possible strings of length ~2N~ with ~N~ zeroes and ~N~ ones to this trie.

First, it is obvious that the upper half of this tree will be a full binary tree. Let's take a look at ~N = 3~:

• level ~0~: ~1~ vertex
• level ~1~: ~2~ vertices
• level ~2~: ~4~ vertices
• level ~3~: ~8~ vertices.

Starting from level ~N+1~, not every vertex will have two children. Vertices that will have two children are those that have less than ~N~ zeroes and less than ~N~ ones on the path to the root.

So, here is how we calculate how many vertices there will be on level ~i+1~:

• Let's define ~S_i~ as the number of vertices on level ~i~ which have less than two children
• If ~V_i~ is the number of vertices on level ~i~, then ~V_{i+1} = 2V_i-S_i~
• ~S_i~ can be calculated easily using binomial coefficients: ~S_i = 2 \binom i N~

Everything else in the task are implementation techniques. We need to calculate some modular multiplicative inverses, which can be done in logarithmic time using exponentiation by squaring. We can calculate binomial coefficients efficiently, by using the values calculated for the previous level.

Time complexity: ~\mathcal O(N \log(10^9+7))~