4208. Por Una Cabeza

【题目背景】

不玩原神

【题目描述】

现在我们有一个长度为$n$ 的排列 $a$，对于一个排列满足：$存在也仅存在一个{i}\in~[2,n-1],a_1<a_2<a_3...a_{i-2}<a_{i-1}>a_i<a_{i+1}<a_{i+2}...a_n$，称这是雪豹排序。如果将雪豹排序中$a_{[1,i]}、a_{[i+1,n]}$随机打乱（${i}$是雪雪位置），则生成的序列为豹雪排列，这个${i}$也叫做豹豹位置。现豹豹给你${q}$次操作，操作有两种，操作一为交换排列里两个数的值，操作二为查询区间${[l,r]}$中有多少个数是当前数列的豹豹位置。当然豹豹想要先知道${n}$的${n!}$种排列里雪豹排列的数量，所有输出的答案都模上${1e9+7}。n,q\le 2e5$。

【输入格式】

第一行包含两个整数$ n $和 $Q$，表示排列长度和操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示初始排列。

接下来 $Q$ 行，每行描述一个操作： 

交换操作：$1 x y$，其中 $1 \le x, y \le n$

查询操作：$2 L R$，其中 $1 \le L \le R \le n$

【输出格式】

第一行首先输出雪豹排列的数量,可能特别大，对1919810取模。

接下来，对于每个 2 L R 操作，输出一行一个整数，表示区间 [L, R] 内豹豹位置的数量。

【样例输入】

5 5



2 5 3 1 4



2 1 4



1 2 4



2 1 4



1 1 3



2 1 5 

【样例输出】

26



4



2



3 

【样例说明】

在120个排列中，雪豹排列有26个。

对于第一次询问：序列为2 5 3 1 4

2>1,5>1,5>1,5>4,所以说输出4

【数据规模与约定】

$目前对于66.7\%的数据Q=0$，另外33.3\%的数据$Q,n\le 100$

【来源】

芝士雪豹