{"problem":{"name":"[NICA #3] 数计组数","description":{"content":"称一个长度为 $n$ 的数组 $a$ 是“数计的”，当且仅当存在一种将其划分成若干个区间的方案，使得每个区间的最小值恰好等于区间长度，或者说存在 $0=x_1<x_2<x_3<\\cdots<x_m=n$，满足 $\\forall 1\\le i<m,\\min\\limits_{j=x_i+1}^{x_{i+1}}a_j=x_{i+1}-x_i$。 给定正整数集 $S$，询问有多少长度为 $n$ 的数组","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3902"},"statements":[{"statement_type":"Markdown","content":"称一个长度为 $n$ 的数组 $a$ 是“数计的”，当且仅当存在一种将其划分成若干个区间的方案，使得每个区间的最小值恰好等于区间长度，或者说存在 $0=x_1<x_2<x_3<\\cdots<x_m=n$，满足 $\\forall 1\\le i<m,\\min\\limits_{j=x_i+1}^{x_{i+1}}a_j=x_{i+1}-x_i$。\n\n给定正整数集 $S$，询问有多少长度为 $n$ 的数组 $a$ 满足 $a_i\\in S$ 且 $a$ 是“数计的”。答案对 $10^9+7$ 取模。\n\n## Input\n\n输入第一行两个整数 $n,m$，$n$ 表示数组的长度，$m$ 表示正整数集 $S$ 的大小。\n\n第二行包含 $m$ 个正整数 $b_1,b_2,\\dots,b_m$，表示正整数集 $S$ 中包含的元素。特别的，我们保证 $1\\le b_1< b_2<b_3<b_4<\\cdots<b_m\\le 10^6$。\n\n## Output\n\n输出仅包含一个整数，表示答案对 $10^9+7$ 取模后的结果。\n\n[samples]\n\n## Note\n\n#### 样例 1 解释\n\n只有两种可能的数组为“数计的”，分别是 $[1,1]$ 和 $[2,2]$。\n\n#### 数据范围\n\n对于所有数据，保证 $1\\le n\\le 2000$，$1\\le m\\le 100000$，$1\\le b_1< b_2<b_3<b_4<\\cdots<b_m\\le 10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3902","tags":["动态规划 DP","O2优化","排列组合"],"sample_group":[["2 2\n1 2","2"]],"created_at":"2026-03-03 11:09:25"}}