페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5510

Problem Setting 1s 512MB

문제

Farmer John은 N (1\le N\le 10^5)개의 문제를 만들었다. 그는 이후 M (1\le M\le 20)명의 테스트 솔버를 모집했고, 각 솔버는 모든 문제를 “쉬움(easy)” 또는 “어려움(hard)“으로 평가하였다.

이제 Farmer John의 목표는 1개 이상의 문제를 선택하여 난이도가 증가하는 순서로 정렬된 문제집을 만드는 것이다. 문제집에는 다음과 같은 조건이 있어야 한다.

어떤 두 문제 (a, b)가 있을 때, 문제 a가 문제 b보다 먼저 등장하고, 어떤 테스트 솔버가 문제 a를 어렵다고 평가했지만 문제 b를 쉽다고 평가한 경우, 이러한 문제집은 유효하지 않다.

Farmer John이 만들 수 있는 서로 다른 문제집의 개수를 구하라. 단, 결과는 10^9+7로 나눈 나머지를 출력해야 한다.


입력

첫 번째 줄에 정수 N과 M이 주어진다.

다음 M개의 줄에는 길이가 N인 문자열이 주어진다.

• 이 문자열의 i번째 문자는 해당 테스트 솔버가 i번째 문제를 쉽다고(E) 평가했는지, 어렵다고(H) 평가했는지를 나타낸다.


출력

만들 수 있는 서로 다른 문제집의 개수를 10^9+7로 나눈 나머지를 출력한다.


예제 #1

3 1

EHE
9

문제집을 만드는 경우는 아래와 같다.

  • 1문제짜리 : [1], [2], [3]

  • 2문제짜리 : [1,2], [1,3], [3,1], [3,2]

  • 3문제짜리 : [1,3,2], [3,1,2]


예제 #2

10 6

EHEEEHHEEH

EHHHEEHHHE

EHEHEHEEHH

HEHEEEHEEE

HHEEHEEEHE

EHHEEEEEHE
33

출처

USACO 2023 February Platinum

로그인해야 코드를 작성할 수 있어요.