326 : モジュロ総和

$a\_n$を以下の式によって再帰的に定義される数列とする。

$a_1 = 1$ $\displaystyle a_n = \left ( \sum_{k=1}^{n-1} k \cdot a_k \right ) \mod n$

従って、$a_n$の最初の10個の要素は1,1,0,3,0,3,5,4,1,9となる。

下記を満たす対$(p,q)$の個数を$f(N,M)$で表す。

$1 \leq p \leq q \leq N$かつ$\displaystyle \left ( \sum_{i=p}^q a_i \right ) \mod M = 0$

$f(10,10)=4$であることが分かる。（(3,3), (5,5), (7,9), (9,10) の４個）

また$f(10^4,10^3)=97158$である。

$f(10^{12},10^6)$を求めよ。