시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 71 | 42 | 36 | 92.308% |
영선이는 길 위에 혼자 서있다. 영선이가 서있는 길에는 늑대가 나타나기 때문에 매우 조심스러워 졌다.
도로는 N개의 구역으로 나누어져 있고, 구역은 0번부터 N-1번까지 번호가 매겨져 있다. 각 구역에는 최대 1마리의 늑대가 존재한다.
영선이는 늑대가 나타나는 정보를 총 M개 가지고 있다. 각각의 정보는 구간으로 이루어져 있으며, 그 구간에 늑대가 적어도 한 마리 존재한다는 것이다.
늑대가 적어도 한 마리 존재하는 구간에 대한 정보를 M개 가지고 있을 때, 도로에 있을 수 있는 늑대 배치의 경우의 수를 구하는 프로그램을 작성하시오.
첫째 줄에 구간의 개수 N과 정보의 수 M이 주어진다. (1 ≤ N, M ≤ 300)
둘째 줄부터 M개의 줄에는 늑대가 적어도 한 마리 존재하는 구간의 왼쪽 끝 구역 L과 오른쪽 끝 구역 R이 주어진다. 구간은 양 끝 구역을 포함한다.
첫째 줄에 늑대가 있을 수 있는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.
5 2 0 2 1 4
27
10 4 0 3 4 9 2 5 7 9
798
3 1 1 2
6