You are given an array A of length N and a number M such that M N$.$ It is given that each element in A is between $1$ and M$,$ and each number from $1$ to M appears at least once in A$.$

Find the maximum lexicographical subsequence permutation in A$.$

Let's assume that the resulting array is P$.$ Your task is to print the sum of $($P$[$i$]*$ i$)$ modulo $1$e$9+7$ for each i from $1$ to M$.$

Input Format

The first line contains an integer, N$,$ denoting the number of elements in A$.$

The next line contains an integer, M$,$ denoting the given integer.

Each line i of the N subsequent lines $($where $0$ i $<$ N$)$ contains an integer describing A$[$i$].$

Constraints

$1<=$N$<=2*10^5$

Sample Test Cases

Case $1$

Input:

$2$

$1$

$1$

$1$

Output:

$1$

Explanation:

Given N $=2,$ M$1,$ A$=[1,1].$

The resulting array is $1,$ so the answer is $1*1=1$

Case $2$

Input:

$2$

$2$

$1$

$2$

Output:

$5$

Explanation:

Given N $=2$ M $=2$ A $=[$ matrix $1,2$ matrix $].$

The resulting array is $12,$ so the answer is $1^*1+22=5$

Case $3$

Input:

$3$

$3$

$3$

$1$

$2$

Output:

$11$

Explanation:

Given N $=3$ M $=3$ A $=[3,1,2]$

The resulting array is $312,$ so the answer is $2*3=11$

int get$\_$ans$($int N$,$ int M$,$ vector A$)\{$

$//$ Write your code here

$\}$