406550: GYM102439 D Light show

Junior DJ DIMAS wants to held $$$d$$$ parties in a row in the Byteland. As known, a single party of DJ DIMAS can't be without a light show. There are $$$n$$$ different lightbulbs in the night club, where the parties are held. However, after the last rave, some vandals broke all the switches. Now Dima has the following problem: he has to find new switches somewhere. However, a purchase of them is not possible, because DJ DIMAS isn't wealthy yet. So, he will rent them. Because of the fact that there are some other DJ in Byteland, each switch has an interval of days when it is available.

Switches toggle the state of a subset of lightbulbs. The switch is denoted by a binary string $$$s$$$, consisting of $$$n$$$ characters, ones and zeroes. If $$$i$$$-th position contains one, then after toggling this switch the state of $$$i$$$-th light will change on the opposite (if the light was on, it becomes off, and vice versa).

There are $$$q$$$ switches in the store. For each of them you are given $$$l$$$ and $$$r$$$ — interval of days this switch is available for rent.

DJ DIMAS wants the light show be as various as possible, so before each party, he wants to know the number of different sets of enabled lights he can get using some of the available switches. DJ DIMAS doesn't have much time preparing new tracks, so he asks you to help.

The first line contains three integers $$$n$$$, $$$q$$$ and $$$d$$$, where $$$n$$$  — the number of lightbulbs, $$$q$$$  — the number of switches, $$$d$$$  — the number of days parties will be held.

The next $$$q$$$ subsequent lines contain information about switches. Every switch is given as follows:

• $$$l$$$ $$$r$$$ $$$s$$$  — interval of days, when the switch is available. $$$s$$$  — string of $$$n$$$ characters consisting of $$$0$$$ and $$$1$$$ (for example, if $$$n = 5$$$, $$$s$$$ can be $$$\text{01101}$$$).

$$$$$$1 \leq n, q, d \leq 500 \, 000$$$$$$ $$$$$$1 \leq l \leq r \leq d$$$$$$

It is guaranteed that total length of $$$s$$$ of all switches will not exceed $$$500 \, 000$$$.

Print $$$d$$$ space-separated integers, $$$i$$$-th ($$$1 \leq i \leq d$$$) of them denoting the number of different sets of enabled lights, that are possible to toggle using some of the available switches at day $$$i$$$. It is worth mention, that all the switches can be unused.

Still this numbers can be very large, print them modulo $$$10^9 + 7$$$.

3 3 3
1 3 011
3 3 101
3 3 001

2 2 8 

4 3 4
2 4 1010
2 4 0101
3 4 1101

1 4 8 8 

5 2 2
1 2 01101
1 1 10101

4 2