이항 계수 $\displaystyle{\binom{10^{18}}{10^9}}$는 무려 90억($9\times 10^9$)자리가 넘는 수입니다.

$M(n,k,m)$은 이항 계수 $\displaystyle{\binom{n}{k}}$를 $m$으로 나눈 나머지를 나타냅니다.

$1000\lt p\lt q\lt r\lt 5000$ 이고 $p$,$q$,$r$이 소수일 때, $\displaystyle{\sum M(10^{18},10^9,p\cdot q\cdot r)}$ 값을 계산하세요.