In this problem, why do we calculate factorial for 10^9 + 6 instead of the normal 10^9+7
Read this whole thread. Look at this for the proof of the special case when p is a prime.