Сцепка вагонов без разрывов букв

Дан список cars из n строк из строчных латинских букв: каждая строка — сцепленная группа вагонов, переворачивать её нельзя. Сцепите все группы в один поезд, выбрав их порядок. Поезд правильный, если все вхождения каждой буквы стоят подряд. Верните число порядков групп, дающих правильный поезд, по модулю 1 000 000 007. Группы различаются по позиции в списке: две одинаковые строки, переставленные местами, дают два разных порядка.

Ограничения: 1 ≤ n ≤ 100, длина каждой строки от 1 до 100; перебор порядков слишком медленный.

Пример: ["aa", "aa", "bc", "c"] → 4.

Источник: Coding Competitions Archive, codejam/2014/round_1c/reordering_train_cars · © Google LLC · Apache-2.0 · условие переведено и дополнено