As a fashionista, you own distinct outfits. You plan to wear one of them each day for the next days.
Only outfits for a fashionista? Do not worry: you have thought this through.
You will not show the people you meet today an outfit they have seen you wear during the previous days. For each day, you have therefore listed the days within that period on which the people you will meet saw what you were wearing.
For day , you are given day offsets . You want the outfit you wear on day to differ from the outfit worn on each of the specified days . For example, if and , you cannot wear the outfit from yesterday or the outfit from three days ago.
You cannot wear an outfit that you wore on any of the specified days. You are free to wear any other outfit, since the people you will meet have not seen you wear it during the relevant period.
Find the number of outfit plans satisfying these conditions, modulo . Two plans are different if the outfits worn differ on at least one day.
The first line contains the number of days to plan for.
The next lines describe days through in order. The line for day contains an integer , followed by integers , separated by spaces. If , the line contains only .
Print the number of outfit plans satisfying the conditions, modulo .
In the first example, the numbers of choices on successive days are , , , , and , so the answer is .
In the second example, there are plans in which the same outfit is worn on days and . There are plans in which different outfits are worn on those days, giving a total of .
In the third example, if the same outfit is worn on the first two days, there are choices for day . If different outfits are worn, there are choices for day . Thus, the answer is .