Щасливий склад
Обмеження: 2 сек., 512 МіБ
Зеник працює на складі, де зараз зберігається новий мерч Алготестера, присвячений дню щасливих чисел. Усього на складі є n коробок з номерами від 1 до n. Коробки розташовані в ряд. i-а коробка має номер pi. Усі номери коробок різні.
Зеник з нетерпінням очікував на день щасливих чисел. Щоб якось згаяти час, він захотів попереставляти коробки місцями й вирішив робити таке. Спершу Зеник обирає деякий проміжок коробок, починаючи від l-ї і закінчуючи r-ю включно, а також деяке число x. Далі довільну кількість разів обирає пару індексів i та j з проміжку [l,r], такі що |i−j|=1, та pi≤x, pj≤x, і міняє коробки на позиціях i та j місцями. Тобто довільну кількість разів міняє місцями пару сусідніх коробок, у яких номери не перевищують x.
Зеник поки що вагається, які конкретно значення l,r,x йому обрати, тому він просить вашої допомоги.
Вам задано m трійок li,ri,xi, і для кожної з них Зеник просить сказати, скільки різних послідовностей коробок він може отримати, вибравши такі значення.
Оскільки відповіді можуть бути дуже великі, вам необхідно вивести остачу від їх ділення на просте число 109+7.
Дві послідовності коробок вважаються різними, якщо є позиція, на якій коробки в обох послідовностях мають різні номери.
Вхідні дані
У першому рядку задано два цілих числа n та m — кількість коробок на складі, а також кількість трійок, для яких треба знайти кількість способів.
У другому рядку задано n цілих чисел pi — номери коробок у порядку, у якому вони розташовані на складі.
У наступних m рядках задано трійки цілих чисел: li, ri, xi.
Вихідні дані
Виведіть m рядків, i-ий з яких повинен містити остачу від ділення кількості можливих послідовностей для i-ої трійки на 109+7.
Обмеження
1≤n,m≤105,
1≤pi≤n,
1≤li≤ri≤n,
1≤xi≤n.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 7 4 4 6 3 1 7 5 2 2 6 4 1 2 3 4 7 7 3 6 6 | 2 1 24 2 |