K-균등 문자열

0과 1로 이루어진 문자열에서 길이가 $K$인 연속 부분문자열을 모두 살펴봤을 때 그 안에 들어 있는 1의 개수가 전부 같으면, 이 문자열을 $K$-균등하다고 하자.

예를 들어 문자열 100110은 4-균등하다. 길이가 4인 연속 부분문자열은 1001, 0011, 0110 세 개인데 셋 다 1을 두 개씩 담고 있기 때문이다.

온조는 0과 1로 이루어진 길이 $N$의 문자열을 만들려고 한다. 온조에게는 좋아하는 구간 $M$개와 좋아하는 수 $M$개가 있다. $i$번째 구간은 $L_i$번째 문자부터 $R_i$번째 문자까지의 부분문자열을 뜻하고, $i$번째 수는 $K_i$이다. 온조는 $i$번째 구간에 해당하는 부분문자열이 $K_i$-균등하기를 원한다. $K_i$는 $i$번째 구간의 길이보다 크지 않다.

온조가 만들 수 있는 문자열의 개수를 구하여라. 수가 커질 수 있으니 1,000,000,007로 나눈 나머지를 출력한다.

첫째 줄에 $N$과 $M$이 주어진다. ($1 \le N \le 1000$, $0 \le M \le 1000$)

이어지는 $M$개 줄 중 $i$번째 줄에 $L_i$, $R_i$, $K_i$가 주어진다. ($1 \le L_i \le R_i \le N$, $1 \le K_i \le R_i - L_i + 1$)

첫째 줄에 온조가 만들 수 있는 문자열의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

첫 번째 예제에서 만들 수 있는 문자열은 00000, 00001, 01010, 01011, 10100, 10101, 11110, 11111의 여덟 가지이다.

두 번째 예제에는 온조가 좋아하는 구간도 수도 없으므로 길이 $N$의 문자열을 아무렇게나 만들어도 된다. 즉 $2^{1000}$가지를 만들 수 있다.