After collecting a bountiful harvest of nuts to last him throughout the winter, Clifford the Squirrel has decided to make some of them into a necklace so that he can easily carry them around. However, as a fashionable squirrel, he needs help choosing the necklace's design.

Clifford would like to make a necklace consisting of nuts arranged in a single **closed cycle** such that each nut is one of the types that he has collected. Please help him find the number of different necklace designs, modulo , satisfying the following requirements:

- No two adjacent nuts in the design have the same type.
- Necklaces that are rotations of each other count as a single design.

For example, if and , and are valid designs while and are invalid designs under requirement . Also, is the same design as , , and under requirement because they are cyclic shifts of each other.

#### Constraints

For all subtasks:

**It is guaranteed that will not be a multiple of .**

##### Subtask 1 [10%]

##### Subtask 2 [10%]

is guaranteed to be prime.

##### Subtask 3 [30%]

##### Subtask 4 [50%]

No further constraints.

#### Input Specification

The first line will contain two space-separated integers, and .

#### Output Specification

Output one integer, the number of different necklace designs modulo .

#### Sample Input 1

`3 3`

#### Sample Output 1

`2`

#### Explanation for Sample Output 1

The two valid designs are and . Note that all other valid arrangements are just rotations of these designs. For example, is a rotation of .

#### Sample Input 2

`5 4`

#### Sample Output 2

`48`

#### Sample Input 3

`8 6`

#### Sample Output 3

`48915`

## Comments

>:(