Count the number of binary string of length N that satisfies the following M conditions:

The conditions can be 1 of 2 type

1 l r: There exists that least 1 '0' in the range [l, r]

2 l r: there exists at least 1 '1' in the range [l, r]

N <= 1e18

M <= 1e5

Thanks!