题目描述

大家都知道 $n$ 阶排列有 $n!$ 个，神奇的 zzy 认为这很没意思。

他施展魔法把所有的 $n$ 阶排列传送到了异世界，然后创死了所有最长上升子序列长度 $\ge 3$ 的排列。

但 zzy 依旧觉得很无趣，他又创造了 $m$ 条世界线，第 $i$ 条世界线的法则是 $x$ 必须位于 $pos_i$ 位置。

对于每个世界线，你需要告诉 zzy 符合条件的排列有多少个，对 $10^9+7$ 取模。

形式化地，对于第 $i$ 个问题，符合他条件的排列 $P$ 满足：

• $P$ 是 $n$ 阶排列。
• $\forall 1\leq i<j<k \leq n, \neg (P_i<P_j<P_k)$.
• $P_{pos_i} = x$.

输入格式

第一行三个整数 $n,m,x$ ($1\leq n,m\leq 500, 1\leq x\leq n$)。

第二行 $m$ 个整数 $pos_1,pos_2,\ldots,pos_m$ ($1\leq pos_i \leq n$)。

输出格式

一行，$m$ 个整数，第 $i$ 个整数表示第 $i$ 个问题的答案。

样例 1 输入

10 10 5
1 2 3 4 5 6 7 8 9 10

样例 1 输出

429 1375 2310 2520 1764 588 1848 2673 2288 1001

样例 2 输入

50 5 12
2 12 22 32 42

样例 2 输出

649624491 426442934 805738681 404720023 80426482

样例 3 输入

500 5 212
12 112 212 312 412

样例 3 输出

38822761 799706133 331782079 959426566 240547714

数据范围

对于 $100\%$ 的数据，$1\leq n, m \leq 500$, $1 \leq x, pos_i \leq n$。