Combinatorial Expression |
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 :
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.
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.
For each test case show the result in a line as specified in the problem statement.
3 3 10 5 10 4 10 3 10 7 10 6 10 5 3 3 10 5 10 4 10 3 10 7 10 6 10 1 3 3 10 5 10 4 10 3 10 7 10 6 10 10 4 1 10 5 10 5 10 5 10 5 100 100
1 0 252 4032758016
Md. Kamruzzaman