ПОДНИЗОВЕ

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

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

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

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