小A的排列

题号：NC22729
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小A有一个长度为n的排列 $p_i$ ，
小A想要知道这个排列中，所有区间的中位数。
不过最近小A沉迷巫师3，到处打牌无法自拔，所以他找到了你，希望你能够解决这个问题。
设区间l,r的中位数为 $mid_{l,r}$
为了方便，只需要你输出 $ans=2×\sum_{l=1}^n \sum_{r=l}^n seed^{(l-1)*n+r} mid_{l,r}$ 。
答案对

取模。
中位数的定义：
对于一个不重集合，将这个集合里的数从小到大排序为 $a_1,a_2,a_3,....,a_m$
当m是奇数，S的中位数为 $a_{(m+1)/2}$
当m是偶数，S的中位数为 $(a_{m/2}+a_{m/2+1})/2$

输入描述:

第一行两个正整数n,seed ,含义如题目所示
第二行一个排列p

输出描述:

一个正整数ans。

示例1

输入

复制

4 1
1 2 3 4

输出

复制