Multi-tap keypad: every string a press sequence can spell

An old phone types letters by multi-tap: pressing a key once gives its first letter, twice in a row gives its second letter, and so on. Use this keypad:

You get a string digits of key presses, with no pauses recorded. A run of the same digit is ambiguous: it can be cut into groups in any way, and a group of k presses means the k-th letter of that key. A group can never be longer than the number of letters on its key (no wrap-around), and a group never spans two different digits.

Implement keypad_combinations(digits: str) -> list[str] that returns every string the presses could spell, in sorted order.

Constraints

• 0 <= len(digits) <= 20, each character is 0-9.
• Return [] for an empty input. Raise an error for any other character.

Example 1

input:  "111"
output: ["AAA", "AB", "BA", "C"]

The run of three 1s can be cut as 1+1+1, 1+2, 2+1 or 3.

Example 2

input:  "772"
output: ["SSD", "TD"]

Key 7 has two letters, so its run gives SS or T; the single 2 gives D.

Part 2: return only the number of possible strings for inputs up to 10^5 presses, modulo 10^9 + 7.

Reconstructed from the reported question; details may differ from what interviewers ask.