Not So Close
시간 제한1초메모리 제한1024 MB
r행 c열 격자에서 서로 인접한 8칸 안에 콘도가 겹치지 않도록 배치하는 경우의 수를 1e9+7로 나눈 나머지를 구한다.
문제
Orlando is quickly growing and new houses have to be built. However, people don't like being too close to each other these days. Universal Condos Forever (UCF) is building some housing units. The land they have is parceled out in grid squares as shown below:
In the example above, there are 5 rows and 4 columns. The owners of the condos, denoted by triangles, do NOT want other condos in ANY of the potentially 8 adjacent (up, down, left, right, diagonal) grid squares. For example, the above layout is a valid arrangement of five condos.
Given the number of rows and columns in the lot that UCF is building condo units, determine the number of different sets of placements of condos they could choose. Two sets are different if in one set a condo is built on a specific square but in the other set no condo is on that same exact square, or vice versa. Since the number of different arrangements could be very large, find the value modulo 109 + 7.
Note: trivially, building no condos is always a valid arrangement.
입력
There is only one input line; it contains two integers: r (1 ≤ r ≤ 10) and c (1 ≤ c ≤ 103), representing the number of rows and columns (respectively) for UCF's lot.
출력
Print the number of valid arrangements of condos, modulo 109 + 7.