지구 밖 koi4u 행성에는 생명체가 살고 있다.
tompi는 emppu에게 줄 선물로 크기가 W*H이고 크기 1*1의 정사각형으로 나뉘어진 직사각형의 과자를 만들었다.
그런데 megalusion은 너무 배가 고픈 나머지 K-블록을 빼내서 먹고 싶다.
그러나 빼내 먹은 뒤에 나머지 부분이 나뉘어지면 tompi는 매우 화를 낼 것이다.
tompi가 화를 내지 않도록 하면서 megalusion이 먹을 수 있는 가능한 블록의 서로 다른 경우의 수를 구하시오.
K-블럭은 크기가 1*1인 정사각형이 K개 연결되어 있는 모양이다.
아래 그림은 5-블럭의 모든 모양이다. (회전, 반사했을 때, 같은 모양이 나오는 것은 제외)
임의의 정사각형에서 정사각형의 변만을 통과해서 다른 모든 정사각형으로 갈 수 있을 때 연결되어 있다고 말한다.
왼쪽 두 모양은 연결되어 있지 않은 상태이고, 오른쪽 모양은 연결된 상태이다.
아래 그림은 K가 7일 때 정답에 포함되어야 하는 경우와 포함되면 안 되는 경우를 나타낸 것이다.
왼쪽 두 가지 모양은 정답으로 세면 안 된다.
그 이유는 빨간색 모양으로 빼내면 두 부분으로 나누어지기 때문이다.
오른쪽 모양은 잘라도 남은 과자가 모두 연결되어 있으므로 정답으로 센다.