Однажды на уроке информатики Дима решил все возможные задачи про перестановки. Тогда он придумал задачу про суперперестановку.

Суперперестановкой порядка $$$n$$$ называется такая последовательность чисел от $$$1$$$ до $$$n$$$, что каждая перестановка чисел от $$$1$$$ до $$$n$$$ входит в неё как подотрезок.

Дима быстро придумал, что получать суперперестановки он будет с помощью следующего алгоритма:

• $$$s_1 = [1]$$$.
• Исходно $$$s_{n+1}$$$ приравняем к $$$s_n$$$.
• Будем рассматривать подотрезки $$$s_n$$$ длины $$$n$$$ слева направо, по увеличению левой границы.
• Если очередной подотрезок $$$s_n[l, l+1, \ldots, l+n-1]$$$ является перестановкой чисел от $$$1$$$ до $$$n$$$, то есть, на этом отрезке встречаются все числа от $$$1$$$ до $$$n$$$ по одному разу, то вставим в $$$s_{n+1}$$$ числа $$$n + 1, s_n[l], s_n[l + 1], \ldots, s_n[l+n-1]$$$ сразу после последнего элемента $$$s_n[l+n-1]$$$ соответствующего подотрезка.

Посмотрим, как получаются суперперестановки порядка $$$1$$$, $$$2$$$, $$$3$$$ и $$$4$$$:

По определению $$$s_1 = [ 1 ]$$$.

Положим $$$s_2 = [ 1 ]$$$. Рассмотрим единственный отрезок длины $$$1$$$ в $$$s_1$$$: $$$[1]$$$ является перестановкой, вставляем после него $$$[2, 1]$$$ в $$$s_2$$$, получаем $$$s_2 = [1, \mathbf{2, 1}]$$$.

Положим $$$s_3 = [ 1, 2, 1 ]$$$. Рассмотрим отрезки длины $$$2$$$ в $$$s_2$$$. $$$[1, 2]$$$ является перестановкой, вставляем после него $$$[3, 1, 2]$$$, получаем $$$s_3 = [1, 2, \mathbf{3, 1, 2}, 1]$$$. $$$[2, 1]$$$ также является перестановкой, после его последнего элемента в $$$s_3$$$ вставляем $$$[3, 2, 1]$$$, получаем $$$s_3 = [1, 2, 3, 1, 2, 1, \mathbf{3, 2, 1}]$$$.

Положим $$$s_4 = [ 1, 2, 3, 1, 2, 1, 3, 2, 1]$$$. Рассмотрим отрезки длины $$$3$$$ в $$$s_3$$$.

• $$$[1, 2, 3]$$$ является перестановкой, вставляем после него $$$[4, 1, 2, 3]$$$, получаем $$$s_4 = [ 1, 2, 3, \mathbf{4, 1, 2, 3}, 1, 2, 1, 3, 2, 1]$$$.
• $$$[2, 3, 1]$$$ является перестановкой, вставляем после него $$$[4, 2, 3, 1]$$$, получаем $$$s_4 = [ 1, 2, 3, 4, 1, 2, 3, 1, \mathbf{4, 2, 3, 1}, 2, 1, 3, 2, 1]$$$.
• $$$[3, 1, 2]$$$ является перестановкой, вставляем после него $$$[4, 3, 1, 2]$$$, получаем $$$s_4 = [ 1, 2, 3, 4, 1, 2, 3, 1, 4, 2, 3, 1, 2, \mathbf{4, 3, 1, 2}, 1, 3, 2, 1]$$$.
• $$$[1, 2, 1]$$$ перестановкой не является, поэтому ничего не делаем и переходим к следующему отрезку.
• $$$[2, 1, 3]$$$ является перестановкой, вставляем после него $$$[4, 2, 1, 3]$$$, получаем $$$s_4 = [ 1, 2, 3, 4, 1, 2, 3, 1, 4, 2, 3, 1, 2, 4, 3, 1, 2, 1, 3, \mathbf{4, 2, 1, 3}, 2, 1]$$$.
• Аналогично делаем для двух оставшихся перестановок длины 3: $$$[1, 3, 2]$$$ и $$$[3, 2, 1]$$$.

Дима заметил, что это довольно эффективный способ построения суперперестановки, поскольку каждая перестановка встречается ровно один раз. Чтобы убедиться, что Дима не ошибся, он хочет по заданной перестановке $$$a_1, \dots, a_n$$$ найти её вхождение в суперперестановку $$$s_n$$$. Позиции в суперперестановке нумеруются, начиная с единицы.

Так как длина $$$s_n$$$ достаточно большая, то необходимо вывести остаток от деления номера первого элемента последовательности $$$s_n$$$, с которого начинается вхождение в неё заданной перестановки, на число $$$10^9 + 7$$$.