$a_n$은 다음과 같이 재귀적으로 정의되는 수열입니다:$\quad a_1=1,\quad\displaystyle a_n=\biggl(\sum_{k=1}^{n-1}k\cdot a_k\biggr)\bmod n$.

수열 $a_n$의 첫 10개 항은 다음과 같습니다: 1,1,0,3,0,3,5,4,1,9.

다음 조건을 만족하는 쌍 (p,q)의 개수를 f(N,M)이라 합니다:

$$ \def\htmltext#1{\style{font-family:inherit;}{\text{#1}}} 1\le p\le q\le N \quad\htmltext{ 이고 }\quad\biggl(\sum_{i=p}^qa_i\biggr)\bmod M=0 $$

f(10,10)=4 이고, 네 쌍은 (3,3), (5,5), (7,9), (9,10) 입니다.

또한, f(10⁴,10³)=97158 입니다.

f(10¹²,10⁶) 값을 구하세요.