시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB46302257.895%

문제

Даден е низ s с дължина n, съдържащ две букви а и n–2 букви b. Напишете програма substring, която по дадени дължината на низа и позициите на буквите а, намира броя на поднизовете на s, които съдържат поне една буква а.

입력

От единствения ред на стандартния вход се въвеждат числата n, p и q, където p и q са позициите на буквите а в низа. Позициите в низа s имат номера 1,2, …, n.

출력

На стандартния изход да се изведе остатъкът при делението на търсения брой на числото 123456789.

제한

  • 1 < n < 106
  • 1 ≤ p < q ≤ n

예제 입력 1

7 2 5

예제 출력 1

21