На одной из своих контрольных работ по информатике Дмитрий Олегович решил дать следующую задачу:

Пусть дано дерево 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 вершинах считаются различными, если их матрицы смежности a₁ и a₂ не совпадают, то есть существует такая пара (i, j), что 1 ≤ i, j ≤ n и a₁[i][j] ≠ a₂[i][j].