시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 37 13 12 38.710%

문제

이 문제에서 자연수 하나를 숫자들의 수열로 나타낼 수 있다고 한다. 마찬가지로 숫자로 이루어진 수열을 자연수 하나로 표현할 수 있다. 하지만 leading zeros (맨 앞의 0)은 허용하지 않는다. 예를 들어 N = 2090 일 때, 수열 {2, 0, 9, 0}이 된다. 하지만 수열 {0, 0, 1, 0}이 의미하는 자연수는 없다.

수열의 Anagram이란 수열의 원소 구성은 같으면서 순서만 바뀐 것을 의미한다. 마찬가지로 자연수의 Anagram도 정의할 수 있다. N = 2090 일 때, N의 Anagram은 2009, 2090, 2900, 9002, 9020, 9200이 된다.

자연수 N이 주어졌을 때, N의 Anagram 중 11의 배수가 되는 것이 몇 개나 있는지 궁금하다. 이를 계산하는 프로그램을 작성하자. 예를 들어, N = 2090 일 때 Anagram 중 2090 과 9020 만이 11의 배수이기 때문에 답은 2가 된다.

입력

첫 줄에 자연수 N이 leading zeros 없이 주어진다. (1 ≤ N ≤ 10100)

출력

주어진 자연수 N의 Anagram 중 11의 배수의 개수를 출력한다. 단, 답이 매우 클 수 있으므로 109 + 7로 나눈 나머지를 출력한다.

예제 입력

2090

예제 출력

2

힌트