問題文

0 以外の数字のみを使って書ける正の整数 X のうち、 以下の条件をともに満たすものが何通りあるかを求め、 10^9 + 7 で割った余りを出力してください。

• X は 9 の倍数
• X を 10 進法で表したときの各桁の数字の和は K

制約

• 1 \leq K \leq 100000
• K は整数

入力例 1

1

出力例 1

0

0 以外の数字のみを使って書ける正の整数のうち、各桁の数字の和が 1 になるのは 1 のみです。 ここで、1 は 9 の倍数ではないため、条件を満たす整数 X はありません。よって、答えは 0 通りになります。

入力例 2

234

出力例 2

757186539

10^9 + 7 で割った余りを出力することに注意してください。