• محدودیت زمان: ۱٫۵ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت
• روز ۲ دوره ۳۱

---

چند روز دیگر، مسابقه حساس دربی تهران بین دو تیم استقلال و پرسپولیس برگزار می‌شود. این اولین دربی با حضور تماشاگران پس از شکست دادن ویروس کرونا می‌باشد. به همین دلیل تعداد زیادی تماشاگر به ورزشگاه می‌آیند تا تیم خود را تشویق کنند. مسئولین برگزاری مسابقه $n$ صندلی را برای تماشاگران درنظر گرفته‌اند و می‌خواهند صندلی‌ها را رنگ کنند.

همه‌ی صندلی‌ها در ابتدا سیاه هستند. مسئولین ورزشگاه از شما می‌خواهند به $q$ درخواست آن‌ها توجه کنید. هر درخواست یکی از دو نوع زیر است.

1. رنگ یکی از صندلی‌ها را به سیاه، آبی یا قرمز تغییر می‌دهند. تضمین می‌شود اگر رنگ صندلی را آبی یا قرمز بکنند، صندلی در مرحله قبل سیاه بوده است.
2. به چند روش می‌توان همه صندلی‌های سیاه را با دو رنگ آبی و قرمز رنگ کرد به طوری که تنش میان هواداران دقیقا $k$ باشد.

در روز مسابقه، هواداران پرسپولیس روی صندلی‌های قرمز و هواداران استقلال روی صندلی‌های آبی می‌نشینند. مقدار تنش میان آن‌ها برابر تعداد زوج‌ها $i < j$ است که صندلی $i$ام آبی و صندلی $j$ام قرمز باشد. به مسئولین مسابقه پاسخ درخواست‌های نوع دوم را بدهید.

ورودی

در خط اول $n$ تعداد صندلی‌ها و $q$ تعداد درخواست‌ها به ترتیب می‌آیند.

هر یک از $q$ خط بعدی به یکی از دو شکل زیر هستند.

در خط اول $n$ تعداد صندلی‌ها و $q$ تعداد درخواست‌ها به ترتیب می‌آیند.

هر یک از $q$ خط بعدی به یکی از دو شکل زیر هستند.

درخواست نوع اول: 1 x c مسئولین رنگ صندلی $x$ام را به رنگ $c$ درمی‌آورند. قرمز را با $R$، آبی را با $B$ و سیاه را با $X$ نمایش می‌دهند.

درخواست نوع دوم: 2 k به چند روش می‌توان صندلی‌های سیاه را آبی و قرمز کرد که تنش میان هواداران دقیقا $k$ باشد.

$$2 \leq n \leq 100$$ $$1 \leq q \leq 100$$

خروجی

باقی‌مانده تقسیم جواب هر درخواست نوع دوم بر $10^9+7$ را در خطی جدید چاپ کنید.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۷	$q\le50,:n\le10$
۲	۹	$q\le50,:n\le30$
۳	۴۳	هیچ درخواستی صندلی را سیاه نمی کند.
۴	۴۱	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

3 6
1 1 B
2 2
1 2 B
2 2
1 3 R
2 2

خروجی نمونه ۱

2
1
1

ورودی نمونه ۲

3 4
1 1 B
1 2 B
2 2
2 1

خروجی نمونه ۲

1
0

ورودی نمونه ۳

6 9
1 3 B
2 4
1 3 X
2 4
1 5 B
1 1 R
1 2 B
1 6 B
2 3

خروجی نمونه ۳

5
11
0

ورودی نمونه ۴

3 7
2 2
1 1 B
2 2
1 1 X
1 1 R
2 3
2 1

خروجی نمونه ۴

2
2
0
1