In combinatorics the term mainly used is nCr which literally means the number of ways r things can be taken from n things. Mathematically nCr is defined as : C= N! (N −R)!×R! A combinatorial expression may involve many such terms with arithmatic operators. In this problem you have to evaluate a combinatorial expression involving only multiplication and division of nCr. Here a combinatorial expression has two parts. One is numerator and the other is denominator. Both consist of as a mutiplication of several nCr’s or a single nCr. A simple expression could be : nCr ∗ nCr/nCr. You have to determine whether the expression produces an integer result (The numerator is divisible by the denominator). If so then you have to show the result only when the number of digits in the result is less than 101 otherwise just print ‘-1’. If not divisible then print zero only. Input The input will start with two positive integer, N and M (N, M ≤ 100). Each of the following N + M lines will contain two integers (n and r). The first 2 ∗ N integers will make the numerator and the next 2 ∗ M integers will make the denominator. It is guranteed that no invalid nCr will be present (0 ≤ r ≤ n ≤ 5000). Input will be terminated by EOF. Output For each test case show the result in a line as specified in the problem statement. Sample Input 33 10 5 10 4 10 3 10 7 10 6 10 5 33 10 5 10 4 10 3 10 7 10 6 10 1 33 10 5 10 4 10 3
2/2 10 7 10 6 10 10 41 10 5 10 5 10 5 10 5 100 100 Sample Output 1 0 252 4032758016