- All Contests
- ProjectEuler+
- Project Euler #190: Maximising a weighted product

# Project Euler #190: Maximising a weighted product

# Project Euler #190: Maximising a weighted product

_{This problem is a programming version of Problem 190 from projecteuler.net}

Let be the -tuple of positive real numbers with for which is maximised.

For example, it can be verified that .

Let's make a generalization of . Let (where is a natural number and is an -tuple of natural numbers) be the -tuple of positive real numbers with for which is maximised.

It's easy to see that .

You're given three natural numbers: , and . Find the sum of among all with modulo . It is guaranteed that in every test case this sum could be represented as a rational fraction with a denominator not divisible by .

**Definitions**

In this problem it is considered that set of natural numbers does not include .

If we have some rational number where is integer and is natural, then where is a modular multiplicative inverse.

**Input Format**

The only line of each test case contains exactly three integers separated by single spaces: , and .

**Constraints**

**Output Format**

Print exactly one number which is the answer to the problem modulo .

**Sample Input**

```
6 3 2
```

**Sample Output**

```
64
```

**Explanation**

There are two ways to represent as a sum of two ordered natural numbers: and . , thus the answer is .