典型042

問題文

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

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

制約

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

入力

入力は以下の形式で標準入力から与えられます。

K

出力

答えを $1$ 行に出力してください。

入出力例

1

0

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

234

600805229

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