Let $a_n$ be a sequence recursively defined by:$a_1=1,{\displaystyle a_n=(\sum _{k=1}^{n-1}k\cdot a_k)modn}$.

So the first $10$ elements of $a_n$ are: $1,1,0,3,0,3,5,4,1,9$.

Let $f(N,M)$ represent the number of pairs $(p,q)$ such that:

$$1\le p\le q\le N\text{and}(\sum _{i=p}^q{a}_i)modM=0$$

It can be seen that $f(10,10)=4$ with the pairs $(3,3)$, $(5,5)$, $(7,9)$ and $(9,10)$.

You are also given that $f({10}^4,{10}^3)=97158$.

Find $f({10}^{12},{10}^6)$.