평범한 승차권

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

요약

길이 2N인 티켓 문자열에서 물음표를 0부터 9까지 채울 때, 앞 절반의 곱과 뒤 절반의 곱이 같은 경우와 다른 경우의 수를 각각 구한다.

난이도: 보통10점 중 7점
유형: 조합론, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

표트르(Peter)는 정수론을 좋아해서 흥미로운 버스 승차권을 찾아다닌다. 길이가 $2N$ 인 번호가 적힌 승차권에서, 앞쪽 $N$ 개 숫자의 곱과 뒤쪽 $N$ 개 숫자의 곱이 같으면 그 승차권을 흥미로운(interesting) 승차권이라 부르고, 그렇지 않으면 평범한(banal) 승차권이라 부른다.

표트르는 주머니에서 사용한 승차권 한 장을 발견했다. 그런데 승차권에 구멍이 뚫려 일부 숫자를 알아볼 수 없다. 그는 이 승차권이 흥미로운 승차권이었는지 궁금하다. 나아가, 구멍이 뚫린 자리를 채워서 만들 수 있는 서로 다른 흥미로운 승차권과 평범한 승차권이 각각 몇 가지인지 알고 싶다.

알아볼 수 없는 각 자리에는 숫자 $0$ 부터 $9$ 까지 중 어느 것이든 들어갈 수 있으며, 각 자리를 독립적으로 채운다. 채운 결과로 만들어지는 서로 다른 승차권의 개수를 세어 표트르를 도와라.

입력

첫째 줄에 정수 $N$ ( $1 \le N \le 18$ )이 주어진다. 둘째 줄에 승차권 번호를 나타내는 길이 $2N$ 의 문자열이 주어진다. 구멍이 뚫려 알아볼 수 없는 자리는 ?로 표시하고, 그렇지 않은 자리는 해당 숫자 그대로 표시한다.

출력

첫째 줄에 흥미로운 승차권의 개수를, 둘째 줄에 평범한 승차권의 개수를 출력한다.

예제4

예제 1
입력
```
2
2??3
```
예상 출력
```
4
96
```
예제 2
입력
```
1
55
```
예상 출력
```
1
0
```
예제 3
입력
```
1
??
```
예상 출력
```
10
90
```
예제 4
입력
```
2
1234
```
예상 출력
```
0
1
```