B'A year ago on the bench in public park Leha found an array of n numbers. Leha believes that permutation p is right if for all 1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89i xe2 x80 x89< xe2 x80 x89n condition, that api xc2 xb7api xe2 x80 x89+ xe2 x80 x891 is not perfect square, holds. Leha wants to find number of right permutations modulo 109 xe2 x80 x89+ xe2 x80 x897. First line of input data contains single integer n (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89300) -- length of the array. Next line contains n integers a1, xe2 x80 x89a2, xe2 x80 x89... , xe2 x80 x89an (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ai xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89109) -- found array. Output single integer -- number of right permutations modulo 109 xe2 x80 x89+ xe2 x80 x897. For first example: [1, xe2 x80 x892, xe2 x80 x894] -- right permutation, because 2 and 8 are not perfect squares. [1, xe2 x80 x894, xe2 x80 x892] -- wrong permutation, because 4 is square of 2. [2, xe2 x80 x891, xe2 x80 x894] -- wrong permutation, because 4 is square of 2. [2, xe2 x80 x894, xe2 x80 x891] -- wrong permutation, because 4 is square of 2. [4, xe2 x80 x891, xe2 x80 x892] -- wrong permutation, because 4 is square of 2. [4, xe2 x80 x892, xe2 x80 x891] -- right permutation, because 8 and 2 are not perfect squares. '...