This Christmas Anina and her friends have decided to make some Christmas trees to decorate her town. A Christmas Tree can be with some nodes and edges. They have managed infinite amount of nodes of each type and infinite amount of edges. Each type of node has a beauty value .The process of building a tree is describing below.
Choose any type of node as a root and hang it somewhere.
After hanging the first node they pick any type of node and connect it with any node which is already in the structure.
But Anina have some conditions to make a Christmas Tree x-beautiful. A Christmas Tree must be built with n distinct type of nodes and for each level the xor of all node's beauty value must be x. We have illustrated these conditions in the above picture. So How many different Christmas Tree Anina’s team can build with n different type of nodes and each of tree will be x-beautiful ?
Note
Two trees will be considered different if they have different structure or different labeling. See the mentioned figure for better understanding.
Also note that orientation of child having same parent does not consider two different trees.
The first line of each test case contains a two integers — different type of nodes Anina has and the beauty factor .
Next line contain integers. -th of them denotes the beauty value of the node .
Print an integer denoting the number of different Christmas Trees Anina’s team can make. The answer can be very large. Print the answer modulo.
Input | Output |
---|---|
3 1 1 2 3 | 1 |