Yana و Mino و White و Huzz هم أفضل الأصدقاء.
يشعر Mino بالحيرة مؤخراً. وبسبب هوسه بإخفاقاته السابقة في OI، كان يكافح للتخطيط لمستقبله أثناء إدارة جدوله المدرسي المزدحم. اقترح أصدقاؤه الثلاثة أن يقيّم أهمية مهامه ويرتب أولوياتها.
لنفترض أن هناك $n$ مهام مختلفة مرقمة من $1$ إلى $n$. في كل مرة، يختار Huzz مهمتين متجاورتين، وتقارنهما White، وتدمجهما Yana في مهمة واحدة. يتفاجأ Mino عندما يكتشف أن هذه العملية تشكل بالصدفة شجرة مقاطع (segment tree)، والتي لا تنقسم بالضرورة في المنتصف. وبشكل أكثر دقة، فإنها تشكل شجرة تحتوي على $2n - 1$ عقد، حيث تقابل كل شجرة فرعية مقطعاً متجاوراً. لاحظ أن جميع المهام الـ $n$ هي أوراق، بينما لكل عقدة من العقد الـ $n - 1$ الأخرى طفلان. هذه العقد الناتجة عن المقارنات تحدد قيم الحواف المتجهة إلى طفليها: $0$ للأصغر و $1$ للأكبر.
يحب Mino الحسابات كثيراً. وهو يعرّف وزن كل مهمة بأنه مجموع XOR للحواف على طول المسار من المهمة إلى الجذر. ويتساءل: إذا أُعطيت الأوزان، فكم طريقة توجد لبناء مثل هذه الأشجار ومقارنة الأطفال؟
مرة أخرى، Mino ليس ماهراً في OI، ولهذا السبب لجأ إليك طلباً للمساعدة. لتبسيط المسألة، تحتاج فقط إلى إيجاد الإجابة بباقي القسمة على $998,244,353$.
الإدخال
يحتوي السطر الأول من الإدخال على عدد صحيح موجب $n$ ($1 \le n \le 250000$)، وهو عدد المهام.
يحتوي السطر الثاني على سلسلة ثنائية $S$ بطول $n$، حيث يمثل $S_i$ قيمة Bitwise-XOR لجميع القيم الموجودة على الحواف من المهمة $i$ إلى الجذر.
الإخراج
اطبع عدداً صحيحاً، وهو الإجابة بباقي القسمة على $998,244,353$.
مثال
الإدخال القياسي
4 0101
الإخراج القياسي
6
ملاحظة
توجد $6$ طرق لبناء الشجرة ومقارنة الأطفال:
