30849번 - Вкусные тортики 다국어

문제

Каждый день летних каникул Миша рисовал в блокнотике аккуратное прямоугольное поле размером N × M клеточек и закрашивал на нём некоторые клеточки. Отметим, что каждый день у Миши получалась новая картинка, непохожая на другие, таким образом, всего у Миши получилось 2^NM картинок (на рисунке ниже закрашенные клетки обозначены серым).

Каждый день его друг Володя помогал Мише скрасить тяжелые будни: он брал очередной Мишин рисунок и пытался покрыть незакрашенные клетки этого рисунка прямоугольниками размера 1 × 2 (при этом каждая незакрашенная клеточка рисунка должна быть покрыта, прямоугольник не может накрывать закрашенную клеточку, прямоугольники не могут вылезать за пределы поля или перекрываться).

Конечно, Володе не всегда удавалось это сделать (те случаи, в которых ему удалось это сделать при N = 2 и M = 2 изображены на рисунке выше). Но в те немногие дни, когда это происходило, мама Миши очень радовалась за ребят и пекла им тортик. Сколько же тортиков пришлось ей испечь?

입력

В первой строке входных данных содержится два целых числа N и M — размеры поля (1 ⩽ N ⩽ 6, 1 ⩽ M ⩽ 500).

출력

Выведите единственное число — искомое количество тортиков по модулю 10⁹ + 7.

제한

힌트