## COCI '22 Contest 4 #3 Bojanje

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Oliver is a rubber duck that not only finds bugs, but also likes to paint. His latest painting has parts, each coloured with a unique colour. After he got a lot of critiques that his painting is too predictable, he decided to modify his painting in iterations. In every iteration he will do the following steps:

1. Oliver will select uniformly at random an index , and memorize the colour on the part of the painting.
2. Again, Oliver will select uniformly at random an index . He will repaint the part of the painting with the colour of the part of the painting. If the part is already painted in that colour, there is no change. Note that can be equal to .

Now, Oliver is afraid his painting will become monotonous or boring. He considers a painting good if there are at least different colours on it. Help him calculate the probability that his painting will be good at the end.

#### Input Specification

The first line contains the integers from the task statement, , , and .

#### Output Specification

On the first and only line, output the answer modulo .

Formally, let . It can be shown that the answer can be expressed as an irreducible fraction , where and are integers and . Output the integer equal to . In other words, output an integer such that and .

1 30
2 40

#### Sample Input 1

2 1 2

#### Sample Output 1

500000004

#### Explanation for Sample 1

There are two colours on the painting, so the probability that it remains the same after one iteration is .

#### Sample Input 2

10 2 5

#### Sample Output 2

1

#### Explanation for Sample 2

After two iterations, the number of different colours can't go from to less than , so in every case the painting will have at least different colours.

#### Sample Input 3

3 141592653589793 2

#### Sample Output 3

468261332