Crate stacks

Count the legal ways to stack crates of several types, modulo 1,000,000,007.

A loading dock builds a stack of exactly n crates, listed from the bottom crate to the top crate. There are k crate types numbered 0 to k - 1, and any type can be used any number of times. A stack is legal when it obeys both rules:

1. Run limit. At most limits[t] crates of type t may sit directly on top of each other in a row. A row of more than that many consecutive crates of type t is not allowed.
2. Banned pairs. banned is a list of pairs [a, b] with a != b. For such a pair, a crate of type b may not sit directly on top of a crate of type a. The pair is directional: [a, b] being banned says nothing about a crate of type a sitting on a crate of type b.

Two stacks are different if they differ in the type of the crate at any position.

Input: n, an integer; limits, a list of k integers (so k is len(limits)); and banned, a list of [a, b] pairs.

Output: an integer, the number of legal stacks of height n, modulo 1_000_000_007. If no stack is legal, return 0.

The stack height can be astronomically large, so building the stack one crate at a time will be too slow.