strips одинаковой длины; позиции на полосках — это столбцы 0, 1, 2, …. Нужно собрать слово goal по таким правилам:
- буквы goal берутся по очереди, слева направо;
- очередную букву goal[i] можно взять из любой полоски strips[j] в любом столбце k, где strips[j][k] == goal[i];
- после этого столбец k и все столбцы левее становятся недоступны на всех полосках: следующая буква берётся строго правее.
Из одной полоски можно брать несколько букв. Посчитайте, сколькими способами можно собрать goal; способы различаются выбором полоски или столбца хотя бы для одной буквы. Ответ верните по модулю 10⁹ + 7.strips=["ab", "ba"], goal="ab" → 1
Букву a можно взять только из столбца 0 (полоска "ab"), а b — только из столбца 1 (тоже "ab"). Способ один.
strips=["aaa", "aaa"], goal="aa" → 12
Пару столбцов можно выбрать тремя способами: (0, 1), (0, 2), (1, 2); в каждом столбце буква берётся из любой из двух полосок: 3 · 2 · 2 = 12.
strips=["xy"], goal="yx" → 0
strips=["ab", "ba"], goal="ab"
1
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 127 тестов на сервере, включая скрытые.