#MX103. 整除 2

整除 2

题目描述

给定一个长度为 nn 的数列 aa,你可以操作任意次,每次选择数列中相邻的两个元素 u,vu,v,计算 w=u+vw=u+v,并将 ww 插入 u,vu,v 之间,再把 u,vu,v 删除。

求出最终数列中最多能有多少项能被 pp 整除。

输入格式

第一行两个整数 n,pn,p。

第二行共 nn 个数,表示数列 aa。

输出格式

仅一行一个数,表示答案。

样例 1 输入

5 3
1 2 3 1 2

样例 1 输出

3

样例 1 说明

两次均选定 u=1,v=2u=1,v=2,操作后,数列 a=[3,3,3]a=[3,3,3]。

数据规模与约定

  • 数据点 11:p=2p=2。
  • 数据点 2∼32\sim3:n≤10n\le 10。
  • 数据点 4∼64\sim6:n≤2×103n\le 2\times10^3。
  • 数据点 7∼107\sim10:无特殊限制。

对于 100%100\% 的数据,有 1≤n,p,ai≤1061\le n,p,a_i\le 10^6。