MianKing and GreenKing are playing a game. Initially there are integers on the blackboard and a set .

MianKing and GreenKing take turns to operate and MianKing will operate first.

In each operation the player can choose an integer on the blackboard which is not a Bad Number(Will be defined below), then choose an integer in . 

The player should guaranteed that and if there is no y that satisfies in the set , the player cannot choose this . 

Then the player will replace with on the blackboard.

If a player cannot do any operations, the player loses this game.

GreenKing is a bad woman, she wants to choose a subset of size from to ensure that she can win the game(Assuming that both players are smart enough). Now you need to help her calculate how many subset of satisfies the above conditions.

The answer may be very large, so you only need to output answer mod .

We call a number is a Bad Number, if and only if it has an even number of 1 in the binary representation.

For example, are all Bad Numbers and are not Bad Numbers.

The first line has three integers 

The second line has  distinct integers denotes the set .

Output the answer mod .

5 2 1
2

6

1000 100 10
1 2 3 4 5 6 7 8 10 11

896262428