eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Ініціалізація масиву

Ініціалізація масиву

В багатьох мовах програмування є функції, які відповідають за заповнення усього масиву або деякої його частини певним значенням. У мові \textit{Pascal} це функція \textit{fillchar()}, у \textit{Java} --- \textit{Arrays.fill()}, у \textit{C++} --- \textit{memset()}. У новій мові програмування \textit{J#} з'явилась функція \textit{mark()}, яка вміє працювати лише з масивами логічного типу. Функція \textit{mark}, викликана з двома параметрами \textbf{a} та \textbf{b}, присвоює усім елементам масиву з індексами від \textbf{a} до \textbf{b }включно значення \textbf{true}, Так, якщо взяти масив довжині \textbf{4}, елементи якого пронумеровано з одиниці і усі значення у якому спочатку рівні \textbf{false}, і виконати з ним операції \textbf{mark(1, 3)} та \textbf{mark(2, 4)}, то увесь масив виявиться заповнений значеннями \textbf{true}. Одним з перших завдань для тех, хто починає вивчати \textit{J#}, є написання програми, яка містить рівно \textbf{M }операцій \textbf{mark}, і повністю заповняє значеннями \textbf{true} масив довжини \textbf{N}, який спочатку заповнено значенями \textbf{false}. Ви швидко впорались з цим завданням, і тепер задумались: скількома різними способами це можна зробити? Різними вважаються такі способи, у яких \textbf{i}-ту операцію \textbf{mark} у двох програмах запущено з різними параметрами хоча б для одного \textbf{i} від \textbf{1} до \textbf{M}. Це число може бути великим, тому потрібно порахувати його по модулю \textbf{10^9+7}. \InputFile У першому рядку вхідного файлу задано два натуральних числа \textbf{N} та \textbf{M} --- довжина масиву та кільксть операцій \textbf{mark}, які повинні бути у програмі (\textbf{1} ≤ \textbf{N}, \textbf{M} ≤ \textbf{70}). \OutputFile У єдиному рядку вихідного файлу виведіть остачу від ділення числа способів заповнити масив з \textbf{N} елементів значеннями \textbf{true} при допомозі \textbf{M} викликів операції \textbf{mark} на число \textbf{10^9+7}. \textbf{Пояснення до прикладу} Шукані варіанти: \begin{itemize} \item mark(1, 1); mark(1, 2) \item mark(1, 1); mark(2, 2) \item mark(1, 2); mark(1, 1) \item mark(1, 2); mark(1, 2) \item mark(1, 2); mark(2, 2) \item mark(2, 2); mark(1, 1) \item mark(2, 2); mark(1, 2) \end{itemize}
Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
2 2
Вихідні дані #1
7