思路解析

首先我们注意到：

• 数字中不允许有 $0$，每一位只能是 $1$ 到 $9$，这是一个类似整数划分的组合方案问题。
• 问题等价于：求将整数 $s$ 划分为若干个（顺序重要）正整数，每个数在 $1$ 到 $9$ 之间的方案数。
• 如果用 $f[s]$ 表示数位和为 $s$ 的香香正整数个数，那么可得递推式：

题目内容

给定一个非负整数 $s$ ，定义一个 香香的正整数 为由数字 $(1-9)$ 组成正整数，其数位之和恰好等于 $s$ 。请计算所有香香的正整数的总数，并对 $(10^9+7)$ 取模。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≦ T≦ 10^4)$ 表示测试用例数；

接下来 $T$ 行，每行输入一个整数 $s(0 ≦s≦2×10^5)$ 。

输出描述

对于每组测试数据，输出一个整数，表示所有香香的正整数的数量对 $(10^9+7)$ 取模的结果。

样例1

输入

3
0
1
3

输出

0
1
4

说明

在这个样例中，$s=3$ 时合法正整数有：

• "$3$”；

• "$12$"；

• “$21$”；

• "$111$"。共 $4$ 个。