All submissions for this problem are available.
Indian RAW maintains a track of all its Secret Agents spread across the globe, by maintaining a list of their Fake names in the order of the riskiness
of their place of posting. All names are distinct and each name is composed of only lowercase letter ('a'-'z'). The RAW agent, Charlie, who keeps this list secretive, is one day assigned the task of keeping a backup of this list in his
brain memory so that the security is not compromised in case of any cyber attack on the computer database and the original database can be automatically
erased. However Charlie employs a faulty retention method which is as follows:
Charlie remembers two lists memory1 and memory2 such that for each valid index k, memory1[k]th (0-indexed) name in the list is a prefix of the memory2[k]th name. Charlie might have missed to remember some possible such pairs. However with such a brain memory retention technique, there are a lot of possible orderings that can arise.
Let Y be the number of different orderings possible of original list consistent with Charlie's memory . Output Y modulo 1,000,000,007 given the shuffled list of Fake names and the two memory lists. If Charlie's memory is inconsistent then Y will be 0.
- The first line of test case contains a single integer N denoting the number of names. The second line contains N space-separated names A0, A1, A2,...... AN-1.
- Next line contains a single integer M denoting the number of elements in each array memory1 and memory2. The next two each line contains M space-separated integers denoting the elements of memory1 and memory2.
- Output Y
Should contain all the constraints on the input data that you may have. Format it like:
- 2 ≤ N ≤ 50
- 0 ≤ M ≤ 8
- 1 ≤ length of each name ≤ 50
Input: 4 marc marco marcol marcpolo 2 0 0 1 2 Output: 6
Input: 3 alpha marco tango 2 0 1 1 0 Output: 0
Input: 3 alpha alp alphabeta 0 Output: 6
Example case 1.
According to charlie 0th name is the prefix of 1st and 2nd name. "marc" has to be the first name.
Example case 2.
According to charlie 0th name and 1st are prefix of each other which is only possible if both the names are same but all names should be distinct. Incosistent memory.
Example case 3.
Charlie failed to remember anything.
|Time Limit:||2 - 3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.