By XIII Maratona de Programação IME-USP, 2009 Brazil
We are in 2433 and the Pythanic spaceship has just been launched with the first group of humans to inhabit another planet. This journey has been long awaited since the life conditions on Earth became extremelly difficult after a failed attempt of a terrorist to exterminate the human race using mutant bacteria, about 400 years ago. Once the bacteria were very poorly made, with a lot of last minute kludges, the only thing he achieved was a terrible stench in the environment.
Before the beginning of the journey, some decisions had to be taken with respect to the way of life that these people would take on the other planet. One of those decisions was that the duration of a day would be the same in all planets inhabited by humans, that is, the word "day" becomes simply a term that means "24 hours" and no more a term that specifies a complete rotation of the planet around itself. However, it was decided that the duration of the month may vary from planet to planet. Worried about the confusion it could generate, the analists from the interplanetary colonization comittee asked you to create a program that, given the duration of the months (in days) in two different planets, say how much different combinations of pairs (D1, D2) exist, where D1 is a day on planet 1 and D2 is a day on planet 2 (not necessarilly days of the same month). You may assume that the first day 1/1 (the first day of the year) occurs at the same time on both planets.
For example, if a planet has 2 days in a month and the other has 3, we'll have 6 different day combinations: (1,1), (2,2), (1,3), (2,1), (1,2) and (2,3). If a planet has 4 days in a month and the other has 2, there will be only 4 combinations: (1,1), (2,2), (3,1) and (4,2).
Given D1 and D2, your program must determine how many combinations exist.
The input contains various instances.
Each instance is composed by only one line containing two integers D1 and D2 (1 ≤ D1, D2 ≤ 1.000.000.000), that correspond to the number of days in a month on the two different planets. The input finishes then D1 = D2 = 0.
For each instance of the input, print a line containing the number of different day combinations between the two planets.
The answer must be given in modulo 1713371337.
|Sample Input||Sample Output|