Фермер Джон турбується за здоров'я своїх корів після вибуху високорозповсюдженої хвороби худоби COWVID-19.

Для обмеження передачі хвороби ~N~ корів фермера Джона (~2 \leq N \leq 10^5~) вирішили практикувати "соціальну дистанцію" та розійшлись по фермі. Ферма має форму 1D числової лінії, з ~M~ не перетинаючимися інтервалами (~1 \leq M \leq 10^5~), де є трава для пасовища. Корови хочуть розташуватися в різних цілих точках, кожна з яких покрита травою, щоб максимізувати значення ~D~, де ~D~ представляє відстань між найближчою парою корів. Будь ласка, допоможіть коровам визначити найбільше можливе значення ~D~.

Input

Перший рядок введення містить ~N~ та ~M~. Наступні ~M~ рядків описують кожен інтервал у вигляді двох цілих чисел ~a~ і ~b~, де ~0 \leq a \leq b \leq 10^{18}~. Жодні два інтервали не перекриваються і не дотикаються до своїх кінцівок. Корова, що стоїть на кінці інтервалу, рахується, як стояча на траві.

Output

Виведіть найбільше можливе значення ~D~ таке, щоб всі пари корів були віддалені на ~D~ одиниць. Гарантується наявність рішення з ~D>0~.

Оцінювання

Ви отримаєте ~20~ балів, якщо рішення буде працювати правильно для ~b\le 10^5~.

Sample Input 1

5 3
0 2
4 7
9 9

Sample Output 1

2

Notes

Один із способів досягнення ~D=2~ - мати корови на позиціях ~0~, ~2~, ~4~, ~6~ та ~9~.

Об'єднані корови фермера Джона (UCFJ) відправляють делегацію на Міжнародну олімпіаду з інформатики (IOI).

Є ~N~ корів, що беруть участь у відборі делегації (~1 \leq N \leq 2 \cdot 10^5~). Вони стоять в лінії, і корова ~i~ має породу ~b_i~.

Делегація складатиметься з інтервалу принаймні з двох корів - тобто корів ~l\ldots r~ для цілих чисел ~l~ і ~r~, які задовольняють ~1\le l<r\le N~. Дві бічні корови вибраного інтервалу будуть визначені як "лідери". Щоб уникнути конфлікту між породами, кожен лідер повинен бути іншої породи від решти делегації (лідерів або ні).</p>

Допоможіть UCFJ визначити кількість способів, яким вони можуть обрати делегацію для відправлення на IOI.

Input

Перший рядок містить ~N~.

Другий рядок містить ~N~ цілих чисел ~b_1,b_2,\ldots,b_N~, кожне з діапазону ~[1,N]~.

Output

Виведіть одне ціле число.

Оцінювання

• Для ~15~ балів ~N \le 100~.
• Для ~40~ балів ~N \le 5000~.

Sample Input 1

7
1 2 3 4 3 2 5

Sample Output 1

13

Notes

Кожна делегація відповідає одному з наступних пар лідерів:

$$(1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7).$$

Трава висохла на пасовищі фермера Джона через посуху. Після годин відчаю та роздумів ФД придумав прекрасну ідею купити кукурудзу, щоб годувати своїх дорогоцінних корів.

~N~ (~1 \leq N \leq 100~) корів ФД розташовані в ряд так, що ~i~-та корова в ряду має не від'ємний цілочисельний рівень голоду ~h_i~. Оскільки корови ФД - соціальні тварини і настоюють на тому, щоб їсти разом, єдиний спосіб знижувати рівні голоду своїх корів - обрати дві сусідні корови ~i~ та ~i+1~ і погодувати кожну з них мішком кукурудзи, що призведе до зменшення їх голоду на одиницю.

ФД хоче годувати своїх корів до того моменту, коли всі вони матимуть однаковий цілий невід'ємний рівень голоду. Хоча він не знає точних рівнів голоду своїх корів, він знає верхню межу голоду кожної корови; зокрема, рівень голоду ~h_i~ ~i~-того корови становить не більше ~H_i~ (~0\le H_i\le 1000~).

Ваше завдання полягає в тому, щоб прахувати кількість ~N~-масивів рівнів голоду ~[h_1,h_2,\ldots,h_N]~, які відповідають цим верхнім межам, так що ФД може досягти своєї мети, за модулем ~10^9+7~.

Input

Перший рядок містить ~N~.

Другий рядок містить ~H_1,H_2,\ldots,H_N~.

Output

Кількість ~N~-масивів рівнів голоду за модулем ~10^9+7~.

Оцінювання

~N~ парне у випадках з парним номером тестів і непарне в випадках з непарним номером тестів.

• Для ~20~ балів ~N\le 6~ та ~H_i \le 10~.

• Для ~50~ балів ~N\le 50~ та ~H_i \le 100~.

Notes

Перший приклад:

Є ~(9+1)\cdot(11+1)\cdot(7+1)~ ~3~-масиви ~h~, які узгоджуються з ~H~.

Один з цих масивів - ~h=[8,10,5]~. В цьому випадку можна зробити всі корови з однаковими рівнями голоду: дайте по два мішки кукурудзи обом коровам ~2~ та ~3~, тоді дайте по п'ять мішків кукурудзи обом коровам ~1~ та ~2~, що призведе до того, що кожна корова матиме рівень голоду ~3~.

Інший з цих масивів - ~h=[0,1,0]~. В цьому випадку не можна зробити рівні однаковими.

Бовінополіс проводить перерозподіл округів! – завжди суперечливий політичний процес між двома основними породами корів (Хольштини та Гернсі), які там проживають, оскільки обидві породи хочуть забезпечити собі достатній вплив у уряді Бовінополісу.

Велика метрополійна зона Бовінополісу складається з лінії з ~n~ пасовищ ~(1 \leq n \leq 3 \cdot 10^5)~, кожне з яких містить одну корову, яка є або Хольштиною, або Гернсі.

Уряд Бовінополісу хоче розділити велику метрополійну зону на кілька суміжних округів так, щоб кожен округ містив не більше ~k~ пасовищ ~(1 \leq k \leq n)~, і кожне пасовище входило рівно в один округ. Оскільки уряд наразі контролюється Хольштинами, вони хочуть знайти спосіб перерозподілу, який мінімізує кількість округів із більшістю Гернсі або рівною кількістю (округ вважається рівним, якщо кількість Гернсі дорівнює кількості Хольштинів).

Стурбована коаліція Гернсі намагається зрозуміти, якої шкоди може завдати перерозподіл уряду. Допоможіть їм визначити найгірший мінімальний можливий результат — кількість округів, які є або з більшістю Гернсі, або рівними.

Input

Перший рядок містить два цілі числа ~n~ та ~k~.

Другий рядок містить рядок довжини ~n~. Кожен символ — це або H, або G, що позначає Хольштину чи Гернсі.

Output

Виведіть мінімально можливу кількість округів, які є з більшістю Гернсі або рівними.

Sample Input 1

7 2
HGHGGHG

Sample Output 1

3