Təsadüfi ağac
Gəlin T ağacının qurulma prosesini nəzərdən keçirək.
Əvvəlcə ağac yalnız bir zirvədən ibarətdir və bu zirvənin nömrəsi 1-dir.
Sonra ağaca 2 ... n nömrəli zirvələr əlavə olunur.
i-ci addımda ağaca i + 1 nömrəli zirvə əlavə olunur, həmçinin bu zirvədən artıq əlavə edilmiş zirvə p-yə (1 ≤ p ≤ i) bir kənar əlavə olunur, hansı ki, bu zirvələr arasında təsadüfi bərabər ehtimalla seçilir.
Qoy V - artıq T-yə əlavə edilmiş zirvələrin çoxluğu olsun.
Onda qoy f(A) - T-nin elə zirvələrinin sayıdır ki, onlar ya A-da, ya da A-nın hər hansı iki zirvəsi arasında olan yolda yerləşir (ola bilsin ki, həm orada, həm də burada).
Sizin vəzifəniz hər zirvə əlavə edildikdən sonra f(A) cəmini artıq T-yə əlavə edilmiş zirvələrin çoxluğunun alt çoxluqları olan bütün A çoxluqları üzrə çıxarmaqdır (Σ f(A) bütün A ⊂ V üzrə). Cavablar çox böyük ola biləcəyi üçün, yalnız cavabın 998244353-ə bölünməsindən qalanı çıxarın.
Giriş məlumatları
Birinci sətir bir ədəd n (2 ≤ n ≤ 200000) - son addımdan sonra ağacda olan zirvələrin sayını ehtiva edir.
Növbəti sətirdə n - 1 tam ədəd p[1], p[2], ..., p[n] (1 ≤ p[i] ≤ i) yerləşir, hansı ki, qrafda i + 1 zirvəsinin və p[i] ilə i + 1 arasında kənarın əlavə olunmasını göstərir. Zəmanət verilir ki, p[i] 1-dən i-yə qədər olan ədədlər arasında təsadüfi bərabər ehtimalla seçilib.
Çıxış məlumatları
Hər zirvə əlavə edildikdən sonra (Σ f(A) bütün A ⊂ V üzrə) 998244353-ə bölünməsindən qalan n - 1 tam ədəd çıxarın.