Распределение резерва по районам

Городской велопрокат ведёт две таблицы. В первой таблице перечислены станции и районы, в которых они расположены. Во второй таблице записаны завершённые поездки и станции возврата велосипедов.

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

Пусть T — число корректных строк поездок, а K — число различных районов, в которые попала хотя бы одна корректная поездка. После окончания дня требуется посчитать число способов распределить T одинаковых резервных велосипедов между этими K районами. В одном районе может оказаться ноль велосипедов.

Искомое число равно количеству наборов неотрицательных целых чисел x1, x2, ..., xK, для которых x1 + x2 + ... + xK = T. По формуле сочетаний с повторениями оно равно C(T + K - 1, K - 1). Если корректных поездок нет, необходимо вывести 0.

При равенстве каких-либо промежуточных количеств дополнительный выбор не выполняется, так как ответом является одно целое число.

Формат ввода

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

В следующих n строках записаны таблица станций: station_id district, где station_id — идентификатор станции, district — название района.

В следующих m строках записаны таблица поездок: trip_id return_station_id, где trip_id — идентификатор завершённой поездки, return_station_id — идентификатор станции возврата.

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

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

Дробная часть отсутствует, округление не требуется.

Ограничения

1 <= n <= 3999.

1 <= m <= 3999.

n + m <= 4000.

1 <= station_id <= 10^9, все значения station_id в таблице станций различны.

1 <= trip_id <= 10^9, все значения trip_id в таблице поездок различны.

1 <= return_station_id <= 10^9.

Название района состоит из строчных латинских букв, его длина от 1 до 12 символов.

Число различных районов в таблице станций не превышает n.