Feather on the Shaman's Head
The Shaman of Decorations, Paueokunyatl, adorns his head with n feathers, initially numbered from 1 to n. 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.
Input
The first line of input contains two integers n and m (1 ≤ n ≤ 10000, 1 ≤ m ≤ 10)—the number of feathers on Paueokunyatl's head and the number of feats he performed.
Each of the next m lines provides a number d_i (1 ≤ d_i ≤ 10^9) and a permutation of numbers from 1 to n. 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.
Output
Print the number of rituals that match the given descriptions, modulo "ten hundred hundred hundred and a dozen less three".