На одной из своих контрольных работ по информатике Дмитрий Олегович решил дать следующую задачу:
Пусть дано дерево T на n вершинах, заданное своей матрицей смежности a[1... n, 1... n]. Какую последовательность чисел выведет следующий псевдокод?
used[1 ... n] = {0, ..., 0};
procedure dfs(v):
print v;
used[v] = 1;
for i = 1, 2, ..., n:
if (a[v][i] == 1 and used[i] == 0):
dfs(i);
dfs(1);
Чтобы было легче проверять работы студентов, Дмитрий Олегович решил придумать такое дерево T, чтобы в ответе получилась его любимая последовательность b. С другой стороны, Дмитрий Олегович не хочет давать студентам одинаковые данные в контрольной работе — ведь в таком случае не миновать списывания. Поэтому у Дмитрия Олеговича возник следующий вопрос: сколько существует таких деревьев, что при запуске данного псевдокода на них выведенная последовательность в точности совпадает с последовательностью b?
Два дерева на n вершинах считаются различными, если их матрицы смежности a1 и a2 не совпадают, то есть существует такая пара (i, j), что 1 ≤ i, j ≤ n и a1[i][j] ≠ a2[i][j].
В первой строке задано натуральное число n (1 ≤ n ≤ 500) — количество чисел в последовательности b.
Во второй строке задаются n натуральных чисел b1, b2, ..., bn (1 ≤ bi ≤ n), разделенные пробелом. Гарантируется, что последовательность b является перестановкой. Иными словами, каждое из чисел 1, 2, ..., n встречается в последовательности b ровно один раз. Также гарантируется, что b1 = 1.
Выведите одно число — остаток от деления количества подходящих деревьев на 109 + 7.
3
1 2 3
2
3
1 3 2
1
