Background

USACO January 2019 Gold, Problem 1.

Problem Description

Unknown to Farmer John, Bessie is also enthusiastic about sponsoring artistic creation. Recently, she started studying many great poets, and now she wants to try writing some poems of her own.

Bessie knows $N$ words ($1 \leq N \leq 5000$) and wants to use them in her poems. She has computed the length of each word she knows in syllables, and she has also divided these words into different "rhyme classes". Each word rhymes only with other words in the same rhyme class.

Each poem Bessie writes has $M$ lines ($1 \leq M \leq 10^5$). Each line must consist of exactly $K$ syllables ($1 \leq K \leq 5000$). In addition, Bessie's poem must follow a specified rhyme scheme.

Bessie wants to know how many different poems she can write that satisfy these constraints.

Input Format

The first line contains $N$, $M$, and $K$.

The next $N$ lines each contain two integers $s_i$ ($1 \leq s_i \leq K$) and $c_i$ ($1 \leq c_i \leq N$). This indicates a word that Bessie knows with length $s_i$ (in syllables) and rhyme class $c_i$.

The last $M$ lines describe the rhyme scheme Bessie wants, each containing an uppercase letter $e_i$. All lines whose rhyme scheme letter equals $e_i$ must end with a word from the same rhyme class. Lines with different $e_i$ values are not required to end with words from different rhyme classes.

Output Format

Output the number of different poems Bessie can write that satisfy these constraints. Since this number may be very large, output it modulo $1,000,000,007$.

3 3 10
3 1
4 1
3 2
A
B
A

960

Hint

In this example, Bessie knows three words. The first two words rhyme and have lengths of three and four syllables, respectively. The last word has length three syllables and does not rhyme with any other word. She wants to write a three-line poem, where each line has ten syllables, and the first and last lines rhyme. There are $960$ such poems. One valid poem is (where $1,2,3$ represent the first, second, and third words): $\text{121 123 321}$.

Translated by ChatGPT 5