题目背景

星光合唱团即将登台演出,团长小星正在为排队形的事情发愁。

题目描述

合唱团共有 $n$ 名成员,第 $i$ 名成员的身高数值为 $h_i$($1000 \le h_i \le 2000$),且任何两名成员的身高互不相同。最终队形是 $n$ 个人站成一排。小星设计了一套独特的排队方法:让所有人先按某种顺序站成一个初始队形,然后从左到右依次把每个人插入最终队形中,规则如下:

• 第一个人直接进入空的当前队形;

• 从第二个人开始,每个人与初始队形中排在他前一个人(即上一个插入的人)比较身高:若他更高,则把他插入当前队形的最右边;若他更矮,则把他插入当前队形的最左边。

所有人都插入完毕后,就得到了最终队形。

例如,$6$ 个人站成初始队形,身高依次为 $1850, 1900, 1700, 1650, 1800, 1750$,排队过程如下:

• $1850$;

• $1850, 1900$,因为 $1900 \gt 1850$;

• $1700, 1850, 1900$,因为 $1700 \lt 1900$;

• $1650, 1700, 1850, 1900$,因为 $1650 \lt 1700$;

• $1650, 1700, 1850, 1900, 1800$,因为 $1800 \gt 1650$;

• $1750, 1650, 1700, 1850, 1900, 1800$,因为 $1750 \lt 1800$。

因此最终队形为 $1750, 1650, 1700, 1850, 1900, 1800$。

现在小星心中有一个理想队形,他想知道有多少种不同的初始队形能够排出这个理想队形。答案对 $19650827$ 取模。

输入格式

输入第一行一个整数 $n$。

第二行 $n$ 个整数,表示理想队形(从左到右每个人的身高数值)。

输出格式

输出一行一个整数,表示方案数对 $19650827$ 取模的结果。

样例

4
1701 1702 1703 1704

8

提示

对于 $30\%$ 的数据,$n \le 100$。

对于 $100\%$ 的数据,$n \le 1000$,$1000 \le h_i \le 2000$,且身高互不相同。