042 - Multiple of 9(★4)
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点:4 点
問題文
0 以外の数字のみを使って書ける正の整数 X のうち、 以下の条件をともに満たすものが何通りあるかを求め、 10^9 + 7 で割った余りを出力してください。
- X は 9 の倍数
- X を 10 進法で表したときの各桁の数字の和は K
制約
- 1 \leq K \leq 100000
- K は整数
入力
入力は以下の形式で標準入力から与えられます。
K
出力
答えを 1 行に出力してください。
入力例 1
1
出力例 1
0
0 以外の数字のみを使って書ける正の整数のうち、各桁の数字の和が 1 になるのは 1 のみです。 ここで、1 は 9 の倍数ではないため、条件を満たす整数 X はありません。よって、答えは 0 通りになります。
入力例 2
234
出力例 2
757186539
10^9 + 7 で割った余りを出力することに注意してください。