Problem Statement

You are given a length-$N$ integer sequence $A=(A _ 1,A _ 2,\ldots,A _ N)$.

There are $2 ^ N$ (not necessarily contiguous) subsequences of $A$. Find how many subsequences $(A _ {i _ 1},A _ {i _ 2},\ldots,A _ {i _ k})\ (1\le i _ 1\lt i _ 2\lt\cdots\lt i _ k\le N)$ satisfy both of the following two conditions:

• The selected elements are not adjacent in $A$. That is, $1+i _ j\ne i _ {j+1}$ holds for all $1\le j\lt k$.
• The sum is a multiple of $M$. That is, $\displaystyle\sum _ {j=1} ^ kA _ {i _ j}\equiv0\pmod M$.

Even if two subsequences are equal as integer sequences, they are counted separately if the positions from which they are taken are different.

Constraints

• $1\le N\le60$
• $1\le M\le10 ^ 9$
• $0\le A _ i\lt M$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A _ 1 A _ 2 \ldots A _ N

Output

Print the answer.