가희와 서울 지하철 3호선

가희는 지하철을 타고 가다가 지상역과 지하역이 번갈아 나오는 롤러코스터 구간을 발견하였습니다. 롤러코스터 구간은 다음과 같이 정의합니다.

• 길이가 1인 구간은 롤러코스터 구간입니다.
• 역 sa번부터 sb번까지가 롤러코스터 구간이고 아래 두 조건 중 하나를 만족하면, 역 sa번부터 sb+1번까지도 롤러코스터 구간입니다.
  • sb번 역이 지상역이고 sb+1번 역이 지하역입니다.
  • sb번 역이 지하역이고 sb+1번 역이 지상역입니다.

예를 들어, 서울 지하철 3호선에서 가장 긴 롤러코스터 구간의 길이는 5입니다. 원흥, 원당, 화정, 대곡, 백석역이 차례로 지하, 지상, 지하, 지상, 지하역이기 때문입니다. 서울 지하철 5호선에서 가장 긴 롤러코스터 구간의 길이는 1입니다. 지상역이 하나도 없기 때문입니다.

가희가 타고 다니는 3호선에는 다음과 같은 특징이 있습니다.

• 역의 개수는 n개입니다.
• 가장 긴 롤러코스터 구간의 길이는 m입니다.
• 환승역은 없으며, 한 역에는 승강장이 하나뿐입니다.
• 지상역의 승강장은 지상 1층, 2층, 3층, 4층, 5층 중 한 곳에 있습니다.
• 지하역의 승강장은 지하 1층부터 지하 11층까지 중 한 곳에 있습니다.

가희는 롤러코스터 구간에 정신이 팔려 정작 중요한 승강장 층수를 적지 않았습니다. 그래서 오빠에게 n개의 역을 모두 돌면서 승강장 층수를 적어 달라고 부탁했습니다. 오빠는 덜렁대는 성격이라, 위의 조건만 지키면 된다는 생각으로 n개 역의 승강장 층수 정보를 마음대로 적어 가희에게 줄 것입니다.

승강장 층수가 한 역이라도 다르면 서로 다른 경우로 셉니다. 가희가 오빠에게 받을 수 있는 서로 다른 정보는 몇 가지인가요? 답은 $10^9+7$로 나눈 나머지를 출력하세요.

첫 번째 줄에 n과 m이 공백으로 구분되어 주어집니다.

다음 n개의 줄에 역 이름이 한 줄에 하나씩 주어집니다. 1번 역이 가장 먼저, n번 역이 가장 마지막에 주어집니다.

답을 $10^9+7$로 나눈 나머지를 출력하세요.

• $1 \le n \le 20$
• $1 \le m \le n$
• 모든 역 이름의 길이는 10 이하이며, 중복된 역 이름은 없습니다.
• 역 이름은 대소문자 영문자와 숫자로만 이루어져 있습니다.