农夫约翰（Farmer John）有 （）头奶牛，他试图让它们依靠自身的懒惰性来排序一个长度为 的非负整数数组 。他有很多沉重的箱子，所以他把奶牛们排成一列，其中奶牛 在奶牛 的后面，并给奶牛 分配 （）个箱子。
奶牛们天生就很懒，所以它们总是想把工作推给别人。从奶牛 到 ，每头奶牛依次看向它后面的奶牛。如果奶牛 的箱子严格多于奶牛 ，奶牛 会认为这“不公平”，并把它的一个箱子交给奶牛 。这个过程会一直重复，直到每头奶牛都满意为止。
然后，农夫约翰会记下每头奶牛 持有的箱子数量 ，并用这些值创建一个数组 。如果 （即 排序后的结果），那么农夫约翰就会很高兴。不幸的是，农夫约翰忘记了 中除了 （）个值之外的所有值。幸运的是，这些记住的值包括了他打算给第一头和最后一头奶牛的箱子数量。FJ 记住的每个值都以 的形式给出，表示 （，）。请确定有多少种不同的方法可以填补缺失的值，使得他在奶牛们完成懒惰排序后会感到高兴，结果对 取模。
第一行包含两个空格分隔的整数 和 ，分别代表奶牛的数量和查询（记住的值）的数量。
接下来的 行，每行包含两个空格分隔的整数 ，表示奶牛 最初持有 个箱子。保证 ，，并且 （奶牛的编号是严格递增的）。
输出可以分配 值的方法数量，使得农夫约翰在奶牛执行懒惰排序后感到高兴，结果对 取模。保证至少存在一种有效的分配方案。
3 2 1 3 3 2
2
6 3 1 1 3 3 6 5
89
在这个例子中，FJ 记住了数组两端的值。数组 和 是有效的数组，它们会在懒惰排序结束时让 FJ 高兴。