题目描述

程老师开了一家小工厂，厂里最宝贝的是一台会造数字的机器。机器是个铁盒子，一侧开着一道进料口，另一侧开着一道出料口，盒子前面并排着两个旋钮，一个标着 k，一个标着 m。这台机器是程老师花大价钱淘来的，厂里好几道工序都指望着它先算个数出来。平时程老师干活，就把一个数字从进料口送进去，机器就开始一项一项地把算好的数字从出料口吐出来，吐出来的数字越堆越多，只要机器不停，就永远没有吐完的那一天。

机器的算法是定死的，从装上那天起就没变过：送进去的那个数，算作它生产出的第 1 项。从第 2 项开始，每一项都由前一项推出来。给定前一项，先把它每一位上的数字都找出来，一位一位加起来，得到一个数，程老师管它叫"数字和"；再把旋钮 k 指着的那个数乘到这个数字和上；最后把旋钮 m 指着的那个数加进去。三步做完，得出来的数就是这一项。也就是说，第 1 项机器照单全收、不做加工，从第 2 项起，才一项接一项地按这套三步算法往下算。算出来的每一项照样是一个数，可以接着当下一项的前一项用，机器从不多想，只管照算法往下推。两个旋钮的取值在一场生产里是固定的，只要不拧它们，k 和 m 就一直是这两个数。

这天程老师干完活，收工前突然想问问机器：照这么一直算下去，第 n 项会是多少？他盯着旋钮上的数字，一时不想自己动手算。请你帮程老师算一算：给定送进机器的数 $a_1$，以及两个旋钮的取值 $k$、$m$，求出机器生产出的第 $n$ 项是多少。算出来的数就是答案，直接报给程老师就行。

输入格式

从文件 factory.in 中读入数据。

一行四个整数 $a_1$、$k$、$m$、$n$，依次表示送进机器的数、旋钮 $k$ 的取值、旋钮 $m$ 的取值，以及要问的是第几项。

输出格式

输出到文件 factory.out 中。

一行一个整数，表示机器生产出的第 $n$ 项。

数据范围

特殊性质 A：序列中首次重复出现的值恰好是 $a_1$。

特殊性质 B：$k = 0$。

对于所有测试点：$1 \le a_1 \le 10^9$，$0 \le k \le 100$，$0 \le m \le 10^6$，$1 \le n \le 10^{18}$。

样例

7 2 1 5

19

10 1 2 100

10

5 0 42 100

42

样例解释

样例 2：从 10 开始按规则逐项计算：10 的数字和是 1，乘 1 加 2 得 3；3 的数字和是 3，得 5；5 得 7；7 得 9；9 得 11；11 的数字和是 2，得 4；4 得 6；6 得 8；8 得 10。前 10 项依次是 10, 3, 5, 7, 9, 11, 4, 6, 8, 10，第 10 项与第 1 项相同。依此规律，第 100 项仍为 10。