Вкусные тортики
시간 제한1초메모리 제한1024 MB
N x M 격자에서 칠하지 않은 칸을 1 x 2 도미노로 정확히 덮을 수 있는 색칠 패턴의 수를 구한다. N은 6 이하, M은 500 이하이며 답을 10^9+7로 나눈 나머지를 출력한다.
문제
Каждый день летних каникул Миша рисовал в блокнотике аккуратное прямоугольное поле размером N × M клеточек и закрашивал на нём некоторые клеточки. Отметим, что каждый день у Миши получалась новая картинка, непохожая на другие, таким образом, всего у Миши получилось 2NM картинок (на рисунке ниже закрашенные клетки обозначены серым).
Каждый день его друг Володя помогал Мише скрасить тяжелые будни: он брал очередной Мишин рисунок и пытался покрыть незакрашенные клетки этого рисунка прямоугольниками размера 1 × 2 (при этом каждая незакрашенная клеточка рисунка должна быть покрыта, прямоугольник не может накрывать закрашенную клеточку, прямоугольники не могут вылезать за пределы поля или перекрываться).
Конечно, Володе не всегда удавалось это сделать (те случаи, в которых ему удалось это сделать при N = 2 и M = 2 изображены на рисунке выше). Но в те немногие дни, когда это происходило, мама Миши очень радовалась за ребят и пекла им тортик. Сколько же тортиков пришлось ей испечь?
입력
В первой строке входных данных содержится два целых числа N и M — размеры поля (1 ⩽ N ⩽ 6, 1 ⩽ M ⩽ 500).
출력
Выведите единственное число — искомое количество тортиков по модулю 109 + 7.