0211. Examination

Имя входного файла: a.in
Имя выходного файла: a.out
Ограничение по времени: 2 s
Ограничение по памяти: 64 megabytes

One student has failed his exam. Fairly known story, isn▓t it? It was combinatorics exam and student had the following question:

You have K urns, every urn has Ni balls in it and all balls in all urns are different (i.e. there are no two same balls neither in any of K urns, nor in two different urns). This makes a total of N1+N2+…+NK balls and all of them are different. You are asked to pick M1 balls from the first urn, then M2 balls from the second urn and so on; finally you will pick MK balls from the K▓th urn. The question is: what is the total number of different collections of M1+M2+…+MN extracted balls if the order of extraction is relevant? Remember, that the urns are processed in the predefined ascending order of their numbers; only balls extraction from a particular urn can vary and is relevant.

The student did not manage to solve the problem during allowed time but the teacher was not a villain, so instead of knocking the student out of the university, he made him an offer to calculate this number at home trying all possible ways with real balls and real urns given some fixed K, Ni, Mi. Pretty generous offer I must say┘ see the limits below.

The teacher was not a villain, and the student was not an idiot. Soon he reread his lections and found the formula and also he found that number of digits will be too huge to write it even on a single sheet of paper but he knows that his teacher usually looks only at the end of the answer, so he decides to report only two things in his answer: the number of trailing zeroes and the last non-zero digit of the answer. Well, you are to help him by calculating these things and save one more soul from examination headache.

Input file format

On the first line given a single integer K (0 ≤ K ≤ 1024). Following K lines contain Ni and Mi separated by a single space. Both numbers will fit into signed 64-bit integer and 0 ≤ Mi ≤ Ni, so there is always at least one way to do the extraction.

Output file format

Output first the number of trailing zeroes and then print the last non-zero digit of the answer. Separate these two numbers in the output with a single space.

Example:

a.ina.out
2 7 5 10 3 2 4


Источник: Petrozavodsk Winter 2004. Denis Koshman Contest, Saturday, January 31
Автор: Denis Koshman

Обсудить       Отправить решение



Версия для печати