409036: GYM103423 C Birthday Nim

It's your brother's birthday! Hooray!

You have decided to give him $$$N$$$ presents, each of which contains some number of coins. Present $$$1$$$ contains $$$a_1$$$ coins, present $$$2$$$ contains $$$a_2$$$ coins and so on...

Since both you and your brother are serious competitive programmers (and are skilled in the art of game theory), you have decided to invent a variant of the infamous nim game, called "Birthday Nim".

Birthday Nim is a two player game which requires $$$N$$$ stacks of coins, the $$$i$$$-th of which being $$$a_i$$$ coins tall. In one move, the current player can remove any amount of coins from multiple stacks, provided that they remove at least one coin overall. The two players take turns alternatively, starting with the birthday boy. Birthday Nim ends when all the stacks are empty.

Unfortunately, Birthday Nim can be quite a boring, long and uneventful game. For this reason in particular you have decided to find how many distinct Birthday Nim games last exactly $$$k$$$ turns. Since this number can be very large, you are also satisified with its remainder modulo $$$10^9 + 7$$$.

The first line of input contains two integers $$$N$$$ and $$$K$$$ - the number of presents, and the number of turns, respectively. The second line contains $$$N$$$ space separated integers, the amount of coins in each present ($$$0 \le a_i \le 10^5$$$).

Print one integer, the number of distinct Birthday Nim games that last exactly $$$k$$$ turns. Since this number can be very large, print its remainder modulo $$$10^9 + 7$$$.

• For all tests , $$$0 \le a_i \le 10^5$$$
• Subtask 1 (10 points): $$$N=1$$$, $$$1 \le K \le 10^5$$$;
• Subtask 2 (10 points): $$$N=2$$$, $$$1 \le K \le 500$$$, $$$a_i \le 500$$$;
• Subtask 3 (10 points): $$$N=2$$$, $$$1 \le K \le 5000$$$;
• Subtask 4 (20 points): $$$N=2$$$, $$$1 \le K \le 10^5$$$;
• Subtask 5 (15 points): $$$2 \lt N \le 500$$$, $$$1 \le K \le 500$$$;
• Subtask 6 (35 points): $$$500 \lt N \le 5000$$$, $$$1 \le K \le 5000$$$

2 2
2 3

10

2 50
69 420

362313492

The only possible games are the following :

• [2,3] => [2,0] => [0,0]
• [2,3] => [2,1] => [0,0]
• [2,3] => [2,2] => [0,0]
• [2,3] => [1,0] => [0,0]
• [2,3] => [1,1] => [0,0]
• [2,3] => [1,2] => [0,0]
• [2,3] => [1,3] => [0,0]
• [2,3] => [0,1] => [0,0]
• [2,3] => [0,2] => [0,0]
• [2,3] => [0,3] => [0,0]

Thus, there are 10 possible games that last 2 moves, so print 10 mod $$$10^9+7$$$ = 10.