## A huge binomial coefficient

### Problem 365

Published on Saturday, 31st December 2011, 04:00 pm; Solved by 756; Difficulty rating: 40%
The binomial coefficient C(10^{18},10^{9}) is a number with more than 9 billion (9×10^{9}) digits.

Let M(n,k,m) denote the binomial coefficient C(n,k) modulo m.

Calculate ∑M(10^{18},10^{9},p*q*r) for 1000<p<q<r<5000 and p,q,r prime.