Detective Sherlock Holmes stared at the crime scene photos, his pipe emitting thoughtful curls of smoke. The Lestrade Manor banquet had ended in what appeared to be a meticulously orchestrated mass murder.
He turned to you, his assistant. "The police have recorded every constraint, but missed the crucial connections. We need to count every possible scenario consistent with their fragmented evidence. It's a straight forward combinatorial problem, really."
Sherlock Holmes needs to count the number of possible crime scenarios that fit the police evidence. A "scenario" consists of two independent parts: assigning suspects and scheduling actions.
Part 1: There are $$$S$$$ suspects and $$$K$$$ cases. Suspects were assigned to these cases under rigid constraints: every case had at least one suspect, and every suspect was assigned to at least one case.
Part 2: For each of the $$$K$$$ case files, the forensic team has identified exactly $$$L$$$ distinct actions that occurred during the crime. However, the exact order of these actions is not fully known. To model this, the police have represented the $$$L$$$ actions of a single case as a Directed Acyclic Graph (DAG). If there is a directed edge from action $$$u$$$ to action $$$v$$$, it means action $$$u$$$ must happen before action $$$v$$$ in the sequence.The structure of the DAG is identical for all $$$K$$$ cases.The "Global Timeline" consists of all actions from all cases combined.
Global Sequence: You must merge the actions from all $$$K$$$ cases into one single sequence of length $$$N = K \times L$$$. You can interleave actions from different cases however you like, as long as the internal order for each case is preserved.
Calculate the total number of valid scenarios modulo $$$10^9 + 7$$$.A scenario is valid if it satisfies all rules in Part 1 and Part 2.
The first line contains four integers $$$S$$$, $$$K$$$, $$$L$$$, and $$$M$$$ ($$$1 \le S, K \le 10^3$$$, $$$1 \le L \le 20$$$, $$$0 \le M \le \frac{L(L-1)}{2}$$$) — the number of suspects, the number of cases, the number of actions per case, and the number of dependencies in the DAG.The next $$$M$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le L, u \ne v$$$), indicating that action $$$u$$$ must occur before action $$$v$$$.
It is guaranteed that the graph is a Directed Acyclic Graph (DAG).
Output a single integer — the total number of valid scenarios modulo $$$10^9 + 7$$$.
2 2 4 2 1 2 2 3
7840
There are 7 possible ways to assign the suspects :
case 1 $$$.....$$$ case 2
{1,2}$$$....$$$ {1,2}
{1,2}$$$....$$$ {1}——> x2 (switch)
{1,2}$$$....$$$ {2}——> x2
{1}$$$.......$$$ {2}——> x2
for the second part we have : 1—>2—>3 , 4
Therefore, in the final solution, the characteristic sequence of a case can be constructed in 4 ways :
$$$A_1$$$$$$A_2$$$$$$A_3$$$$$$A_4$$$ ; $$$A_4$$$$$$A_1$$$$$$A_2$$$$$$A_3$$$ ; $$$A_1$$$$$$A_4$$$$$$A_2$$$$$$A_3$$$ ; $$$A_1$$$$$$A_2$$$$$$A_4$$$$$$A_3$$$ .
An exemple of the global sequence : $$$A_1$$$$$$B_4$$$$$$B_1$$$$$$A_2$$$$$$B_2$$$$$$A_4$$$$$$A_3$$$$$$B_3$$$
it can be shown that there are 1120 valid configurations .
