27884번 - 가희와 서울 지하철 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층, 2층, 3층, 4층, 5층, 6층, 7층, 8층, 9층, 10층, 11층 중 하나에 있습니다.

가희는 롤러코스터 구간이 긴 3호선에 정신이 팔려서, 정작 중요한 승강장 층수를 적는 것을 까먹었습니다. 그래서, 오빠에게 n개의 역을 모두 돌면서 승강장 층수를 적어 달라고 하였습니다. 오빠는 너무 덜렁대서 위에 있는 조건에만 맞도록 노선에 있는 n개 역의 승강장 층수에 대한 정보를 아무렇게나 적어 가희에게 줄 것입니다.

최소한 한 역 이상의 승강장 층수가 다르면, 다른 경우로 셉니다. 가희가 오빠에게 받을 수 있는 서로 다른 정보의 개수는 몇 가지인가요?

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

그 다음 줄부터 n개의 줄에 n개의 역 이름이 주어집니다. 1번 역은 처음에, n번 역은 가장 마지막에 주어집니다.

문제에 대한 답을 109+7로 나눈 나머지를 출력해 주세요.

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