排列计数机
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

定义一个长为k的序列的权值为：对于所有，有多少种不同的取值。
给出一个1到n的排列，求B的所有非空子序列的权值的m次方之和。
答案对取模。

输入描述:

第一行两个整数n、m。
接下来一行n个整数，第i个整数为B_i。

输出描述:

输出一个整数，表示答案。
示例1

输入

复制 
3 2
1 3 2

输出

复制 
16

说明

在所有非空子序列中：
(1), (3), (2), (3, 2)权值为1，
(1, 3), (1, 2), (1, 3, 2)权值为2。
那么所有非空子序列权值的2次方和为4 \times 1^2 + 3 \times 2^2 = 16。

备注:

对于前的数据，。
对于前的数据，。
对于前的数据，。
对于另外的数据，m = 1。
对于所有数据，，，保证B是1到n的排列。