Пусть $\displaystyle S(n)=\sum\limits_{k=0}^{n}\binom{n}{k}k^n$.

Известно, что $S(10)=142469423360$.

Найдите $S(10^{18})$. В качестве ответа приведите остаток от деления полученного результата на $83^3 89^3 97^3$.