You and your friends are at the great Renaissance fair playing a very interesting game of cards. Shop-keeper gives you N cards and M bags. Each of the N cards has an integer written on it. Now...

You and your friends are at the great Renaissance fair playing a very interesting game of cards. Shop-keeper gives you N cards and M bags. Each of the N cards has an integer written on it. Now shop-keeper asks you to close your eyes and choose a subset of them. He then sums the numbers written on chosen cards, takes its absolute value and gives you those many coins. You win the game if you can divide these coins into M bags with each bag having equal share. As a first step to calculate the probability of winning, you would like to know the number of different subsets which will make you win. Note that all the cards are of different colour, so even if 2 cards have the same number written on it, they are still considered as different cards.

Develop a C++ code that outputs answer modulo 1000000009. Answer is the number of subsets that will ensure you win.

Input:

1

5 1

1 2 -1 4 5

9

Output:

4