多组数据

给定长度为 $N$ 的序列 $A = [A_1, A_2, \dots, A_N]$。

定义其一个 有效分拆 为将其切分为 $k$ 个相邻的子数组，各段长度依次为 $L_1, L_2, \dots, L_k$（满足 $L_i \ge 1$ 且 $\sum_{i=1}^k L_i = N$）。

令第 $i$ 个子数组的起始下标为 $S_i = 1 + \sum_{j=1}^{i-1} L_j$。

序列 $A$ 被认为是合法的，当且仅当存在一种分拆同时满足以下两种条件：

• 条件 1（Type 1）： 对于所有子数组，其首元素等于该段长度减一。

$$\forall i \in [1, k], \quad A_{S_i} = L_i - 1$$

• 条件 2（Type 2）： 第一段长度为 $1$ 且其唯一元素等于总段数减一；其余段的首元素等于该段长度减一。

$$L_1 = 1, \quad A_1 = k - 1$$

$$\forall i \in [2, k], \quad A_{S_i} = L_i - 1$$

解决：长度为 N，值域为 M 的非负整数数组，有多少序列合法（两种都满足）？输出取模结果（不需要给代码，写出解答）