Поликарп играет в (очередную) стратегическую компьютерную игру. В этой игре он управляет армией наемников.
Поликарп хочет собрать свою армию для выполнения задания. Для найма доступны \(n\) наемников, и армия Поликарпа должна состоять из некоторого подмножества множества доступных наемников.
\(i\)-го наемника можно выбрать только в том случае, если итоговое количество выбранных наемников не менее \(l_i\) (иначе этот наемник считает задание слишком опасным) и не более \(r_i\) (он не хочет делить добычу со слишком большим количеством других наемников). Кроме того, \(m\) пар наемников ненавидят друг друга, и из каждой такой пары можно взять на задание не более одного наемника.
Сколько непустых подмножеств наемников Поликарп должен рассмотреть? Другими словами, посчитайте количество подмножеств наемников, которые не содержат пар наемников, ненавидящих друг друга, и размер которых принадлежит отрезку \([l_i, r_i]\) для каждого наемника из подмножества.
Ответ может быть очень большим, поэтому посчитайте его по модулю \(998244353\).
Выходные данные
Выведите одно целое число — количество подмножеств, удовлетворяющих условию задачи, взятое по модулю \(998244353\).