На одной из своих контрольных работ по информатике Дмитрий Олегович решил дать следующую задачу:
Пусть дано дерево 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].