Очень просто. Смотри на первый пример:
product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
Генерятся комбинации из двух символов (так как два параметра). Причем первый параметр кодирует возможные первые символы, а второй - возможные вторые.
Нам нужно только обобщить это.
Идешь циклом по строке-маске и формируешь список, где каждый элемент - список подставляемых знаков, соответствующих текущему символу строки-маски. (Назовём этот список списков parts).
А дальше просто делаешь цикл for combo in product(*parts):
