题目背景

基础算法思维赛的 $C$ 题。

小 C 的班主任想要给同学们找一种排队方式以方便参见升旗仪式等集体活动。但是小 C 的班主任很忙，没有时间，于是他就把这份工作推给了身为体育委员的小 P 。

题目描述

所谓排队就是排成一排。

每个同学都对自己在队伍中的位置有一定要求。对于第 $i$ 名同学，他要求自己的位置要在前 $a_i$ 个。小 P 希望满足尽量多的同学的要求。

但是小 P看小 C 不顺眼，所以她决定最后安排小 C 的位置并忽略小 C 的要求。现在小 P 想知道满足除小 C 以外的所有的同学的需求的方案数（小 C 的要求可以被满足也可以不被满足）。答案对 1000000007 取模。

输入格式

输入两行。

第一行两个数 $n, m$，表示同学数量和小 C 的编号；

第二行 $n$ 个数，表示每位同学的需求。

输出格式

输出一行。

一个数表示答案。

样例 #1

样例输入 #1

4 3
4 4 1 2

样例输出 #1

12

提示

对于 $40 \%$，$n \leq 10$，$a_i \leq n$；

对于 $100 \%$，$n \leq 10^5$, $a_i \leq n$。