어려운 비밀번호

학생들이 강력한 로그인 비밀번호를 쓰도록 강좌 팀이 클러스터에 비밀번호 복잡도 정책을 설정했다. 학기 초에 수강 학생 모두에게 무작위로 생성된 초기 비밀번호가 지급된다. 학생이 초기 비밀번호로 로그인하면 클러스터는 새 비밀번호를 입력하라고 요구한다. 비밀번호를 바꾼 뒤에야 클러스터에 접속할 수 있다. 이 문제는 다음 정책을 사용한다.

• 비밀번호는 최소 $L$자 이상이어야 하며, 숫자와 영문자를 각각 하나 이상 포함해야 한다.
• 같은 문자가 $A$개 연속으로 나오면 안 된다. 예를 들어 2333에는 같은 문자가 세 개 연속으로 들어 있다.
• 오름차순 또는 내림차순을 이루는 문자가 $B$개 연속으로 나오면 안 된다. 오름차순은 0123456789, ABCDEFGHIJKLMNOPQRSTUVWXYZ, abcdefghijklmnopqrstuvwxyz 중 하나의 연속된 부분 문자열이다. 내림차순은 이 세 문자열 중 하나의 연속된 부분 문자열을 거꾸로 읽은 것이다. 예를 들면 다음과 같다.
  • 6789는 길이 4인 오름차순이고, FED는 길이 3인 내림차순이다.
  • 90, AZ, az는 오름차순도 내림차순도 아니다.
  • GPU는 문자가 연속되지 않아서 오름차순이 아니다.
  • Def는 대소문자가 섞여 있어서 오름차순이 아니다. 다만 길이 2인 연속 오름차순 ef를 부분 문자열로 포함한다.
  • 1112345678999는 오름차순이 아니지만, 부분 문자열 123456789는 오름차순이다.

비밀번호는 숫자와 대소문자 영문자로만 이루어진다. 이 정책을 만족하면서 길이가 $R$ 이하인 비밀번호의 개수를 구하라. 개수가 매우 클 수 있으므로 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

한 줄에 양의 정수 $L$, $R$, $A$, $B$가 차례로 주어진다 ($1 \le L \le R \le 10^9$; $2 \le A \le 6$; $2 \le B \le 26$).

정책을 만족하고 길이가 $R$ 이하인 비밀번호의 개수를 $1\,000\,000\,007$로 나눈 나머지를 한 줄에 출력한다.

예제 1에서 비밀번호에는 숫자와 영문자가 각각 하나 이상 있어야 한다. 따라서 유효한 비밀번호는 $2 \cdot 10 \cdot (26 \cdot 2) = 1040$개다.