The Alchemist provides you some very easy sequences:
Sequence 1: 2, 3, 5, 7, 11, 13. . . .
Sequence 2: 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1 . . .
Sequence 3: 4, 6, 12, 18, 30, 42, 60, 72 . . .
Sequence 4: 6, 14, 36, 98, 276 . . .
Sequence 5: 23, 21, 24, 19, 26, 15, 28, 11, 30, 7, 36 . . .
Given sequence id and a positive integer N, find the term of required series modulo
Input:
There is only one line in test file containing 2 space separated integers denoting sequence id and N.
Output:
For each test case, output the term of required series.
Constraints: