чемпионаты Спб: СПбКОШП 2019

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

Суперперестановкой порядка \(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\).