정수 a, b, c에 대하여, 미친 함수 F(n)를 다음과 같이 정의합니다:
F(n) = n - c, n > b 일 때,
F(n) = F(a + F(a + F(a + F(a + n)))), n ≤ b 일 때.

또한, $S(a, b, c) = \sum \limits_{n = 0}^{b} {F(n)}$로 정의합니다.

예를 들어, 만일 a = 50, b = 2000, c = 40 이라면, F(0) = 3240 이고 F(2000) = 2040 입니다.
또한, S(50, 2000, 40) = 5204240 입니다.

S(21⁷, 7²¹, 12⁷)의 마지막 9자리수를 답으로 제출하세요.