解题思路

余数分组

1. 求余数：把每个价格取模 $m$，记余数为 $r=a_i\bmod m$。
2. 统计频次：用数组 cnt[r] 记录余数 $r$ 出现的次数，大小为 $m$。

配对规则

• 若两件商品余数分别为 $r$ 与 $m-r$（$1\le r\ < m$），则 $r+(m-r)\equiv 0 \pmod m$。

题目内容

多多正在参加一个特殊的满减活动,有几个名不相同的商品，每个商品的价格是$a_i$。活动规则是——若挑选的两个商品的价格总和是$m$的倍数的话，可以免费带走这两个商品，由于多多最多只能带两个商品，请问多多有多少种组合方式免费带两个商品。

输入描述

第一行输入两个数字$n$和$m$。

接下来输入$n$个商品的价格$a_i$，$a_i$为整数。

$1≤n≤200000,1≤m < 200000,1 ≤ a_i ≤ 1000000000$

输出描述

输出一个数字，表示多多鸡能免费带走两个商品的方式数量。

最终结果对$998244353$取模

样例1

输入

2 4
1 3

输出

1 

说明

多多只有$1$种方式免费拿走两件商品。

第$1$件商品和第$2$件商品

样例2

输入

5 2
1 2 3 4 5

输出

4

说明

多多有$4$种方式带走两件商品

第$1$件商品和第$3$件商品

第$2$件商品和第$4$件商品

第$1$件商品和第$5$件商品

第$3$件商品和第$5$件商品