## LCC '22 Contest 2 S5 - Nutty Necklaces

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 64M
Python 128M

Author:
Problem types

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:

1. No two adjacent nuts in the design have the same type.
2. 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

It is guaranteed that will not be a multiple of .

is guaranteed to be prime.

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