RiseOJ – 문제 출제

설명

*참고: 이 문제의 메모리 제한은 기본의 2배인 512MB이다.*

농부 존은 $$N$$ ( $1\le N\le 10^5$ )개의 문제를 만들었다. 그런 다음 $$M$$ ( $1\le M\le 20$ )명의 검수자를 모집했고, 각 검수자는 모든 문제를 "쉬움" 또는 "어려움"으로 평가했다.

이제 그의 목표는 $$N$$ 개의 문제 중 일부 부분집합을 어떤 순서로 배열하여, 난이도가 증가하는 순서로 구성된 문제집을 만드는 것이다. 어떤 검수자가 순서상 뒤에 있는 문제는 쉽다고 생각하지만 앞에 있는 문제는 어렵다고 생각하는 문제 쌍이 존재해서는 안 된다.

그가 만들 수 있는 서로 다른 비어 있지 않은 문제집의 개수를 $$10^9+7$$ 로 나눈 나머지를 구하라.

출제자: Benjamin Qi

제약

배점

출제자: Benjamin Qi

입력 형식

첫째 줄에 $$N$$ 과 $$M$$ 이 주어진다.

다음 $$M$$ 개의 줄에는 각각 길이 $$N$$ 의 문자열이 주어진다. 이 문자열의 $$i$$ 번째 문자는 해당 검수자가 $$i$$ 번째 문제를 쉽다고 생각하면 E, 그렇지 않으면 H이다.

출력 형식

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

예제 1

입력

3 1
EHE

출력

설명

The nine possible problemsets are as follows:

[1]
[1,2]
[1,3]
[1,3,2]
[2]
[3]
[3,1]
[3,2]
[3,1,2]

Note that the order of the problems within the problemset matters.

예제 2

입력

10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > February > Platinum

태그

JudgeUSACO

문제 출제