对于正整数 $k$，将 $d(k)$ 定义为其通常十进制表示形式的 $k$ 的数字之和。 因此 $d(42)=4+2=6$。

对于正整数 $n$，将 $S(n)$ 定义为具有以下属性的正整数 $k<{10}^n$ 的数量：

• $k$ 可以被 $23$ 整除并且
• $d(k)=23$。

已知 $S(9)=263626$ 和 $S(42)=6377168878570056$。

求 $S({11}^{12})$ 并给出答案 mod ${10}^9$。