Background

理论楼怎么这么高啊......

Description

你是一名省理论职专的信竞生，你每天需要爬楼才能到达位于高层的机房。

你为了节省时间，一步可以爬 $1\sim m$ 阶楼梯，如果整栋楼中一共有 $k$ 阶楼梯，那么我们把这栋楼的复杂度定义为你从底爬到第 $k$ 阶的不同的方案数。

你今天突然发现理论楼装修了，导致你不知道一共需要爬多少阶楼梯了。但是你找到了装修图，发现装修图上有个很长的数 $T$，这个数 $T$ 是每两层之间的楼梯阶数首尾相连所得到的数。

举个例子，如果理论楼有三层，且每两层之间的楼梯阶数分别是 $1$ 和 $2$，则你所看到的 $T$ 就应该是 $12$。

当然，你既不知道理论楼有几层，也不知道层与层之间有多少阶楼梯，所以你想要知道对于所有可能的情况，理论楼的复杂度之和是多少？

答案对 $704581223$ 取模。

• 两层楼之间的楼梯阶数允许有前导 $0$（也允许阶数等于 $0$，问就是理论楼构造奇特）。
• 你一步可以跨楼层上台阶（问就是你骨骼清奇）。

---

Constraints and Subtasks

• $1\le m\le 5$
• $T\lt 10^{601}$

另外，还有一些测试点满足特殊要求。

Subtask	分值	$T<$	特殊性质
$1$	$20\%$	$10^6$	无
$2$	$30 \%$	$10^{11}$
$3$	$10\%$	$10^{601}$	有
$4$	$40 \%$		无

特殊性质：保证 $m=1$。

Input

输入格式如下：

$\boxed{ \begin{aligned} & T & m \end{aligned} }$

Output

一行一个正整数，表示答案取模后的结果。

Samples

12 3

931

你一步可以上 $1\sim 3$ 阶楼梯。

由于 $T=12$，所以理论楼有两种构造：

• 楼有三层，两层楼之间的楼梯阶数分别是 $1$ 和 $2$，则一共有 $3$ 阶楼梯，共有 $4$ 种上楼方案。
• 楼有两层，这两层楼之间的楼梯阶数是 $12$，则一共有 $12$ 阶楼梯，共有 $927$ 种上楼方案。

则最后答案为 $4+927=931$。

Notes

为了避免题意发生歧义，出题组在这里再举一个例子：

如果 $T=1000$，则理论楼会有如下构造：

• 楼有五层，两层楼之间的楼梯阶数分别是 $1,0,0,0$，则一共有 $1$ 阶楼梯。
• 楼有四层，两层楼之间的楼梯阶数分别是 $1,0,00$，则一共有 $1$ 阶楼梯。
• 楼有四层，两层楼之间的楼梯阶数分别是 $1,00,0$，则一共有 $1$ 阶楼梯。
• 楼有四层，两层楼之间的楼梯阶数分别是 $10,0,0$，则一共有 $10$ 阶楼梯。
• 楼有三层，两层楼之间的楼梯阶数分别是 $1,000$，则一共有 $1$ 阶楼梯。
• 楼有三层，两层楼之间的楼梯阶数分别是 $10,00$，则一共有 $10$ 阶楼梯。
• 楼有三层，两层楼之间的楼梯阶数分别是 $100,0$，则一共有 $100$ 阶楼梯。
• 楼有两层，两层楼之间的楼梯阶数是 $1000$，则一共有 $1000$ 阶楼梯。