D. Санамсаргүй функц ба мод

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд $n$ оройгоос тогтох үндэстэй мод байв. Оройнуудыг $1$-ээс $n$ хүртэлх бүхэл тоонуудаар дугаарлая (эдгээр тоонууд нь өөрсдөө орно). Модны үндэс нь $1$ дугаартай орой байх юм. $i > 1$ байх орой бүрийн хувьд $i$ оройн эх үндэс нь $p_{i}$ байна. Бид $i$ дугаартай оройг уг оройн шууд эх үндэс $p_{i}$-ын үр гэж нэрлэнэ.

Танд анхандаа бүгдээрээ улаанаар будагдсан оройнууд байв. Та модны хэсэг оройнуудыг дахин будахыг хүсэж байгаа юм. Ингэж будахын тулд та будалтын функц ашиглах бөгөөд модны үндсийг та аргумент гэж үзэх юм. Доор тус функцийн хуурмаг код өгөгдөв:

count = 0 // global integer variable   

rnd() { // this function is used in paint code  
    return 0 or 1 equiprobably  
}  

paint(s) {  
    if (count is even) then paint s with white color  
    else paint s with black color  

    count = count + 1  

    if rnd() = 1 then children = [array of vertex s children in ascending order of their numbers]  
    else children = [array of vertex s children in descending order of their numbers]  

    for child in children { // iterating over children array  
        if rnd() = 1 then paint(child) // calling paint recursively  
    }  
}

Тус функцийн үр дүнгээр зарим орой нь өөрсдийн өнгөө цагаан эсвэл хар болгон өөрчлөх ба зарим нь улаан хэвээр үлдэх юм.

Таны даалгавар бол модны оройнуудыг будах боломжит хэчнээн тооны ялгаатай будалт байгааг тодорхойлох юм. Хэрэв тэгээс ялгаатай магадлалаар ганц $paint(1)$ ашиглан уг будалтыг үүсгэх бол уг будалтыг боломжит гэж үзнэ. Хэрэв 2 будалтад ялгаатай өнгөөр будагдсан хос оройнууд оршин байвал бид уг будалтуудыг ялгаатай гэж үзнэ. Хариу нь хэтэрхий том тоо байж болох тул $1000000007$ ($10^{9} + 7$)-д хуваан үлдэгдлийг хэвлэнэ үү.

Оролт

Эхний мөрөнд модны оройн тоог илэрхийлэх бүхэл тоо $n$ ($2 ≤ n ≤ 10^{5}$) өгөгдөнө.

2-дахь мөрөнд $n - 1$ ширхэг бүхэл тоо $p_{2}, p_{3}, ..., p_{n}$ ($1 ≤ p_{i} < i$) өгөгдөнө. $p_{i}$ тоо нь $i$-дахь оройн эх үндэс байна.

Гаралт

Бодлогын хариултыг $1000000007$ ($10^{9} + 7$) модулаар бодсон бүхэл тоон хариуг хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
4
1 2 1
Гаралт
8
Оролт
3
1 1
Гаралт
5

Тэмдэглэл

Эхний жишээний бүх боломжит будалтыг доор дүрслэв.

Сэтгэгдлүүдийг ачааллаж байна...