Для натурального числа k определим d(k), как сумму цифр обычной десятичной записи числа k. То есть, d(42) = 4+2 = 6.

Для натурального числа n, определим S(n) как количество натуральных чисел k < 10ⁿ, обладающих следующими свойствами:

• k делится на 23 без остатка;
• d(k) = 23.

Дано, что S(9) = 263626 и S(42) = 6377168878570056.

Найдите S(11¹²) и введите ответ по mod 10⁹.