Эрик — учитель по теории графов. Сегодня он рассказывает независимое множество и реберно-порожденный подграф.

Для данного графа $$$G=(V,E)$$$ независимым множеством называется такое подмножество вершин $$$V' \subset V$$$, что для каждой пары $$$u,v \in V'$$$, $$$(u,v) \not \in E$$$ (то есть в $$$E$$$ нет ребра, соединяющего две вершины из $$$V'$$$).

Реберно-порожденный подграф состоит из подмножества ребер $$$E' \subset E$$$ и всех вершин оригинального графа, которые инцидентны хотя бы одному ребру подграфа.

Для $$$E' \subset E$$$ обозначим за $$$G[E']$$$ реберно-порожденный подграф такой, что $$$E'$$$ — это множество ребер этого подграфа. Иллюстрации этих определений:

В качестве упражнения на закрепление материала он дал студентам следующую задачу:

Дано дерево $$$G=(V,E)$$$, посчитайте сумму $$$w(H)$$$ по всем реберно-порожденным подграфам $$$H$$$ графа $$$G$$$, кроме пустого, где $$$w(H)$$$ — это количество независимых множеств в $$$H$$$. Формально, посчитайте $$$\sum \limits_{\emptyset \not= E' \subset E} w(G[E'])$$$.

Докажите Эрику, что вы умнее его учеников, предъявив правильный ответ как можно скорее. Обратите внимание, что ответ может быть довольно большой, поэтому выведите его по модулю $$$998,244,353$$$.