AT_abc427_f [ABC427F] Not Adjacent

長さ $ N $ の整数列 $ A=(A _ 1,A _ 2,\ldots,A _ N) $ が与えられます。 $ A $ の（連続するとは限らない）部分列は $ 2 ^ N $ 通りあります。 部分列 $ (A _ {i _ 1},A _ {i _ 2},\ldots,A _ {i _ k})\ (1\le i _ 1\lt i _ 2\lt\cdots\lt i _ k\le N) $ であって、次の $ 2 $ つの条件の両方を満たすものがいくつあるか求めてください。 - 選ばれた要素は $ A $ において隣接しない。つまり、すべての $ 1\le j\lt k $ に対して $ 1+i _ j\ne i _ {j+1} $ が成り立つ。 - 総和が $ M $ の倍数である。つまり、 $ \displaystyle\sum _ {j=1} ^ kA _ {i _ j}\equiv0\pmod M $ $ 2 $ つの部分列が整数列として等しくても、取り出す位置が異なるならそれら $ 2 $ つの部分列を区別して数えることに注意してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A _ 1 $ $ A _ 2 $ $ \ldots $ $ A _ N $

答えを出力せよ。

### Sample Explanation 1 以下の $ 6 $ つの部分列が条件を満たします。 - $ ()=() $ - $ (A _ 1,A _ 3,A _ 5)=(3,4,5) $ - $ (A _ 1,A _ 4,A _ 7)=(3,1,2) $ - $ (A _ 1,A _ 6)=(3,3) $ - $ (A _ 2,A _ 5)=(1,5) $ - $ (A _ 3,A _ 7)=(4,2) $ なので、`6` を出力してください。 ### Constraints - $ 1\le N\le60 $ - $ 1\le M\le10 ^ 9 $ - $ 0\le A _ i\lt M $ - 入力はすべて整数