Feathers on the Shaman's Head#4335
The Shaman of Decorations, Paueokunyatl, adorns his head with feathers, initially numbered from to . Each morning, he rearranges these feathers according to a specific ritual, applying a fixed permutation.
On certain days, after performing feats, the Wise Chipmunk records the arrangement of the feathers in his stories.
Your task is to determine how many different rituals (permutations) are consistent with the given descriptions.
The first line of input contains two integers and (1 \leq n \leq 10000, 1 \leq m \leq 10)—the number of feathers on Paueokunyatl's head and the number of feats he performed.
Each of the next lines provides a number d_i (1 \leq d_i \leq 10^9) and a permutation of numbers from to . This indicates that on the d_i-th day, after performing his morning ritual exactly d_i times, the feathers were arranged in the specified order.
Print the number of rituals that match the given descriptions, modulo "ten hundred hundred hundred and a dozen less three".
Example 1