小 Z 最近发现了一种非常有趣的数，他将这种数称之为 Sam 数。
Sam 数具有以下特征：相邻两位的数字之差不超过 。
小 Z 还将 Sam 数按位数进行了分类，他将一个 位 Sam 数称之为 阶 Sam 数。
但不幸的是小 Z 发现他数不清第 阶的 Sam 数一共有多少个，这个时候机智的他想到了向你求助。
答案对 取模。
输入共一行一个整数 ，含义见题面。
一行一个整数 ，表示 阶的 Sam 数的个数。
4
867
对于 的数据，。
