{"problem":{"name":"I. Space and Time and Music","description":{"content":"In the distant future, Ellen works as a musician for the Willbeington D.C. Philharmonic. However, frequent use of time travel has caused the Fabric of Space and Time to weaken considerably, to the ext","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10275I"},"statements":[{"statement_type":"Markdown","content":"In the distant future, Ellen works as a musician for the Willbeington D.C. Philharmonic. However, frequent use of time travel has caused the Fabric of Space and Time to weaken considerably, to the extent that certain melodies can cause severe vibrations and harm the musician playing them, as well as the Fabric itself. To prevent such harm, the Ministry of Music has created a handy guidebook for composing melodies, which details which instruments can follow which other instruments, as well as how many notes can be played on any given instrument.\n\nUnfortunately, this guidebook was greeted by large amounts of backlash from people that believed that the Ministry of Music was suffocating their creative spirit in making music, and was just a power grab on the part of the Minister for Music. In response to concerns that the guidebook was limiting the supply of fresh melodies, Ellen decides to enumerate all the possible melodies that can be written that still follow the guidebook. \n\nSince the guidebook has no restrictions on length of melody, this number is possibly infinite. So, Ellen restricts her count to only consider melodies of length $K$, and ones starting with the $S$'th instrument. \n\nGiven the guidebook, the starting instrument, and the number of notes, find the answer for Ellen. Because the number of possible melodies might be very large, output the answer$mod 10^9 + 7$.\n\nThe first line of input contains four integers, $N, M, K, S$ ($1 <= N <= 50$, $1 <= M <= N^2$, $1 <= K <= 10^6$, $0 <= S <= N -1$) - the number of distinct instruments, the number of ordered pairs of instruments that can follow each other, the number of notes in the melody being constructed, and the index of the starting instrument.\n\nThe second line contains $N$ integers $a_i$ ($1 <= a_i <= 10^6$) — the number of notes the $i$th instrument can play.\n\nFinally, $M$ lines follow, where the $j$th line is of the form $x_j \" \"y_j$ ($0 <= x_j, y_j <= N -1$), indicating that the $y_j$'th instrument can follow the $x_j$'th instrument. \n\nOutput a single integer equal to the number of total melodies that can be created following the rules of the guidebook that start with instrument $S$ and last exactly $K$ notes, mod $10^9 + 7$\n\nIn the first example, the only way to make a melody is to use a note from instrument $0$ and then a note from instrument $1$. After this second note, no further notes can be added to the melody, since no instrument is allowed to follow instrument $1$. So, there are no melodies of length $10$. \n\nIn the second example, there are two ways to make a melody: use instruments $0, 1, 2$, in that order, or $0, 1, 0$, in that order. In the first case, there are $1 dot.op 2 dot.op 3 = 6$ ways to choose the notes, and in the second, there are $1 dot.op 2 dot.op 2 = 2$, for a total of $8$. \n\n## Input\n\nThe first line of input contains four integers, $N, M, K, S$ ($1 <= N <= 50$, $1 <= M <= N^2$, $1 <= K <= 10^6$, $0 <= S <= N -1$) - the number of distinct instruments, the number of ordered pairs of instruments that can follow each other, the number of notes in the melody being constructed, and the index of the starting instrument.The second line contains $N$ integers $a_i$ ($1 <= a_i <= 10^6$) — the number of notes the $i$th instrument can play.Finally, $M$ lines follow, where the $j$th line is of the form $x_j \" \"y_j$ ($0 <= x_j, y_j <= N -1$), indicating that the $y_j$'th instrument can follow the $x_j$'th instrument. \n\n## Output\n\nOutput a single integer equal to the number of total melodies that can be created following the rules of the guidebook that start with instrument $S$ and last exactly $K$ notes, mod $10^9 + 7$\n\n[samples]\n\n## Note\n\nIn the first example, the only way to make a melody is to use a note from instrument $0$ and then a note from instrument $1$. After this second note, no further notes can be added to the melody, since no instrument is allowed to follow instrument $1$. So, there are no melodies of length $10$. In the second example, there are two ways to make a melody: use instruments $0, 1, 2$, in that order, or $0, 1, 0$, in that order. In the first case, there are $1 dot.op 2 dot.op 3 = 6$ ways to choose the notes, and in the second, there are $1 dot.op 2 dot.op 2 = 2$, for a total of $8$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of instruments.  \nLet $ M \\in \\mathbb{Z} $ be the number of valid transitions.  \nLet $ K \\in \\mathbb{Z} $ be the length of the melody.  \nLet $ S \\in \\{0, 1, \\dots, N-1\\} $ be the starting instrument.  \nLet $ A = (a_0, a_1, \\dots, a_{N-1}) \\in \\mathbb{Z}^N $, where $ a_i $ is the number of notes available on instrument $ i $.  \nLet $ G = (V, E) $ be a directed graph with $ V = \\{0, 1, \\dots, N-1\\} $, and $ E \\subseteq V \\times V $, where $ (x, y) \\in E $ iff instrument $ y $ can follow instrument $ x $.  \n\n**Constraints**  \n1. $ 1 \\le N \\le 50 $  \n2. $ 1 \\le M \\le N^2 $  \n3. $ 1 \\le K \\le 10^6 $  \n4. $ 0 \\le S \\le N-1 $  \n5. $ 1 \\le a_i \\le 10^6 $ for all $ i \\in \\{0, \\dots, N-1\\} $  \n6. For each transition $ (x_j, y_j) \\in E $, $ 0 \\le x_j, y_j \\le N-1 $  \n\n**Objective**  \nCompute the total number of melodies of length $ K $, starting at instrument $ S $, where:  \n- Each note in the melody is played on an instrument,  \n- The sequence of instruments follows the transitions in $ E $,  \n- For each instrument $ i $ used in the melody, one of its $ a_i $ notes is chosen.  \n\nDefine $ dp[k][i] $ as the number of melodies of length $ k $ ending at instrument $ i $, starting from $ S $.  \n\nInitial condition:  \n$$\ndp[1][i] = \n\\begin{cases}\na_S & \\text{if } i = S \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$\n\nTransition:  \n$$\ndp[k][j] = \\sum_{\\substack{i=0 \\\\ (i,j) \\in E}}^{N-1} dp[k-1][i] \\cdot a_j \\quad \\text{for } k \\in \\{2, \\dots, K\\}\n$$\n\nAnswer:  \n$$\n\\boxed{\\sum_{i=0}^{N-1} dp[K][i] \\mod (10^9 + 7)}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10275I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}