Пусть \(x\) — массив целых чисел \(x = [x_1, x_2, \dots, x_n]\). Обозначим \(B(x)\) как наименьший размер разбиения \(x\) на подотрезки, такие что все элементы в каждом подотрезке равны. Например, \(B([3, 3, 6, 1, 6, 6, 6]) = 4\) благодаря такому разбиению: \([3, 3\ |\ 6\ |\ 1\ |\ 6, 6, 6]\).
У вас нет точного массива \(x\), но вы знаете, что \(x_i\) может принимать любое целое значение из отрезка \([l_i, r_i]\) (\(l_i \le r_i\)) случайно и равновероятно. Все \(x_i\) независимы.
Посчитайте ожидаемое значение (матожидание) значения \((B(x))^2\) или \(E((B(x))^2)\). Гарантируется, что матожидание может быть представлено как рациональная дробь \(\frac{P}{Q}\), где \((P, Q) = 1\), поэтому выведите значение \(P \cdot Q^{-1} \mod 10^9 + 7\).
Примечание
Опишем все возможные значения массива \(x\) из первого примера:
- \([1, 1, 1]\): \(B(x) = 1\), \(B^2(x) = 1\);
- \([1, 1, 2]\): \(B(x) = 2\), \(B^2(x) = 4\);
- \([1, 1, 3]\): \(B(x) = 2\), \(B^2(x) = 4\);
- \([1, 2, 1]\): \(B(x) = 3\), \(B^2(x) = 9\);
- \([1, 2, 2]\): \(B(x) = 2\), \(B^2(x) = 4\);
- \([1, 2, 3]\): \(B(x) = 3\), \(B^2(x) = 9\);
В результате
\(E = \frac{1}{6} (1 + 4 + 4 + 9 + 4 + 9) = \frac{31}{6}\) или
\(31 \cdot 6^{-1} = 166666673\).
Все возможные значения \(x\) из второго примера:
- \([3, 4, 5]\): \(B(x) = 3\), \(B^2(x) = 9\);
- \([3, 4, 6]\): \(B(x) = 3\), \(B^2(x) = 9\);
- \([3, 5, 5]\): \(B(x) = 2\), \(B^2(x) = 4\);
- \([3, 5, 6]\): \(B(x) = 3\), \(B^2(x) = 9\);
- \([4, 4, 5]\): \(B(x) = 2\), \(B^2(x) = 4\);
- \([4, 4, 6]\): \(B(x) = 2\), \(B^2(x) = 4\);
- \([4, 5, 5]\): \(B(x) = 2\), \(B^2(x) = 4\);
- \([4, 5, 6]\): \(B(x) = 3\), \(B^2(x) = 9\);
В результате
\(E = \frac{1}{8} (9 + 9 + 4 + 9 + 4 + 4 + 4 + 9) = \frac{52}{8}\) или
\(13 \cdot 2^{-1} = 500000010\).