515 : 不協和数

素数 $p$ を法としたときの $n$ の逆数を $d(p,n,0)$ としよう。つまり $n \times d(p,n,0) = 1 \bmod p$ と定義される。 $k \geq 1$ となるような k に対し、$\displaystyle d(p,n,k) = \sum_{i=1}^n d(p,i,k-1)$ としよう。 $a \leq p < a + b$ となるような全ての素数 $p$ に対し $D(a,b,k) = \sum (d(p,p-1,k) \bmod p)$ としよう。

次のように与えられている：

• $D(101,1,10) = 45$

• $D(10^3,10^2,10^2) = 8334$

• $D(10^6,10^3, 10^3) = 38162302$

$D(10^9,10^5,10^5)$ を求めよ。