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로 나눈 나머지를 출력해야 한다.

Problem Setting timer 1s memory 512MB

Problem Setting 1s 512MB