Competitions
ISSPS`13 Wave 2 Day 5
Тройки - 2
Для заданных трех сегментов целых чисел [a, A], [b, B], [c, C], определить общее количество таких упорядоченных троек целых чисел (x, y , z), чтобы одновременно выполнялись условия:
x ≠ y,
x ≠ z,
y ≠ z,
a ≤ x ≤ A,
b ≤ y ≤ B,
c ≤ z ≤ C.
Input data
В единственной строке через пробелы заданы числа a, A, b, B, c, C (a ≤ A, b ≤ B, c ≤ C, -109 ≤ a, b, c, A, B, C ≤ 109).
Output data
В единственной строке – ответ задачи. Ответ выдать по модулю 1000000000 (109).
Examples
Input example #1
1 3 1 3 1 3
Output example #1
6