Кросворди#9688
Щоб залучити більше туристів до Парижа, Анна планує організувати масштабне світломузичне шоу вночі на фасадах Лувра. На фасадах розташовані вікна, розміщені на кількох рівнях і вирівняні як по горизонталі, так і по вертикалі.
Анні прийшла ідея відображати у вікнах величезні літери — по одній літері в кожному вікні — так, щоб утворювалися осмислені слова як по горизонталі, так і по вертикалі.
На одному фасаді вікна утворюють прямокутну сітку з рядків та стовпців.
Анна підготувала:
список з слів довжини (вони будуть відображатися вертикально),
список з слів довжини (вони будуть відображатися горизонтально).
Ваше завдання — визначити, скількома різними способами можна заповнити сітку так, щоб:
кожен рядок утворював коректне горизонтальне слово,
кожен стовпець утворював коректне вертикальне слово.
Потрібно підрахувати кількість різних буквених сіток розміру n \times m, таких що:
кожен з рядків, читаючи зліва направо, є словом з горизонтального списку;
кожен з стовпців, читаючи зверху вниз, є словом з вертикального списку.
Дві сітки вважаються різними, якщо вони відрізняються хоча б в одній клітинці.
Вхідні дані мають такий формат:
у першому рядку задано два цілі числа n~(2 \le n \le 4) і ;
у другому рядку задано два цілі числа m~(2 \le m \le 4) і b~(1 \le a \times b \le 1008016);
у наступних рядках записано слова довжини (вертикальні слова);
у наступних рядках записано слова довжини (горизонтальні слова).
Обмеження:
усі слова складаються тільки з малих англійських літер (–);
кожен список не містить повторюваних слів;
слова можуть використовуватися кілька разів у різних рядках або стовпцях.
Особливий випадок. Якщо n = m, то:
слово з вертикального списку не можна використовувати горизонтально, якщо воно також не присутнє у горизонтальному списку;
слово з горизонтального списку не можна використовувати вертикально, якщо воно також не присутнє у вертикальному списку.
Виведіть загальну кількість різних коректних буквених сіток.
Приклад 1:
Приклад 2:
Приклад 1
Приклад 2