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

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

2 секунди

256 мегабайтів

Складна

В багатьох мовах програмування є функції, які відповідають за заповнення усього масиву або деякої його частини певним значенням. У мові Pascal це функція fillchar(), у Java — Arrays.fill(), у C++ — memset(). У новій мові програмування J# з'явилась функція mark(), яка вміє працювати лише з масивами логічного типу.

Функція mark, викликана з двома параметрами $a$ та $b$ , присвоює усім елементам масиву з індексами від $a$ до $b$ включно значення $t r u e$ . Так, якщо взяти масив довжини $4$ , елементи якого пронумеровано з одиниці і усі значення у якому спочатку рівні $f a l se$ , і виконати з ним операції $ma r k (1, 3)$ mark(1, 3) та $ma r k (2, 4)$ mark(2, 4), то увесь масив виявиться заповнений значеннями $t r u e$ .

Одним з перших завдань для тих, хто починає вивчати J#, є написання програми, яка містить рівно $M$ операцій $ma r k$ , і повністю заповнює значеннями $t r u e$ масив довжини $N$ , який спочатку заповнено значеннями $f a l se$ .

Ви швидко впорались з цим завданням, і тепер задумались: скількома різними способами це можна зробити? Різними вважаються такі способи, у яких $i$ -ту операцію $ma r k$ у двох програмах запущено з різними параметрами хоча б для одного $i$ від $1$ до $M$ . Це число може бути великим, тому потрібно порахувати його по модулю $1 0^{9} + 7$ 10^9 + 7.

Вхідні дані

У першому рядку вхідного файлу задано два натуральних числа $N$ та $M$ — довжина масиву та кількість операцій $ma r k$ , які повинні бути у програмі ( $1 \leq N, M \leq 70$ 1 \leq N, M \leq 70).

Вихідні дані

У єдиному рядку вихідного файлу виведіть остачу від ділення числа способів заповнити масив з $N$ елементів значеннями $t r u e$ за допомогою $M$ викликів операції $ma r k$ на число $1 0^{9} + 7$ 10^9 + 7.

Приклади

Приклад 1

Примітка

Шукані варіанти:

$ma r k (1, 1)$ mark(1, 1); $ma r k (1, 2)$ mark(1, 2)
$ma r k (1, 1)$ mark(1, 1); $ma r k (2, 2)$ mark(2, 2)
$ma r k (1, 2)$ mark(1, 2); $ma r k (1, 1)$ mark(1, 1)
$ma r k (1, 2)$ mark(1, 2); $ma r k (1, 2)$ mark(1, 2)
$ma r k (1, 2)$ mark(1, 2); $ma r k (2, 2)$ mark(2, 2)
$ma r k (2, 2)$ mark(2, 2); $ma r k (1, 1)$ mark(1, 1)
$ma r k (2, 2)$ mark(2, 2); $ma r k (1, 2)$ mark(1, 2)