派蒙的算术总是很差，因此常常算不对香菱的烧烤一共卖了多少钱。

旅行者 orz 决定教教派蒙算术，旅行者给了派蒙两个数字，x 和 y，他让派蒙给 x 增加 1，然后尝试用 y 去整除 x，如果可以整除，则 x 一直除以 y，直到无法整除。

以上过程算一次操作，现在最多可以执行 k 次操作，最后 x 会变成多少，派蒙绞尽脑汁都没法算出正确答案，你能算出来吗。

对于 30% 的数据,1≤x≤100，2≤y≤100，1≤k≤10。

对于 100% 的数据，1≤x≤10^9，2≤y≤10^9，1≤k≤10^9。