پادشاه آندورا (The King of Andorra)

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

در ابتدای مسابقه پادشاهی، پیر خردمند آندورا، یک دنباله شامل $n$ عدد $k$ بیتی را در نظر می‌گیرد. در ادامه در هر یک از مراحل مسابقه، پیر خردمند یک عدد $k$ بیتی مانند $s$ و یک زیربازه دلخواه مانند $[l, r]$ را از دنباله انتخاب کرده و یک کپی از آن را به شرکت‌کنندگان می‌دهد. سپس هر شرکت‌کننده، باید یک عدد $k$بیتی دلخواه مانند $f$ را انتخاب کرده و به‌ترتیب به ازای هر $1 \leq i \leq r- l + 1$ دقیقا یکی از ۲ عملیات زیر را روی $f$ انجام دهد:

• مقدار $f$ را برابر and عدد $i$ام زیردنباله و $f$ قرار دهد.
• مقدار $f$ را برابر or عدد $i$ام زیردنباله و $f$ قرار دهد.

۲ منظور از $and$، $and$ بیتی است، به عبارتی دیگر، حاصل $a\,and\,b$ برای دو عدد $k$بیتی یک عدد $k$بیتی می‌باشد که بیت $i$ام آن برابر and بیت $i$ام $a$ و $b$ است. منظور از $or$، $or$ بیتی است، به عبارتی دیگر، حاصل $a\,or\,b$ برای دو عدد $k$بیتی یک عدد $k$بیتی می‌باشد که بیت $i$ام آن برابر or بیت $i$ام $a$ و $b$ است.

می‌گوییم یک شرکت‌کننده به سعادت می‌رسد، اگر و تنها اگر مقدار نهایی $f$ برابر عدد انتخابی پیر خردمند یا همان $s$ باشد. شرکت‌کنندگان در هرمرحله، باید تعداد راه‌های رسیدن به سعادت را به پیر خردمند بگویند، به عبارت دیگر از بین $2^k \times 2^{r - l + 1}$ حالت ممکن برای انتخاب مقدار اولیه $f$ و عملیات‌های انتخاب شده برای اعداد زیربازه در چند حالت مقدار نهایی $f$ برابر $s$ می‌شود. پیر خردمند که احساس کرد سوال مسابقات پادشاهی زیادی آسان شده، تصمیم گرفت تا برخی از مراحل بجای پرسیدن تعداد روش‌های رسیدن به سعادت، یکی از اعضای دنباله را عوض کند.

بارتور که همیشه موفقیت‌هایش زیر سایه برادر بزرگتر به چشم نیامده، از شما خواسته تا کمکش کنید تا پادشاه آندورا شود.

در خط اول، ۳ عدد $n$ ، $k$ و $q$ می‌آیند که به ترتیب نمایانگر تعداد اعداد دنباله، تعداد بیت‌های اعداد دنباله و تعداد مراحل مسابقه پادشاهی هستند.

در خط دوم، $n$ عدد آمده که نمایانگر دنباله اولیه پیر خردمند است.

هر یک از $q$ خط بعدی به یکی از شکل‌های زیر است:

• 1 l r f: تعداد روش‌های رسیدن به سعادت را به پیر خردمند بگویید.
• 2 i x: پیر خردمند عضو $i$-ام دنباله را به $x$ تغییر می‌دهد.

در تنها خط خروجی جواب مسئله را به پیمانه $10^9 + 7$ خروجی دهید.

• زیرمسئله اول (۳ نمره): $1 \leq n, q \leq 14$.
• زیرمسئله دوم (۷ نمره): $1 \leq n, q \leq 200$.
• زیرمسئله سوم (۷ نمره): $k=1, l=1, r=n$.
• زیرمسئله چهارم (۱۰ نمره): $k=1$.
• زیرمسئله پنجم (۲۳ نمره): $k\leq2$.
• زیرمسئله ششم (۱۷ نمره): پیر خردمند دنباله را تغییر نمی‌دهد.
• زیرمسئله هفتم (۳۳ نمره): بدون محدودیت اضافی.

• $1 \leq n, q \leq 5 \times 10^4$
• $1 \leq k \leq 5$
• $0 \leq a_i,x,s < 2^k$
• $1 \leq i \leq n$
• $1 \leq l \leq r \leq n$