0331. Инициализация массива

Во многих языках программирования есть функции, которые отвечают за заполнение всего массива или некоторой его части определенным значением. В языке Pascal это функция fillchar(), в Java – Arrays.fill(), в C++ – memset(). В новом языке программирования J\# появилась функция mark(), которая умеет работать только с массивами логического типа.

Функция mark, вызванная от двух параметров a и b, присваивает всем элементам массива с индексами от a до b включительно значение true, Так, если взять массив длины 4, элементы которого нумеруются с единицы и все значения в котором изначально равны false, и выполнить с ним операции mark(1, 3) и mark(2, 4), то весь массив окажется заполнен значениями true.

Одним из первых заданий для тех, кто начинает изучать J\#, является написание программы, содержащей ровно M операций mark, и полностью заполняющей значениями true массив длины N, изначально заполненный значениями false.

Вы быстро справились с этим заданием, и теперь задумались: сколькими различными способами это можно сделать? Различными считаются такие способы, в которых i-я операция mark в двух программах запущена с разными параметрами хотя бы для одного i от 1 до M. Это число может быть большим, поэтому требуется посчитать его по модулю 10⁹+7.

Формат входного файла

В первой строке входного файла даны два натуральных числа N и M – длина массива и количество операций mark, которые должны быть в программе. (1 ≤ N, M ≤ 70).

Формат выходного файла

В единственной строке выходного файла выведите остаток от деления числа способов заполнить массив из N элементов значениями true с помощью M вызовов операции mark на число 10⁹+7.

Пример:

Искомые варианты:

• mark(1, 1); mark(1, 2)
• mark(1, 1); mark(2, 2)
• mark(1, 2); mark(1, 1)
• mark(1, 2); mark(1, 2)
• mark(1, 2); mark(2, 2)
• mark(2, 2); mark(1, 1)
• mark(2, 2); mark(1, 2)

Источник: Командный чемпионат школьников Карелии по программированию, 4 ноября 2012

Обсудить       Отправить решение



Версия для печати