• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

همان‌طور که در سوال قبل گفته شد پدر پوپک - همان آقا تورج - فرمانده ارتش است و توک پس از اینکه به پوپک نمی‌رسد، تصمیم می‌گیرد وارد ارتش شود و از آقا تورج انتقام بگیرد.

برای این کار، توک یک بمب در اتاق آقا تورج کار می‌گذارد.

آقا تورج وقتی متوجه بمب می‌شود که دیگر خیلی دیر شده و برای نجات دفترش می‌خواهد رمز بمب را حدس بزند. برای خنثی کردن بمب او باید \(n\) تا عدد \[a_1,a_2,...,a_{n-1},a_{n}\]را انتخاب کند به طوری که هر کدام عددی بین \(0\) تا \(2^{31}-1\) (شامل هر دو) هستند.

او \(q\) ثانیه برای فکر کردن دارد. در هر ثانیه این حدس را می‌زند که \(xor\) دو عدد \(a_i\) و \(a_j\) برابر \(k\) است. شما باید بعد از هر حدس به تورج بگویید که به چند طریق مختلف می‌تواند رمز را بزند (آرایه \(a\) را انتخاب کند) که تمام حدس‌هایی که تا الان زده شده، در آرایه \(a\) صدق کند (توجه کنید که ممکن است تعداد این حالات \(0\) باشد یعنی حالتی نباشد که با حدس‌ها هم‌‌خوانی داشته باشد). باقیمانده جواب را بر \(10^9+7\) چاپ کنید.

اگر با عملگر \(xor\) آشنایی ندارید اینجا را ببینید.

ورودی

در خط اول ورودی دو عدد \(n\) و \(q\) داده شده است.

سپس در \(q\) سطر بعدی در هر سطر یک حدس آقا تورج آمده است که به شکل سه عدد \(i, j, k\) است.

\[1 \le q \le 300\ 000\] \[2 \le n \le 300\ 000\] \[1 \le i,j \le n , i\neq j\] \[0 \le k \le 2^{31}-1\]

خروجی

به ازای هر حدس در \(q\) سطر باقیمانده جواب مساله بر \(10^9+7\) را چاپ کنید.

مثال

ورودی نمونه ۱

3 2
1 2 100
2 3 71

خروجی نمونه ۱

145586002
147483634