Museum Tour Routes

A prestigious interactive museum has recently opened with a unique visitor experience system. The museum features a digital pass program designed to encourage thorough exploration of its exhibitions while managing visitor flow.

Each visitor receives a special digital museum pass upon entry. The pass is included in the admission price and tracks their progress through the museum using an electronic stamp system.

To ensure visitors engage meaningfully with the exhibitions rather than rushing through, the museum has implemented a structured tour system. The museum consists of $N$ exhibition halls, and at each hall, visitors must scan their digital pass at a verification station, which adds a digital stamp to their record. Once a visitor accumulates more than $K$ stamps, they are automatically directed to the exit and receive a completion certificate. If they have fewer than $K$ stamps, they can choose any connecting corridor from their current hall to another hall and continue their tour. At the new hall, they must scan their pass again. The system requires that visitors cannot exit the museum until they have collected exactly $K$ stamps on their pass.

Young museum enthusiast Vincent is planning his visit and wants to explore the most interesting routes through the museum. However, he first needs to determine the total number of possible tour routes. Since this number could be quite large, he asks you to calculate the result modulo $1000000007$.

Help him find the solution.