ПОДНИЗОВЕ
시간 제한1초메모리 제한1024 MB
길이 n인 문자열에서 p번째와 q번째 문자가 'a'이고 나머지가 'b'일 때, 'a'를 하나 이상 포함하는 부분 문자열의 개수를 123456789로 나눈 나머지를 구한다.
문제
Даден е низ s с дължина n, съдържащ две букви а и n–2 букви b. Напишете програма substring, която по дадени дължината на низа и позициите на буквите а, намира броя на поднизовете на s, които съдържат поне една буква а.
입력
От единствения ред на стандартния вход се въвеждат числата n, p и q, където p и q са позициите на буквите а в низа. Позициите в низа s имат номера 1,2, …, n.
출력
На стандартния изход да се изведе остатъкът при делението на търсения брой на числото 123456789.
제한
- 1 < n < 106
- 1 ≤ p < q ≤ n