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$ วิธีในการสร้างต้นไม้และเปรียบเทียบโหนดลูก:
