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$ מייצג את ה-XOR הסיביתי (Bitwise-XOR) של כל הערכים על הקשתות ממשימה $i$ אל השורש.
פלט
הדפס מספר שלם, התשובה מודולו $998,244,353$.
דוגמה
קלט
4 0101
פלט
6
הערה
ישנן $6$ דרכים לבנות את העץ ולהשוות בין הילדים:
