Shrimpy Duc это пухлый и жадный мальчик, который всегда голоден. После бесчисленных попыток найти еду, чтобы утолить его нескончаемый голод, Shrimpy Duc нашел конфеты M&M, лежащие на поле \(L \times L\). Есть \(n\) конфеток M&M на этом поле, \(i\)-я из них находится в точке \((x_i + 0.5, y_i + 0.5),\) и имеет цвет \(c_i\), один из возможных \(k\) цветов (размерами M&Ms можно пренебречь).
Shrimpy Duc хочет украсть прямоугольник M&Ms, а именно, он хочет выбрать прямоугольник с целочисленными координатами внутри поля, и украсть все M&Ms в нем. Ему необязательно красть все конфеты, однако, он хочет украсть хотя бы одну конфету каждого цвета.
Иначе говоря, он хочет посчитать количество таких прямоугольников, в которых левая нижняя вершина находится в \((X_1, Y_1)\), правая верхняя в \((X_2, Y_2)\), они являются точками с целочисленными координатами, удовлетворяющие условиям \(0 \le X_1 < X_2 \le L\) и \(0 \le Y_1 < Y_2 \le L\), что для каждого \(1 \le c \le k\) существует хотя бы одна M&M с цветом \(c\), которая лежит в этом прямоугольнике.
Сколько существует таких прямоугольников? Это число может быть большим, так что вам достаточно найти его по модулю \(10^9 + 7\).
Выходные данные
Выведите одно целое число — количество прямоугольников, удовлетворяющих условиям Shrimpy Duc, по модулю \(10^9 + 7\).