칵테일 만들기

Pia는 스톡홀름의 유명한 나이트클럽 Supernova에서 일하는 유명한 바텐더이다. 그녀의 가장 인상적인 묘기 중 하나는 바에 있는 $N$가지 서로 다른 음료 재료를 각각 정확히 한 번씩 사용해 여러 잔의 칵테일을 만드는 것이다. 그녀는 다음과 같은 방식으로 이를 해낸다.

먼저 Pia는 만들 칵테일의 수를 정한다. 그러면 각 재료가 $1, 2, \dots, N$의 순서로 그녀 앞에 나열된다. 첫 번째 칵테일에는 왼쪽에서부터 양의 개수 $K$개의 재료, 즉 $1, 2, ..., K$를 사용한다. 다음 칵테일에는 아직 사용하지 않은 첫 번째 재료부터 양의 개수 $L$개의 재료, 즉 $K + 1, K + 2, \dots, K + L$을 사용한다. 그녀는 마지막 칵테일이 재료 $N - M, N - M + 1, \dots, N$을 사용할 때까지 이 과정을 계속한다.

하지만 모든 재료 쌍이 칵테일에서 잘 어울리는 것은 아니다. 예를 들어 우유와 물은 그다지 잘 어울리지 않는다. 그녀는 어떤 칵테일에도 어울리지 않는 재료 쌍을 넣을 수 없다.

지금까지 그녀는 매일 밤 서로 다른 칵테일 조합을 만들어 왔다. 그녀는 며칠 동안 새로운 칵테일 조합을 만들 수 있는가? 두 칵테일 조합이 정확히 같은 칵테일들로 이루어져 있지 않으면 서로 다르다고 하며, 일부 칵테일을 공유하는 것은 허용된다.

첫 번째 줄에는 두 정수 $1 \le N \le 100\,000$과 $0 \le P \le 100\,000$가 주어진다. $N$은 재료의 수이고 $P$는 어울리지 않는 재료 쌍의 수이다.

다음 $P$개의 줄에는 각각 두 정수 $1 \le a \not= b \le N$가 주어지며, 이는 칵테일에서 서로 어울리지 않는 두 재료이다. 같은 재료 쌍이 이 목록에 여러 번 나타날 수 있다.

Pia가 서로 다른 칵테일 조합을 만들 수 있는 날의 수를 하나의 정수로 출력한다. 이 수는 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.