Yana, Mino, White және Huzz — ең жақын достар.

Соңғы кезде Mino абдырап жүр. OI-дағы бұрынғы сәтсіздіктеріне байланып қалған ол мектептегі тығыз кестесін алып жүріп, болашағын жоспарлауда қиналып жүрді. Оның үш досы оған тапсырмаларының маңыздылығын бағалап, басымдықтарды белгілеуді ұсынды.

$1$-ден $n$-ге дейін нөмірленген $n$ әртүрлі тапсырма бар делік. Әр жолы Huzz көршілес екі тапсырманы таңдайды, White оларды салыстырады, ал Yana оларды бір тапсырмаға біріктіреді. Mino бұл процесс кездейсоқ (міндетті түрде дәл ортасынан бөлінбейтін) кесінділер ағашын құрайтынын байқап таңғалды. Дәлірек айтқанда, ол $2n - 1$ төбесі бар ағаш құрайды, мұндағы әрбір ішкі ағаш бір тұтас кесіндіге сәйкес келеді. Барлық $n$ тапсырма жапырақтар болып табылатынын, ал қалған $n - 1$ төбенің әрқайсысының екі баласы бар екенін ескеріңіз. Салыстыру нәтижесінде пайда болған бұл төбелер өз балаларына баратын қабырғалардың мәндерін анықтайды: кішісі үшін $0$ және үлкені үшін $1$.

Mino есептеулерді өте жақсы көреді. Ол әрбір тапсырманың салмағын сол тапсырмадан түбірге дейінгі жол бойындағы қабырғалардың XOR қосындысы ретінде анықтайды. Ол былай деп ойланады: егер салмақтар берілген болса, осындай ағаштарды құрудың және балаларын салыстырудың қанша тәсілі бар?

Тағы да, Mino OI-ға шебер емес, сондықтан ол сізден көмек сұрады. Есепті жеңілдету үшін тек жауапты $998,244,353$ модулі бойынша табу керек.

Кіріс деректер

Кірістің бірінші жолында тапсырмалар санын білдіретін оң бүтін сан $n$ ($1 \le n \le 250000$) берілген.

Екінші жолда ұзындығы $n$ болатын $S$ екілік жолы берілген, мұндағы $S_i$ тапсырма $i$-ден түбірге дейінгі қабырғалардағы барлық мәндердің разрядтық XOR (Bitwise-XOR) мәнін білдіреді.

Шығыс деректер

Бір бүтін санды — $998,244,353$ модулі бойынша жауапты шығарыңыз.

Мысал

Кіріс

4
0101

Шығыс

6

Ескертпе

Ағашты құрудың және балаларын салыстырудың $6$ тәсілі бар: