드라마
시간 제한2초메모리 제한512 MB
H행 N열 격자에 검은 칸이 정확히 N개인 피라미드 색칠의 수를 10^9+7로 나눈 나머지를 구한다.
문제
베라에게 행 열 격자가 있다. 행은 위에서부터 1번부터 번까지, 열은 왼쪽에서부터 1번부터 번까지 번호를 매긴다. 행 열에 있는 칸을 로 쓴다. 각 칸은 흰색 또는 검은색으로 칠해져 있다. 칠한 결과가 다음 조건을 모두 만족하면 피라미드라고 부른다.
- 검은 칸이 정확히 개다.
- 은 검은색이다.
- 와 가 모두 검은색이면, 인 모든 에 대해 도 검은색이다.
- 가 검은색이고 가 존재하면, 도 검은색이다.
- 가 검은색이고 가 검은색인 가 하나도 없으면, 가 존재하는 경우 그 칸은 흰색이다.
색이 다른 칸이 하나라도 있으면 두 피라미드는 서로 다르다. 서로 다른 피라미드의 개수를 로 나눈 나머지를 구하라.
입력
첫째 줄에 정수 와 이 공백을 사이에 두고 주어진다. ()
출력
서로 다른 피라미드의 개수를 로 나눈 나머지를 한 줄에 출력한다.
힌트
, 일 때 피라미드는 다음 7가지다. #은 검은 칸, .은 흰 칸을 나타낸다.
###### ####.. ####.. #####. #####. #####. #####.
...... .##... ..##.. .#.... ..#... ...#.. ....#.