같은 자릿수

십진 숫자로 이루어진 문자열 $s$가 있다.

문자열 $s$를 모든 자릿수가 서로 다른 비어 있지 않은 문자열 $t$로 바꾸려고 한다. 이를 위해 서로 겹치지 않는 부분 문자열들을 골라 지울 수 있다. 고른 집합은 비어 있어도 되고, 각 부분 문자열의 길이는 $1$보다 커야 하며, 각 부분 문자열에서 첫 자릿수와 마지막 자릿수가 같아야 한다. 이러한 집합을 고르는 경우의 수를 구하라.

두 집합이 다르다는 것은 한 집합에는 있고 다른 집합에는 없는 부분 문자열이 존재한다는 뜻이다. 부분 문자열은 시작 위치나 끝 위치가 다르면 서로 다른 것으로 본다.

경우의 수가 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

한 줄에 문자열 $s$가 주어진다. ($1 \le |s| \le 10^5$) $s$는 십진 숫자로 이루어져 있다.

문제의 답을 정수 하나로 출력한다.