Bessie's Poetry Composition

Bessie, famous for her secret love of art, is now trying her hooves at writing poetry! She knows N words and has computed their lengths in syllables. Moreover, she has divided these words into different rhyme classes (i.e. words in the same class rhyme with each other). Each poem she writes has M lines, and every line must consist of exactly K syllables. In addition, the poem must follow a specified rhyme scheme.

More formally, you are given integers \(N, M, K\) with \(1 \le N \le 5000\), \(1 \le M \le 10^5\), and \(1 \le K \le 5000\). The next \(N\) lines each contain two integers \(s\) and \(c\) where:

• \(s\) (in syllables) is the length of a word, and
• \(c\) is the rhyme class of that word.

Then, the next \(M\) lines each contain a single uppercase letter indicating the rhyme scheme for that line. Lines with the same letter must end with words from the same rhyme class.

A line can be constructed by concatenating any number of words (words can be reused arbitrarily) such that the total number of syllables is exactly \(K\). When constructing a line, the final word determines its rhyme class. For each word with syllable count \(s\) and rhyme class \(c\), if it is used as the final word then the preceding part of the line must form exactly \(K-s\) syllables. Let \(dp[x]\) be the number of ways to form exactly \(x\) syllables (with \(dp[0]=1\)). Then the contribution of a word of length \(s\) in rhyme class \(c\) is \(dp[K-s]\).

For each rhyme class \(r\), let \[ R[r] = \sum_{\text{word }(s, r)} dp[K-s]. \] If for a given rhyme letter (say letter \(L\)) in the rhyme scheme there are \(f_L\) lines, then the total number of ways to choose ending words for those lines is \[ \sum_{r} (R[r])^{f_L} \pmod{10^9+7}. \] The answer is the product (over distinct letters in the rhyme scheme) of these values modulo \(10^9+7\>.

Output the total number of poems Bessie can compose under these restrictions modulo \(10^9+7\>.

inputFormat

The first line contains three integers: N, M, and K.

The next N lines each contain two integers s and c indicating the syllable count and rhyme class of a word.

The following M lines each contain a single uppercase letter representing the rhyme scheme of the poem. Lines with the same letter must end with words from the same rhyme class.

outputFormat

Output a single integer: the number of different poems Bessie can compose, modulo \(10^9+7\).

sample

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

960