_{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.