题目描述

译自 ROI Regional 2023 Day2 T2. Красивые последовательности

给定一个集合 $A$，其中包含从 $1$ 到 $8$ 的不同整数。

考虑一个由 $n$ 个整数组成的序列 $\left[a_{1}, a_{2}, \ldots, a_{n}\right]$，每个整数都从集合 $A$ 中选取。如果对于任意一个数 $x$，序列中所有等于 $x$ 的元素之间的距离至少为 $x$，我们称这个序列是美丽的。换句话说，对于任意一个数 $x$ 和任意两个索引 $1 \leq i < j \leq n$，如果 $a_{i}=a_{j}=x$，则必须满足 $j-i \geq x$。

需要计算给定长度 $n$ 和集合 $A$ 的美丽序列的数量，并输出这个数量除以 $10^{9}+7$ 的余数。

输入格式

第一行输入包含两个整数 $n$ 和 $m$ $(1 \leq n \leq 100, 1 \leq m \leq 8)$，分别表示序列的长度和集合 $A$ 的元素数量。

输出格式

输出一个整数，表示美丽序列的数量除以 $10^{9}+7$ 的余数。

3 2
1 2

5

在这个样例中，美丽的序列有 $[1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,1,2]$。

序列 $[2,2,2], [1,2,2], [2,2,1]$ 不是美丽的，因为每个序列中都有两个值为 $2$ 的元素，它们之间的距离为 $1$。

数据范围与提示

详细子任务附加限制及分值如下表所示。