\(n\)개의 계단을 오른다. 각 이동에서 주어진 허용 보폭 집합 \(S\)에 있는 값만큼 올라갈 수 있다. 바닥(0번)에서 시작하여 꼭대기(\(n\)번)에 도달하는 서로 다른 순서 있는 방법의 수를 \(10^9+7\)로 나눈 나머지로 세시오. 이동 순서가 다르면 서로 다른 방법으로 센다.

첫 줄에 \(n\) (\(1 \le n \le 10^5\))이 주어진다. 둘째 줄에 허용 보폭의 개수 \(m\) (\(1 \le m \le 7\))이 주어진다. 셋째 줄에 \(m\)개의 서로 다른 정수 \(s_1, \dots, s_m\)이 주어진다 (\(1 \le s_i \le 7\)).

\(n\)번 계단까지 오르는 방법의 수를 \(10^9+7\)로 나눈 나머지로 출력한다.

riseoj 작성

출처 RiseOJ Basics