* 这是这个问题的 hard 版本。它们的区别在于 $n$ 的数据范围。 给你一个长度为 $n$ 的数组 $a$ 和一个正整数 $k$，你需要找到有多少个子数组满足它们的区间和是 $k$ 的倍数。 即：有多少个二元组 $(l,r)$ ，满足 $1\le l \le r \le n$ 且 $\sum \limits _{i=l} ^ r a_i$ $mod\ k =0$ 。

第一行两个正整数 $n,k \ (1\le n \le 10^5, \ 1 \le k \le 10^9)$。 第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$ ($0\le a_i\le 10^9$)。

对于每组测试样例输出一行，代表答案。