Stack

You are given a sequence, $s$, of size $N$ with elements from the set $\{0, 1, 2, \ldots, M - 1\}$. We define the compression function of a sequence as follows:

function compress(s)
	stk ← []
	for i ← 0 ... len(s) − 1 do
		if s[i] = last element of stk then
			remove last element from stk
		else
			stk ← stk + s[i]
		end if
	end for
	return len(stk)
end function

Requirement

We denote by $s[i\dots j]$ the contiguous subsequence of $s$ obtained by removing the prefix $s_0, s_1, \dots s_{i-1}$ and the suffix $s_{j+1}, s_{j+2}, \dots s_{N-1}$.

Compute

Since this number can become very large, output the remainder of its division by $2^{64}$.

Implementation Details

You must implement the function

std::uint64_t sum_compressed_lengths(std::vector<int> s, int M);

which:

• receives as parameters the sequence $s$ and $M$, with the meaning given in the statement;
• returns the required sum modulo $2^{64}$.

The judge will call the function exactly once per test.

Constraints and Notes

• $1 \leq M \leq N \leq 5 \ 000 \ 000$
• $0 \leq s_i < M$

Example

input

10 5
2 2 3 3 4 4 1 1 4 3

output

64