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$$$.