문제 보기 - 팩토리얼 세제곱들의 합 (YDX14_fact)

시간 제한 메모리 제한 제출 횟수 통과한 사람 수 비율
1000 ms 256 MiB 57 15 26.32%

승현이는 최근 정수 $n$의 팩토리얼은 $1$ 이상 $n$ 이하의 모든 양수들의 곱이라는 것을 배웠습니다. $n$의 팩토리얼은 "$n!$"로 나타냅니다. 그래서, 예를 들어, $1! = 1$, $2! = 1 \times 2 = 2$, $3! = 1 \times 2 \times 3 = 6$. 정의에 따라, $0! = 1$입니다.

승현이는 작은 정수들의 팩토리얼을 계산하는 것을 좋아했습니다. 그러나, 그는 10보다 큰 정수들의 팩토리얼은 손으로 계산하기가 어렵다는 것을 이해하게 되었습니다. 그래서 그는 아주 적은 뒷자리들만 계산하기로 마음을 먹었으나, 곧 이것들이 종종 0들로만 구성되어 있다는 것도 알게 되었습니다. 예를 들어, 만약 그의 계산이 정확했다면, $25!$의 마지막 여섯 자리는 모두 0입니다. $n!$의 0이 아닌 마지막 자리수를 찾는 것은 매우 흥미로운 문제였고, 승현이는 이를 쉽게 풀어냈습니다.

승현이의 수학 선생님은 이러한 승현이의 성공에 감동을 받아 그에게 더 어려운 문제를 주었습니다: "$0$ 이상 $n$ 이하의 모든 정수들의 팩토리얼의 $k$제곱을 합한 값의 0이 아닌 마지막 숫자를 구하세요." $k$는 음이 아닌 정수입니다. 승현이는 6학년이므로, 선생님은 이 문제를 $k \le 3$이고 $n \le 100$인 경우에 대해서만 해결하라고 합니다. 그러나 이 문제를 손으로 풀기 위해서는 많은 힘든 계산을 필요로 합니다...

승현이가 이 문제를 푸는 프로그램을 작성하는 것을 도와줍시다. $n$과 $k$가 주어질 때, $0$ 이상 $n$ 이하의 모든 정수들의 팩토리얼의 $k$제곱의 합의 0이 아닌 마지막 자리(..)를 구하는 프로그램을 작성하세요.

편집자 주: $\sum_{i=0}^{n} (i!)^k$의 0이 아닌 마지막 자리를 구하면 됩니다.

입력 형식

첫 번째 줄에 양수 $n$ ($n \le 100$)과 음이 아닌 정수 $k$ ($k \le 3$)가 주어집니다.

출력 형식

위에서 기술한 답을 출력합니다.

예제

입력 출력
4 1 4
3 2 2
문제 내용 수정하기