Програмчлалын олимпиадын бодлогын архив

Ахмад Джек нууц эрдэнэсийн агуйд ортол тэнд n ширхэг авдар байжээ. Авдар бүр өөр өөрийн өнгөтэй сувдаар дүүрэн байсан (нэг авдарт байгаа сувднууд адил өнгөтэй, өөр авдарт байгаа сувднууд ялгаатай өнгөтэй). i-р авдарт m_i ширхэг сувд байна. Тэр дор хаяж a ширхэг сувд авч явахыг хүсч байгаа ба b-гээс олон сувд даахгүй. Ингээд Джек хэдэн ширхэг, хэдэн өнгийн сувд авч явахыгаа шийдэж чадахаа байжээ. Тэр хэдэн янзаар сувдуудыг авч явж чадах вэ?
Дараах үйлдлүүдийг гүйцэтгэх програм бич:
- оролтоос авдар бүрт байх сувдны тоо болон a, b тоог унших
- Джек хэдэн янзаар сувднуудыг сонгон авч явж болохыг тооцолох
- үр дүнг гаргах

Input

Оролтын эхний мөрөнд n, a, b бүхэл тоонууд зайгаар тусгаарлагдан байрлана (1<=n<=10, 0<=a<=b<=10 000 000). Дараагийн n ширхэг мөр тус бүрд нэг бүхэл тоо байна. i+1-р мөрөнд байгаа бүхэл тоо нь m_i буюу i-р авдранд байх сувдны тоог илэрхийлнэ (0<=m_i<=1 000 000).

Output

Джекийн сувднуудыг авч явах ялгаатай боломжуудын тоо нь k байг. Гаралт дээр байх ёстой ганц бүхэл тоо нь k % 2007 гэсэн утгатай байна(k тоог 2007-д хуваасны үлдэгдэл).

Example

Input:
2 1 3
3
5

Output:
9

Тайлбар. Джек сувднуудыг дараах байдлаар авч явж чадна:
(1, 0), (2, 0), (3, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (2, 1)