Cerința

Se dă a, b și c, să se calculeze \({a}^{{b}^{c}}\) modulo \({10}^{9}+7\).

Date de intrare

Programul citește de la tastatură numerele a, b, c.

Date de ieșire

Programul va afișa pe ecran numărul X, rezultatul calculului \({a}^{{b}^{c}}\) modulo \({10}^{9}+7\).

Restricții și precizări

• 1 ≤ a, b, c ≤ 1.000.000.000.

Exemplu:

Intrare

3 4 2

Ieșire

43046721

Explicație

\(4^2 = 16\). \(3^{16}=43046721\).