Алимхүүд $n$ оройтой мод байв. Зарим орой нь (ядаж нэг) хар ѳнгѳтэй ба үлдсэн нь цагаан ѳнгѳтэй байлаа.

Алимхүүгийн модноос $k$ $(0 ≤ k < n)$ ирмэгийг агуулсан олонлогийг авч үзье. Хэрвээ Алимхүү эдгээр ирмэгийг устгавал мод $(k + 1)$ хэсэгт хуваагдна. Хэсэг бүр нь ѳнгѳт мод байхыг тэмдэглэе.

Одоо Алимхүү хэсэг бүр нь яг нэг хар орой агуулсан байхаар хуваадаг олонлогуудын тоог олохыг хүсч байна. Энэ тоог $1000000007$ ($10^{9} + 7$) тоонд хуваахад гарах үлдэгдлийг олно уу.

Оролт

Эхний мѳр модны оройн тоо $n$-г ($2  ≤ n ≤ 10^{5}$) агуулна.

Хоёрдугаар мѳр модыг илэрхийлнэ: $n - 1$ ширхэг бүхэл тоо $p_{0}, p_{1}, ..., p_{n - 2}$ ($0 ≤ p_{i} ≤ i$) агуулна. Энд $p_{i}$ нь $(i + 1)$ орой $p_{i}$ оройтой холбогдсоныг илтгэнэ. Модны оройнуудыг $0$-ээс $n - 1$ хүртэл дугаарлагдсан гэж үзье.

Гуравдугаар мѳр оройнуудын ѳнгийг илэрхийлнэ: $n$ ширхэг бүхэл тоо $x_{0}, x_{1}, ..., x_{n - 1}$ ($x_{i}$ нь $0$ юмуу $1$) агуулна. Хэрвээ $x_{i}$ $1$-тэй тэнцүү бол $i$ орой хар ѳнгѳтэй. Эсрэг тохиолдолд цагаан ѳнгѳтэй байна.

Гаралт

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