# Problem Link:

# Difficulty:

Simple

# Pre-requisites:

Simple Math.

# Problem:

There are **N** cards, each having one of 1000 colors. Little Elephant (lets abbreviate him LE) and Big Hippo (similarly, BH) play a game. LE chooses some subset of cards and then they play a game, consisting of 1000 rounds. In round *k*, if LE has “**a**” cards of color *k*, and BH has “**b**” cards of color *k*, then their scores are updated as follows: if **a** > **b**, then LE scores |a-b| points, else BH scores |a-b| points. Find how many subsets of the **N** cards result in LE winning (if he chose that subset).

# Explanation:

Make a slightly modified game, in which each person in round *k*, scores the number of cards of that color that they have. Lets call this G2, and lets call the original G1. Now compare the scoring schemes.

```
G1 G2
a>b:
LE a-b a
BH 0 b
b>=a:
LE 0 a
BH b-a b
```

The thing to notice is, in both cases, the * point-difference is the same*. Thus, after all rounds, LE had more points than BH due to G1

**iff**LE had more points than BH due to G2.

But in G2, the total score is simply the total number of cards chosen. This gives us,

* LE wins the game iff he chooses more cards than BH !* This is independent of which colors he chooses the cards from, it only depends on the total number.

The answer is thus simply Σ _{i=floor(N/2)+1}^{N} ^{N}C_{i}.

### Algorithm:

Precompute (^{A} C _{B} modulo 1E9+7) for all A, B <= 1000. Then, given **N**, take the sum from i = floor(N/2)+1 to N of the precomputed values ^{N}C_{i}.

Time Complexity: O(T * N).

One last observation. Using N choose i = N choose (N-i), we can get that the answer for odd N is 2^{N-1}, and for even N, it is 2^{N-1} - 1/2 * (N choose N/2). By precomputing N choose N/2, it seems that we have a O(1) per test-case algorithm. However, in all cases, we do need to take O(N) time for Input itself, so this isn’t really an improvement.

# Setter’s Solution:

Can be found here

# Tester’s Solution:

Can be found here