This problem is a programming version of Problem 182 from projecteuler.net
The RSA encryption is based on the following procedure:
Generate two distinct primes and .
Compute and .
Find an integer , , such that .
A message in this system is a number in the interval .
A text to be encrypted is then somehow converted to messages (numbers in the interval ).
To encrypt the text, for each message, , is calculated.
To decrypt the text, the following procedure is needed: calculate such that , then for each encrypted message, , calculate .
There exist values of and such that .
We call messages for which unconcealed messages.
An issue when choosing is that there should not be too many unconcealed messages.
For instance, let and .
Then and .
If we choose , then, although it turns out that all possible messages () are unconcealed when calculating .
For any valid choice of there exist some unconcealed messages.
It's important that the number of unconcealed messages is at a minimum.
For given and find the sum of all values of , and , so that the number of unconcealed messages for this value of is at a minimum.
Input Format
Every test case contains a single line with two integers separated by a single space: and .
Constraints
and are distinct primes.
.
But for more than half of tests .
Output Format
Output the sum of all values of for which the number of unconcealed messages is at a minimum. As this number may be huge, output it modulo .
Sample Input
11 13
Sample Output
438
Explanation
The needed values of are , , , , and which give us only unconcealed messages.