K번째 자리 숫자

X = A + √B이고 |A - √B| < 1일 때, N이 10^9까지, K가 4까지 주어질 때 floor(X^N)의 K번째 최하위 자릿수를 구한다.

보통7수학정수론행렬동적 계획법아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제 설명

예제4

문제

실수 $X$ 가 $X = A + \sqrt{B}$ 꼴로 주어진다. $A$ 와 $B$ 는 양의 정수이고 $-1 < A - \sqrt{B} < 1$ 을 만족한다. 정수 $N$ 과 $K$ 가 함께 주어질 때, $\lfloor X^N \rfloor$ 의 아래에서 $K$ 번째 자리 숫자를 구하여라. 예를 들어 $K = 1$ 이면 $\lfloor X^N \rfloor$ 의 일의 자리 숫자를 구하면 된다. $\lfloor X^N \rfloor$ 의 자릿수가 $K$ 보다 적으면 $K$ 번째 자리 숫자는 0으로 본다.

입력

첫째 줄에 정수 $A$ , $B$ , $N$ , $K$ 가 공백으로 구분되어 주어진다. $1 \le A, B \le 10^4$ , $1 \le N \le 10^9$ , $1 \le K \le 4$ 이고, 입력은 항상 $-1 < A - \sqrt{B} < 1$ 을 만족한다.

출력

$\lfloor X^N \rfloor$ 의 아래에서 $K$ 번째 자리 숫자를 한 줄에 출력한다.