Разбиения посылок на одинаковые партии

В пункте выдачи готовые к выдаче посылки объединяют в партии для внутренней сортировки. В одной партии могут находиться только посылки одной зоны хранения. Размер каждой партии должен совпадать с размером, указанным в запросе.

Посылки со статусом, отличным от READY, в сортировке не участвуют. Посылки с зоной - также не участвуют, так как их зона хранения ещё не определена.

Посылки считаются различными объектами даже при совпадении всех указанных признаков. Если несколько посылок имеют одинаковую зону, каждая перестановка самих посылок внутри одной партии не создаёт нового разбиения, а обмен двух целых партий одинакового состава по размеру также не создаёт нового разбиения.

Пусть в некоторой зоне находится c участвующих посылок, а размер партии в запросе равен k. Если c не делится на k, число допустимых разбиений для всей сортировки равно 0. Иначе число разбиений посылок этой зоны равно c! / ((k!)^(c/k) * (c/k)!). Ответом является произведение этих значений по всем зонам, содержащим хотя бы одну участвующую посылку.

При совпадении всех данных у нескольких строк посылки всё равно считаются разными и различаются позицией строки во входных данных. Пустые зоны не влияют на произведение. Деления на ноль не возникает, поскольку размер партии в запросе не меньше 1.

Формат ввода

В первой строке дано целое число n — число записей о посылках.

В следующих n строках даны через пробел три значения: идентификатор посылки parcel_id, зона хранения zone и статус status.

В последней строке дан запрос в формате ЗАПРОС k, где k — требуемый размер партии.

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

Выведите одно целое число — количество допустимых разбиений участвующих посылок на партии размера k по запросу.

Дробной части в ответе нет, выведите целое число без округления.

Ограничения

1 <= n <= 4000.

Длина parcel_id составляет от 1 до 20 символов из латинских букв, цифр и символа _.

zone равно - либо строке длиной от 1 до 12 символов из латинских букв, цифр и символа _.

status равно одному из значений READY, HOLD, DAMAGED, RETURNED.

1 <= k <= 4000.

Количество участвующих посылок в любой зоне может быть от 0 до 4000.