Вы разрабатываете систему, одной из задач которой является составление расписания работы над задачами, выполняемыми некоторой организацией, занимающейся разработкой программного обеспечения.
Известно, что организации необходимо выполнить n задач, пронумерованных натуральными числами от одного до n. На выполнение каждой задачи требуется ровно один день, и в каждый день может быть выполнена только одна задача. Таким образом, на выполнение всех задач потребуется n дней, а расписание выполнения задач выглядит как назначение определенного дня на выполнение каждой задачи. Для каждой задачи известно также число ai — номер дня, ранее которого не может быть начато выполнение этой задачи.
Ваша программа должна, имея информацию о количестве задач и днях, ранее которых выполнение задач не может быть начато, определить количество допустимых расписаний выполнения задач— количество таких расписаний, при которых каждая задача выполняется не ранее указанного для нее дня.
Входные данные
В первой строке находится натуральное число n (1 ≤ n ≤ 8) — количество задач, которые необходимо выполнить.
Следующая строка содержит n натуральных чисел ai (1 ≤ ai ≤ n) — для каждой работы номер дня, ранее которого не может быть начато выполнение этой задачи. Числа отделены друг от друга одним пробелом.
Выходные данные
Выведите одно число — количество различных допустимых расписаний выполнения задач.
Пример входных и выходных данных