Начинающий DJ DIMAS хочет провести $$$d$$$ вечеринок подряд в Байтландии. Как известно, ни одна вечеринка DJ DIMAS не проходит без светомузыки. В ночном клубе, в котором будут проходить вечеринки, установлено $$$n$$$ различных лампочек. Однако после последней тусовки какие-то маргиналы поломали все переключатели света. Теперь Диме предстоит такая задача. Нужно где-то взять переключатели для лампочек. Однако о покупке переключателей речи быть не может, так как DJ DIMAS еще не достаточно разбогател. Поэтому он будет брать их в аренду. Однако в Байтландии есть еще и другие DJs, поэтому про каждый переключатель известно, в какие дни его можно брать в аренду.
Переключатели переключают состояние подмножества лампочек. Переключатель имеет вид бинарной строки $$$s$$$, состоящей из $$$n$$$ символов, нулей и единиц. Если на $$$i$$$-й позиции стоит единица, значит при переключении этого переключателя, изменится состояние $$$i$$$-й лампочки на противоположное (если лампочка была включена, она выключится, и наоборот).
Всего в пункте проката доступно $$$q$$$ переключателей. Про каждый из них известны $$$l$$$ и $$$r$$$ — промежуток дней, в который этот переключатель можно будет брать в аренду.
DJ DIMAS хочет, чтобы светомузыка была как можно разнообразнее, так что перед каждой вечеринкой он хочет знать, какое количество различных множеств включенных лампочек можно получить, используя имеющиеся переключатели. У DJ DIMAS осталось мало времени на подготовку новых треков, так что он просит помощи у вас.
В первой строке входного файла содержится три целых числа $$$n$$$, $$$q$$$ и $$$d$$$, где $$$n$$$ — количество лампочек, $$$q$$$ — количество переключателей, $$$d$$$ — количество дней, в которые будут проходить вечеринки.
В следующих $$$q$$$ строках содержатся сведения о переключателях. Каждый переключатель имеет вид:
$$$$$$1 \leq n, q, d \leq 500 \, 000$$$$$$ $$$$$$1 \leq l \leq r \leq d$$$$$$
Также гарантируется, что сумма длин $$$s$$$ по всем переключателям не превышает $$$500 \, 000$$$.
Выведите $$$d$$$ чисел через пробел, $$$i$$$-е ($$$1 \leq i \leq d$$$) из которых — количество различных множеств включенных лампочек, которые можно получить используя доступные переключатели в день $$$i$$$. Стоит отметить, что можно не использовать переключатели.
Так как эти числа могут быть слишком большими, выведите их по модулю $$$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
