Подборка фильмов с документальным кино

Онлайн-кинотеатр формирует рекламную подборку из трёх фильмов каталога. Каждая строка входных данных описывает отдельный фильм. Номера фильмов уникальны, поэтому даже фильмы с одинаковым жанром считаются разными объектами.

Требуется посчитать количество способов выбрать ровно три различных фильма так, чтобы среди выбранных был хотя бы один фильм жанра DOCUMENTARY.

Пусть n — число строк каталога, а d — число строк, в которых жанр равен DOCUMENTARY. Искомое число равно

C(n, 3) - C(n - d, 3),

где C(a, 3) = a(a - 1)(a - 2) / 6, а при a < 3 значение C(a, 3) равно 0. Жанр - означает пропуск в данных и не считается жанром DOCUMENTARY. Выведите точное целое число, округление не требуется. Правило равенства не применяется, так как требуется вывести одно число.

Формат ввода

В первой строке дано целое число n — количество фильмов в каталоге.

В следующих n строках записаны два значения через пробел: film_id и genre — номер фильма и его жанр.

Формат вывода

Выведите одно целое число — количество подходящих подборок из трёх фильмов.

Ограничения

• 1 ≤ n ≤ 2000;
• 1 ≤ film_id ≤ 10^9;
• все значения film_id различны;
• genre — одно из значений DOCUMENTARY, FEATURE, ANIMATION, SERIES, SHORT, -;
• длина значения genre составляет от 1 до 11 символов;
• если в каталоге меньше трёх фильмов или нет подходящих подборок, ответ равен 0.