While doing some other things, I've come across the following problem:

There is a grid of **R** rows and **C** columns. Count the number of ways to colour **B** of these squares so that **every column has an even number of coloured squares**. Output the answer **modulo 10^9+7**. You may assume **B is even** and **R >= B**.

The best I've been able to come up with is O(RB^2 + CB). The approach is a simple DP where the state is [Which column you are colouring, How many squares left to colour] and the recursion involves picking how many squares you'd like to colour in this column.

# Best How To :

Here is a way to look at this using generating functions.

The generating function (polynomial) for the number of ways to color a column with an even number of colored squares is

```
a(x) = 1 + (R choose 2)x^2 + (R choose 4)x^4 + ...
```

You are trying to compute the coefficient of x^B in a(x)^C. Your method is to compute the terms up to x^B of a(x), a(x)^2, a(x)^3, ... basically by multiplying out the first few terms at each step.

It should be an improvement to compute a(x)^C by successive squaring: Compute a(x)^2^k for the values of k up to log_2 C, then multiply together those corresponding to 1s in the binary expansion of C. For example, if C=100 = 1100100_2, then compute a(x), a(x)^2, a(x)^4, ... a(x)^64 and then

```
a(x)^100 = a(x)^64 * a(x)^32 * a(x)^4.
```

This uses a little more memory, but if that is an issue you can compute a^1, a^2, a^3, a^6, a^12, a^24, a^25, a^50, a^100 so that at each step you square or multiply by a to compute a^(prefix of 1100100_2).

You may be able to better using the specific form a(x) = ((1+x)^R + (1-x)^R)/2, say by applying the binomial theorem, but I haven't gotten this method to be faster.