문자 a를 포함하는 부분 문자열

면접 대비

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

요약

길이 n인 문자열에서 두 a의 위치 p, q가 주어질 때, a를 하나 이상 포함하는 부분 문자열의 개수를 123456789로 나눈 나머지로 구합니다.

문제

길이가 $n$ 인 문자열 $s$ 에는 문자 a가 2개, 문자 b가 $n-2$ 개 들어 있습니다. 문자열의 길이와 문자 a의 위치가 주어졌을 때, 문자 a를 하나 이상 포함하는 $s$ 의 부분 문자열 개수를 구하는 프로그램 substring을 작성하세요.

표준 입력의 한 줄에 정수 $n$ , $p$ , $q$ 가 순서대로 주어집니다. 여기서 $p$ 와 $q$ 는 문자열에서 문자 a가 있는 위치입니다. $s$ 의 위치는 1, 2, ..., $n$ 으로 번호가 매겨져 있습니다.

구한 개수를 123456789로 나눈 나머지를 표준 출력에 출력하세요.

$1 < n < 10^6$

$1 \le p < q \le n$