Задача . F. Независимое множество

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

Для данного графа \(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\).