30625번 - 댄스타임

호영이는 기대하던 WooJeans의 팬미팅에 가게 되었다. 팬미팅의 하이라이트인 댄스타임에서는 마지막 라운드를 통과한 팬에게 사인 앨범을 주는데, 열혈팬 호영이도 사인 앨범을 받기 위해 열심히 춤 연습을 하고 있다.

댄스타임은 $N$개의 라운드로 이루어져 있으며, 각 라운드에는 WooJeans의 리더 우진이 바라보는 방향에 따라 올바른 춤을 춰야 한다. 댄스타임의 각 라운드에서 올바른 춤을 췄다는 것은 아래와 같이 춤을 추는 것을 뜻한다.

• 우진이 앞을 보고 춤을 추면 호영이는 우진과 같은 춤을 춰야 한다.
• 우진이 뒤를 보고 춤을 추면 호영이는 우진과 다른 춤을 춰야 한다.

댄스타임에서는 최대 한 번까지 올바르지 않은 춤을 추더라도 해당 라운드를 통과할 수 있다. 즉, 두 번 이상 올바르지 않은 춤을 추면 즉시 해당 라운드에서 떨어지게 된다.

호영이가 마지막 라운드까지 통과하여 사인 앨범을 받을 수 있는 경우의 수를 구해보자. 이때, 적어도 하나의 라운드에서 호영이가 추는 춤의 종류가 다르면 다른 경우이며, WooJeans의 열혈팬 호영이는 우진이 출 모든 춤을 알고 있다.

첫째 줄에 댄스타임의 라운드 개수 $N$, 우진이 출 춤 종류의 개수 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 100\,000;$ $1 \le M \le 100)$

둘째 줄부터 $N+1$번째 줄까지 각각의 줄에 우진이 추는 춤의 종류와 우진이 춤을 추는 동안 바라보는 방향을 나타내는 두 정수 $A_i$, $B_i$가 공백으로 구분되어 주어진다. $(1 \le A_i \le M;$ $0 \le B_i \le 1)$

우진은 $B_i$가 $0$이면 앞, $1$이면 뒤를 바라보고 춤을 춘다.

첫째 줄에 호영이가 사인 앨범을 받을 수 있는 경우의 수를 소수 $1\,000\,000\,007$로 나눈 나머지를 출력하라.