K-Uniform String

Time limit1sMemory limit256 MB

Summary

Count binary strings of length N where, for each of M given intervals, every length-K substring inside it contains the same number of ones, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Math, Prefix sum
Solved: No attempts yet

Problem

Take a string made of 0s and 1s. If every contiguous substring of length $K$ holds the same number of 1s, call the string $K$ -uniform.

For example, the string 100110 is 4-uniform. Its contiguous substrings of length 4 are 1001, 0011 and 0110, and each one holds two 1s.

Onjo wants to build a string of 0s and 1s with length $N$ . Onjo has $M$ favorite intervals and $M$ favorite numbers. The $i$ -th interval means the substring from the $L_i$ -th character to the $R_i$ -th character, and the $i$ -th number is $K_i$ . Onjo wants the substring of the $i$ -th interval to be $K_i$ -uniform. $K_i$ is not larger than the length of the $i$ -th interval.

Count the strings Onjo can build. The count can get large, so print it modulo 1,000,000,007.

Input

The first line contains $N$ and $M$ . ( $1 \le N \le 1000$ , $0 \le M \le 1000$ )

The $i$ -th of the next $M$ lines contains $L_i$ , $R_i$ and $K_i$ . ( $1 \le L_i \le R_i \le N$ , $1 \le K_i \le R_i - L_i + 1$ )

Output

Print the number of strings Onjo can build, modulo 1,000,000,007.

Hint

In the first example the eight strings are 00000, 00001, 01010, 01011, 10100, 10101, 11110 and 11111.

The second example gives Onjo no favorite interval and no favorite number, so any string of length $N$ works. That leaves $2^{1000}$ strings.

Examples2

Example 1
Input
```
5 2
1 4 2
3 5 3
```
Expected output
```
8
```
Example 2
Input
```
1000 0
```
Expected output
```
688423210
```