题目描述

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

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

考虑一个由 ( n ) 个整数组成的序列 $( [a_1, a_2, \ldots, a_n] )$，每个整数都从集合 ( 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 ) 的元素数量。

第二行输入 ( m ) 个不同的整数，代表集合 ( A ) 中的元素（元素取值范围为 $( 1 \leq A_i \leq 8 )$）。

输出格式

输出一个整数，表示美丽序列的数量除以 $( 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 )，不满足 $( j - i \geq 2 )$ 的要求。

数据范围与提示

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