首先，

禁止打表！！！

问题描述

小C是名小学生，小学生就要接受奥数的洗礼。果然，老师又要迫害小C了。

老师问，已知$a+b=5$,$ab=3$,那$a^2+b^2$是多少？

小C立刻报出了答案$(a^2+b^2=(a+b)^2-2ab=19)$，但老师又问：

如果已知$s=a+b$ 和 $p=ab$，求$a^n+b^n$，你会求吗？

小C当然不会求，可“好心”的老师把这道题布置成了课后习题，你能帮帮小C吗？
😭😭😭😭😭😭😭😭😭😭😭

输入格式

共一行，有3个数，是$s、p、n$，意义如题所述。

输出格式

一个整数，代表$a^n+b^n$。

输入样例

5 3 5

输出样例

1475

数据范围

$1<=n<=50$
$1<=s<=10$
$1<=p<=10$