AT_abc427_f [ABC427F] Not Adjacent

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.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ A _ 1 $ $ A _ 2 $ $ \ldots $ $ A _ N $

Print the answer.

### Sample Explanation 1 The following six subsequences satisfy the conditions: - $ ()=() $ - $ (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) $ Thus, print `6`. ### Constraints - $ 1\le N\le60 $ - $ 1\le M\le10 ^ 9 $ - $ 0\le A _ i\lt M $ - All input values are integers.