k가 자연수일 때, d(k)를 k의 십진법 표현시 모든 자릿수의 합으로 정의합니다. 따라서 d(42) = 4+2 = 6입니다.

n이 자연수일 때, S(n)을 다음 속성을 가진 자연수 k < 10ⁿ의 개수로 정의합니다:

• k는 23으로 나뉘고
• d(k) = 23입니다.

S(11¹²)을 구하고 10⁹으로 나눈 나머지를 답으로 제출하세요.