Код вероятности для категории чеков

В базе супермаркета сохранены чеки. Для каждого чека указаны идентификатор, главная категория покупки и сумма чека в копейках. Значение - в поле категории означает, что категория не определена.

Из всех n чеков случайно выбирают ровно k различных чеков без возвращения. Порядок выбора не важен: каждый набор из k чеков равновероятен. В конце входа задана категория, для которой требуется вычислить вероятность того, что главная категория каждого выбранного чека совпадает с категорией из запроса.

Пусть m — число чеков с категорией из запроса. Искомая вероятность равна C(m, k) / C(n, k), где C(a, b) — число способов выбрать b объектов из a, а C(a, b) = 0 при a < b. Требуется вывести четырёхзначительный код вероятности: floor(9999 * C(m, k) / C(n, k)).

При равенстве названий категорий, включая строки разных чеков, категории считаются одинаковыми. Значение - не совпадает с категорией из запроса и не учитывается в m.

Формат ввода

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

В следующих n строках даны три значения: receipt_id, category, total_kopecks — идентификатор чека, главная категория и сумма чека в копейках.

В последней строке даны k и query_category — число выбираемых чеков и категория из запроса.

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

Выведите код вероятности ровно из четырёх цифр. Если в коде меньше четырёх цифр, допишите слева нули.

Ограничения

1 <= n <= 2000.

1 <= k <= n.

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

category имеет длину от 1 до 20 символов из латинских букв или равно -.

query_category имеет длину от 1 до 20 символов из латинских букв и не равно -.

0 <= total_kopecks <= 1000000000.