Муравей движется по действительной прямой с постоянной скоростью в \(1\) единицу в секунду. Он начинает движение в точке \(0\) и всегда движется вправо (поэтому его позиция увеличивается на \(1\) каждую секунду).
Существует \(n\) порталов, \(i\)-й из которых находится в позиции \(x_i\) и телепортирует в позицию \(y_i < x_i\). Каждый портал может быть либо активным, либо неактивным. Начальное состояние \(i\)-го портала определяется \(s_i\): если \(s_i=0\), то \(i\)-й портал изначально неактивен, если \(s_i=1\), то \(i\)-й портал изначально активен. Когда муравей проходит через портал (т.е., когда его положение совпадает с положением портала):
- если портал неактивен, он становится активным (в этом случае путь муравья не затрагивается);
- если портал активен, то он становится неактивным, а муравей мгновенно телепортируется в позицию \(y_i\), где продолжает двигаться как обычно.
Сколько времени (с момента начала движения) потребуется муравью, чтобы достичь позиции \(x_n + 1\)? Можно показать, что это произойдет за конечное время. Поскольку ответ может быть очень большим, вычислите его по модулю \(998\,244\,353\).
Выходные данные
Выведите количество времени в секундах, которое пройдет с момента начала движения муравья до момента достижения им позиции \(x_n+1\). Поскольку ответ может быть очень большим, выведите его по модулю \(998\,244\,353\).
Примечание
Объяснение первого примера: Муравей перемещается следующим образом (кривая стрелка обозначает телепортацию, прямая стрелка обозначает обычное движение со скоростью \(1\), а время, затраченное на движение, написано над стрелкой). \(\) 0 \stackrel{6}{\longrightarrow} 6 \leadsto 5 \stackrel{3}{\longrightarrow} 8 \leadsto 1 \stackrel{2}{\longrightarrow} 3 \leadsto 2 \stackrel{4}{\longrightarrow} 6 \leadsto 5 \stackrel{2}{\longrightarrow} 7 \leadsto 4 \stackrel{2}{\longrightarrow} 6 \leadsto 5 \stackrel{4}{\longrightarrow} 9 \(\) Обратите внимание, что общее время составляет \(6+3+2+4+2+2+4=23\).
Пояснение второго примера: Муравей перемещается следующим образом (кривая стрелка обозначает телепортацию, прямая стрелка обозначает обычное движение со скоростью \(1\), а время, затраченное на движение, написано над стрелкой). \(\) 0 \stackrel{454971987}{\longrightarrow} 454971987 \leadsto 406874902 \stackrel{48097086}{\longrightarrow} 454971988 \(\) Обратите внимание, что общее время составляет \(454971987+48097086=503069073\).
Объяснение третьего примера: Поскольку все порталы изначально неактивны, муравей не будет телепортирован и попадет прямо из \(0\) в \(x_n+1=899754846+1=899754847\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 2 0
6 5 1
7 4 0
8 1 1
|
23
|
|
2
|
1
454971987 406874902 1
|
503069073
|
|
3
|
5
243385510 42245605 0
644426565 574769163 0
708622105 208990040 0
786625660 616437691 0
899754846 382774619 0
|
899754847
|
|
4
|
5
200000000 100000000 1
600000000 400000000 0
800000000 300000000 0
900000000 700000000 1
1000000000 500000000 0
|
3511295
|