Count schedules with no process in two slots in a row

You have p distinct processes and t time slots in a row. A schedule puts exactly one process in each slot, and a process may appear in many slots. A schedule is valid when no process is in two neighbouring slots.

Write count_schedules(p: int, t: int) -> int: the number of valid schedules, modulo 1_000_000_007.

• 1 <= p <= 10**9, 0 <= t <= 10**18.
• With t == 0 there is exactly one (empty) schedule, so return 1.
• With one process, only t <= 1 is possible.

t can be up to 10**18, so anything that loops over the slots is far too slow: aim for O(log t).

count_schedules(3, 3)   # 12   (e.g. 1-2-1 and 3-1-2 are valid, 1-1-2 is not)
count_schedules(2, 4)   # 2    (1-2-1-2 and 2-1-2-1)
count_schedules(1, 2)   # 0
count_schedules(5, 0)   # 1

Discussion

• Why is every row of the slot-by-process table identical, and what does that tell you?
• How does square-and-multiply modular exponentiation work, and where must you reduce modulo 10**9 + 7 to avoid overflow in a fixed-width language?