십진법으로 표현된 정수 $N$이 주어집니다.
$N$의 자릿수들을 재배열하여 만들 수 있고 맨 앞에 불필요한 $0$(leading zeros)이 없는 모든 정수를 생각해 봅시다.
이러한 정수들 중 $11$로 나누어떨어지는 것의 개수를 소수인 $2147483647$ ($= 2^{31} - 1$)로 나눈 나머지를 구하세요.
$N$의 자릿수들을 재배열하여 만든 정수에는 $N$ 자신도 포함됨에 유의하세요.
입력
입력은 다음 형식으로 주어집니다:
$$N$$
- 모든 입력값은 정수입니다.
- $1 \le N < 10^{2 \times 10^6}$
- $N$은 맨 앞에 불필요한 $0$이 없는 십진법으로 주어집니다.
출력
정답을 한 줄에 출력합니다.
예제
예제 입력 1
1001
예제 출력 1
2
예제 입력 2
31415926535
예제 출력 2
144000
노트
첫 번째 예제에서는 $1100$과 $1001$이 조건을 만족합니다.