Hôm nay là sinh nhật của flo nên cậu đã được mẹ cậu thưởng \(n\) hộp kẹo với vô vàn loại kẹo khác nhau. Những hộp kẹo này còn có cho mình \(1\) độ ngon nhất định khi hộp thứ \(i\) có độ ngon là \(a_i\). Tuy nhiên nếu ăn hết bây giờ thì sẽ quá lãng phí nên flo quyết định ăn \(n\) hộp kẹo này trong những ngày tới. Mỗi ngày, cậu sẽ chọn \(1\) số nguyên dương \(m\) bất kỳ và ăn \(m\) viên kẹo đầu tiên sao cho độ phong phú của \(m\) hộp kẹo đó giao động từ \(l\) đến \(r\). Đối với flo, độ phong phú của một dãy hộp kẹo là số lượng độ ngon khác nhau của các hộp kẹo đó. Khi ăn như vậy sẽ giúp cậu có thể cảm nhận được sự hòa quyện của các loại kẹo với nhau, từ đó tạo nên một vị ngon khó cưỡng.

Vì là một con người coi trọng việc tiết kiệm, flo muốn ăn theo cách trên nhưng cậu phải ăn hết kẹo mà không chưa lại hộp kẹo nào. Tuy nhiên do số lượng hộp kẹo mà mẹ của flo tặng cho cậu quá lớn làm cho cậu không biết phải phân chia để ăn như thế nào mới có thể thỏa mãn được cậu. Bạn hãy tính giúp flo nhé.

Input

• \(3\) số nguyên dương \(n, l, r\) \((1 \le l \le r \le n \le 10^5)\).
• Dãy \(a\) gồm \(n\) phần tử \(a_1, a_2, ..., a_n\) \((1 \le a_i \le 10^9)\).

Output

• In ra kết quả sau khi chia lấy dư cho \(1234567891\).

Scoring

• Subtask \(1\) \((10\%)\): \(1 \le n \le 10\).
• Subtask \(2\) \((20\%)\): \(1 \le n \le 10^2\).
• Subtask \(3\) \((30\%)\): \(1 \le n \le 10^3\).
• Subtask \(4\) \((40\%)\): Không giới hạn gì thêm.

3 1 2
2 3 2

4

6 2 4
1 2 1 3 2 2

3

Nguồn: TLEoj - Bedan Contest #03