N Pearls Necklace
Statement
Goal
Mr. Burn and Mr. Side work in a necklace shop.Mr. Burn makes the necklaces and Mr. Side sells them.
The necklaces are made with pearls of identical radius.
Sometimes, Mr. Burn launches a new collection: he chooses a panel of colors and a number of pearls and creates necklaces with these constraints.
Mr. Side is very dedicated to his job and whenever a new collection is launched, he displays all possible necklaces that follows the constraints of the collection in a glass case to offer the widest choice to the customers.
The necklaces are circular and reversible so the necklaces
Also note that all colors of the panel must be used at least once.
For example if the constraints of the collection are:
number of pearls: 5 pearls
panel of colors: black and white,
then there are only 6 different necklaces:
To help Mr. Side evaluate the size of the glass case, you must output the number of different necklaces for a given collection.
Input
Line 1: An integer N for the number of pearls.
Line 2: An integer C for the number of colors in the panel.
Line 2: An integer C for the number of colors in the panel.
Output
Line 1: The number of different necklaces for a given collection.
Constraints
1 ≤ C ≤ N ≤ 30
Example
Input
5 2
Output
6
Tags
Group theory, Arithmetic
Difficulty
Hard
Test cases
Test 1 Test
Input
5
2
Output
6
Validator 1 Validator
Input
4
2
Output
4
Test 2 Test
Input
5
3
Output
18
Validator 2 Validator
Input
7
2
Output
16
Test 3 Test
Input
6
3
Output
56
Validator 3 Validator
Input
12
2
Output
222
Test 4 Test
Input
23
3
Output
2046303339
Validator 4 Validator
Input
19
4
Output
7111777860
Test 5 Test
Input
24
4
Output
5840547488954
Validator 5 Validator
Input
20
5
Output
2247627076731
Solution language
Solution
Stub generator input