← 返回题目列表

AtCoder · typical90_ap

042. 9的倍数(★4)

中文机器翻译题面 查看原题

配点: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 后的余数。