F - Not Adjacent 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB



配点 : 525 点

問題文

長さ 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 つの部分列を区別して数えることに注意してください。

制約

  • 1\le N\le60
  • 1\le M\le10 ^ 9
  • 0\le A _ i\lt M
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

答えを出力せよ。

入力例 1

7 6
3 1 4 1 5 3 2

出力例 1

6

以下の 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 を出力してください。

入力例 2

15 10
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

出力例 2

798

入力例 3

20 998244353
778718481 719092922 676292280 713825156 0 434453766 620370916 67922064 0 577696866 21516423 955580612 955580612 0 332156721 0 0 0 632133714 500614291

出力例 3

40

Score : 525 points

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.

Sample Input 1

7 6
3 1 4 1 5 3 2

Sample Output 1

6

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.

Sample Input 2

15 10
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

Sample Output 2

798

Sample Input 3

20 998244353
778718481 719092922 676292280 713825156 0 434453766 620370916 67922064 0 577696866 21516423 955580612 955580612 0 332156721 0 0 0 632133714 500614291

Sample Output 3

40