1249 : 三数之和

Description

【题目背景】

小艾在计算理论课上了解到，三数之和（3SUM）问题在某种意义上是一个惊人困难的问题。当值域在 \(n^2\) 级别时，目前依然没有发现比朴素算法快很多的做法。

TA 想知道，如果值域大到一个惊人的程度时，你能够做到多好呢？

【题目描述】

给定 \(n\) 个整数 \(a_1,\dots,a_n\) 和一个模数 \(M\)，保证 \(M = 10^K-1\)，由输入一个正整数 \(K\) 的方式给出。

请你找出有多少对 \((i, j, k)\)（\(1\leq i\leq j\leq k\leq N\)），满足 \(a_i + a_j + a_k \equiv 0 \pmod M\)。

Input

第一行输入两个正整数 \(n,K\)（\(1\leq n\leq 500\)，\(1\leq K\leq 2\times 10^4\)）。

接下来 \(n\) 行每行输入一个整数，第 \(i\) 个数为 \(a_i\)。

保证输入的每个 \(a_i\) 非负，且不超过 \(2\times 10^4\) 位。

Output

一行输出一个数，表示满足要求的 \((i,j,k)\) 的方案数。

Sample

4 1
0
1
10
17

3

Hint

【样例解释 #0】

三组方案是：

• \(0 + 0 + 0 \equiv 0 \pmod 9\)，
• \(0 + 1 + 17 \equiv 0 \pmod 9\)，
• \(0 + 10 + 17 \equiv 0 \pmod 9\)。

Source

Author

THU