Тройки - 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.

Входные данные

В единственной строке через пробелы заданы числа a, A, b, B, c, C (a ≤ A, b ≤ B, c ≤ C, -10^9 ≤ a, b, c, A, B, C ≤ 10^9).

Выходные данные

В единственной строке – ответ задачи. Ответ выдать по модулю 1000000000 (10^9).

Примеры