### 问题描述 在一个清晨，一位行者在田野上漫步，他发现晨露在阳光下熠熠生辉，于是他决定用一种独特的方式来记录这些露珠。他决定给每滴露珠编号，并且为它们制定了一个生成序列 `$\mathrm{a}_{\mathrm{n}}$`。行者按照以下方式递归定义这个序列：$a_1=1$，对于所有 $n>1$，有 $a_n=\left(\sum_{k=1}^{n-1} k \cdot a_k\right) \bmod n$。 行者记录的露珠序列很奇特，他注意到在某些连续的区间内，露珠编号的总和能被特定的数 $M$ 整除。他定义 $f(N, M)$ 为在前 $N$ 滴露珠中，满足从第 $p$ 滴到第 $q$ 滴的序列总和能整除 $M$ 的 $(p, q)$ 数对的数量。 行者在编号到第 $10$ 滴时，发现了 $4$ 对这样的数对。他又知道，当序列延伸到第 $10^4$ 滴露珠时，能整除 $10^3$ 的数对有 $97158$ 对。现在，行者希望你能帮他计算出，当序列延伸到第 $10^{12}$ 滴露珠时，能整除 $10^6$ 的 $(p, q)$ 数对总数。 ### 输入格式 无。 ### 输出格式 输出一个整数，表示 $f\left(10^{12}, 10^6\right)$ 的值。 ### 说明 **本题为填空题，只需要算出结果后，在代码中使用输出语句将结果输出即可。**