H행 N열 격자에 검은 칸이 정확히 N개인 피라미드 색칠의 수를 10^9+7로 나눈 나머지를 구한다.
어려움9조합론동적 계획법수학아직 제출이 없습니다시간 제한2초메모리 제한512 MB베라에게 H행 N열 격자가 있다. 행은 위에서부터 1번부터 H번까지, 열은 왼쪽에서부터 1번부터 N번까지 번호를 매긴다. r행 c열에 있는 칸을 (r,c)로 쓴다. 각 칸은 흰색 또는 검은색으로 칠해져 있다. 칠한 결과가 다음 조건을 모두 만족하면 피라미드라고 부른다.
색이 다른 칸이 하나라도 있으면 두 피라미드는 서로 다르다. 서로 다른 피라미드의 개수를 109+7로 나눈 나머지를 구하라.
첫째 줄에 정수 H와 N이 공백을 사이에 두고 주어진다. (1≤H,N≤105)
서로 다른 피라미드의 개수를 109+7로 나눈 나머지를 한 줄에 출력한다.
H=2, N=6일 때 피라미드는 다음 7가지다. #은 검은 칸, .은 흰 칸을 나타낸다.
###### ####.. ####.. #####. #####. #####. #####.
...... .##... ..##.. .#.... ..#... ...#.. ....#.