Dado um número real X da forma A + √B, com A e B inteiros positivos e −1 < A − √B < 1, e dois números inteiros N e K, sua tarefa é determinar o K-ésimo dígito menos significativo da parte inteira de X^N. Por exemplo, se K = 1, você precisa determinar o algarismo das unidades de ⌊X^N⌋.

입력 형식

A entrada consiste de uma única linha, que contém quatro números inteiros, A, B, N e K, com 1 ≤ A, B ≤ 10⁴, 1 ≤ N ≤ 10⁹ e 1 ≤ K ≤ 4.

출력 형식

Seu programa deve imprimir uma única linha, contendo o K-ésimo dígito menos significativo da parte inteira de X^N.

예제 입력 1

3 10 1 1

예제 출력 1

6

예제 입력 2

3 10 2 1

예제 출력 2

7

예제 입력 3

3 10 1000000000 1

예제 출력 3

1

예제 입력 4

10 90 1000000000 2

예제 출력 4

9