Окабэ любит гулять, но знает, что шпионы из Организации могут быть где угодно, поэтому он хочет узнать, по скольким различным путям он может пройти по городу. Город Окабэ состоит из всех точек (x, y) на плоскости таких, что x и y неотрицательны. Окабэ должен начать прогулку в начале координат (точке (0, 0)) и должен закончить путь в точке (k, 0). Если Окабэ сейчас находится в точке (x, y), то за один шаг он может перейти в точку (x + 1, y + 1), (x + 1, y) или (x + 1, y - 1).

Кроме того, существуют n горизонтальных отрезков, i-й из которых идет от точки x = a_i до x = b_i, включительно и располагается в y = c_i. Гарантируется, что a₁ = 0, a_n ≤ k ≤ b_n, и a_i = b_i - 1 для всех 2 ≤ i ≤ n. i-й из этих отрезков заставляет Окабэ находиться только в точках с y координатой в отрезке 0 ≤ y ≤ c_i, когда его x координата находится в отрезке a_i ≤ x ≤ b_i. Заметьте, что когда один отрезок кончается, а другой начинается, то он должен находиться под обоими отрезками одновременно.

Окабэ хочет узнать, сколько существует различных путей (последовательностей шагов) из начала координат в точку (k, 0), удовлетворяющих этим ограничениям, по модулю 10⁹ + 7.