+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همان‌طور که در سوال قبل گفته شد پدر پوپک - همان آقا تورج - فرمانده ارتش است و توک پس از اینکه به پوپک نمی‌رسد، تصمیم می‌گیرد وارد ارتش شود و از آقا تورج انتقام بگیرد. برای این کار، توک یک بمب در اتاق آقا تورج کار می‌گذارد. آقا تورج وقتی متوجه بمب می‌شود که دیگر خیلی دیر شده و برای نجات دفترش می‌خواهد رمز بمب را حدس بزند. برای خنثی کردن بمب او باید $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$ آشنایی ندارید [اینجا](https://en.wikipedia.org/wiki/Bitwise_operation#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 ```