Cuber QQ 得到了一台很奇怪的打字机。
这台打字机上，数字键 0 和数字键 1 坏掉了，因此 Cuber QQ 不能直接打出任何包含数字 0 或数字 1 的正整数。我们称一个正整数是 可输入数，当且仅当它的十进制表示中不含数字 0 和数字 1。例如，2, 9, 234, 8888 是可输入数；10, 101, 1203, 2024 不是可输入数。
现在 Cuber QQ 想得到一个目标正整数 。虽然不能直接输入 ，但他可以输入若干个可输入数，并用加号把它们相加。对于一个正整数 ，如果存在 个可输入数 ，满足：
则称 可以用 个可输入数表示。
由于 Cuber QQ 不想敲太多数字，他想知道：
- 表示 所需的最小 ；
- 在使用最小 的情况下，有多少种不同的有序表达式。
两个表达式被认为不同，当且仅当存在某个位置 ，使得第 个加数不同。例如，表达式 和表达式 被认为是两种不同的表达式。
由于方案数可能很大，你只需要输出方案数对 取模后的结果。
可以证明，对于本题输入中的每个 ，最小 一定不超过 。
