q-Factorial

For n a positive integer, the q-factorial is defined by $$\begin{array}{c}[n{]}_q!=\prod _{k=1}^n[k{]}_q=\prod _{k=1}^n\sum _{i=0}^{k-1}{q}^i\\ =1(1+q)(1+q+q^2)\cdots (1+q+\cdots +q^{n-1})\end{array}$$
Let $S(n,q)=[n{]}_q!$. You are given $S(5,2)=9765$, $S(100,7)mod1000000000039=850054509459$.

Find $S(123456789876,7)mod1000000000039$.