Cow Brainiacs

시간 제한1초메모리 제한1024 MB

요약

N이 200만 이하이고 B가 2에서 29일 때, N!을 B진법으로 쓴 뒤 가장 오른쪽에 있는 0이 아닌 자릿값을 구한다.

난이도: 보통10점 중 6점
유형: 수학, 정수론, 구현
정답자: 아직 제출이 없습니다

문제

One afternoon as the cows were chewing their cud, Bessie said, "Let's have a contest to see who is the smartest cow. Here's the contest: we will choose a positive number N (no larger than 2,000,000) and whoever computes the rightmost non-zero digit of N factorial will be crowned the smartest cow."

The other cows demurred, however, mooing, "We did that last year."

"Oh," said Bessie, "but there's a catch. We're not necessarily going to use base 10. I know my hooves don't have that many digits! We'll just specify a positive number base B from 2 through 29."

Write a program to help the cows judge their intelligence contest.

입력

A single line with integers N and B

출력

A single line with the decimal-representation of the "digit" that is the rightmost non-zero digit for N! in base B. If B > 10, go ahead and output a two-digit decimal number as a representation of the final "digit".

힌트

13*12*11*10*9*8*7*6*5*4*3*2*1=6227020800 base 10, which in base 3 is 121001222020102200000, so the right-most non-zero digit is 2.

예제1

예제 1
입력
```
13 3
```
예상 출력
```
2
```