典型042

問題文


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

  • の倍数
  • 進法で表したときの各桁の数字の和は

制約


  • は整数

入力


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

K

出力


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

入出力例


入力例1
1
出力例1
0

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

入力例2
234
出力例2
600805229

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

Submit


Go (1.14)