Floor of Power Expression Modulo p

Given three non‐negative integers b, d and n, compute

$$\left\lfloor \left(\frac{b+\sqrt{d}}{2}\right)^n\right\rfloor \bmod p,$$

where p is a fixed prime number: $$p=7\,528\,443\,412\,579\,576\,937.$$

You may assume that the input is such that the precision issues can be handled using high-precision arithmetic (e.g. the value of n is moderate). In other words, it is guaranteed that the computed answer does not suffer from rounding problems when using an appropriate high‐precision arithmetic library.

Note: The expression \(\frac{b+\sqrt{d}}{2}\) is computed in real numbers; then its n-th power is taken, the floor is applied, and finally the result is taken modulo \(p\).

inputFormat

The input consists of a single line with three non‐negative integers b, d, and n separated by spaces.

Constraints: It is guaranteed that n is moderate enough to allow high‐precision power computation.

outputFormat

Output a single integer representing
$$\left\lfloor \left(\frac{b+\sqrt{d}}{2}\right)^n\right\rfloor \bmod p.$$

sample

1 4 2

2