When John and Brus were high school students, they liked to investigate integer sequences.
Once, John wrote down a sequence containing distinct positive integers.
Brus wanted to reorder the elements to get a "mountain sequence".
A sequence a0, a1, ..., an-1 is called a mountain sequence if there exists an index j, where 0 < j < n-1, such that the sequence a0, a1, ..., aj is strictly increasing, and the sequence aj, aj+1, ..., an-1 is strictly decreasing.
A sequence is strictly increasing if each element is strictly greater than the element before it, and a sequence is strictly decreasing if each element is strictly less than the element before it.
Brus also wanted the resulting sequence to satisfy one additional rule.
The absolute difference between each pair of adjacent elements must be less than or equal to k.
You are given a int sequence containing John's original sequence.
Return the number of possible valid mountain sequences Brus could construct modulo 1234567891.
If no valid sequences can be constructed, return 0.