Count payloads with sync once

Write codeHard40 min

Your task

A frame format reserves a sync word so a receiver can tell where a frame begins. A payload is usable only when the sync word turns up in it exactly once, since no appearance leaves the receiver nothing to lock onto and a second appearance lets it cut the frame in the wrong place. Payloads are exactly size characters long and are built from the characters of alphabet, which are distinct and need not cover every character of sync. Given alphabet, size and sync, return how many payloads hold sync exactly once, where appearances that overlap count separately, so aa turns up twice inside aaa. The sync word is never empty, and a negative size describes no payload at all. Totals grow fast, so return the answer modulo 1000000007.

Examples

single_sync_payload_count(alphabet: str, size: int, sync: str) -> int
Example 1
Inputsingle_sync_payload_count("ab", 3, "ab")
Output4
Example 2
Inputsingle_sync_payload_count("ab", 4, "aa")
Output5
Example 3
Inputsingle_sync_payload_count("abc", 5, "abc")
Output27