龚自珍写了《己亥杂诗》，而爆破鬼才nodgd正在炸地下室，简称“己亥炸室”。

地下室组成树形结构，与地面相连的地下室是树形结构的根。从某个地下室朝地面走到达的下一间地下室是这间地下室的上层地下室。炸地下室之前要在地下室安放炸药，每间地下室安放炸药的数量有上限。并且nodgd规定，一间地下室的上层地下室炸药数量不能超过它的炸药数量，除非它的上层地下室刚好达到炸药数量上限。

那么问题来了，有多少种不同的炸药安放方式呢？

第一行一个整数$n$，表示地下室的数量。其中编号为$1$的地下室与地面相连。

第二行$n$个整数$c_1,c_2,\dots,c_n$，表示每个地下室的炸药数量上限。

第三行$n-1$个整数$u_2,u_3,...,u_n$，表示$2\sim n$每个地下室的上层地下室编号。

输出一个整数，表示炸药安放方案数$\mod{1,234,567,891}$ 的结果。

样例说明1

• 如果第$1$个地下室放$0$个炸药，第$2,3$个地下室都可以放$0,1,2,3$个炸药，共$16$种方案；
• 如果第$1$个地下室放$1$个炸药，第$2,3$个地下室都可以放$1,2,3$个炸药，共$9$种方案；
• 如果第$1$个地下室放$2$个炸药，第$2,3$个地下室都可以放$0,1,2,3$个炸药，共$16$种方案；

累计总共$41$种方案。

样例说明2

• 如果第$1$个地下室放$0$个炸药，第$2$个地下室可以放$0,1$个炸药，第$3$个地下室可以放$0,1,2,3$个炸药，共$8$种方案；
• 如果第$1$个地下室放$1$个炸药，第$2$个地下室可以放$1$个炸药，第$3$个地下室可以放$1,2,3$个炸药，共$3$种方案；
• 如果第$1$个地下室放$2$个炸药，第$2$个地下室无论放多少炸药都不行，共$0$种方案；
• 如果第$1$个地下室放$3$个炸药，第$2$个地下室可以放$0,1$个炸药，第$3$个地下室可以放$0,1,2,3$个炸药，共$8$种方案；

累计总共$19$种方案。

数据规模与约定

对于20%的数据，\(n\leq 8\)，\(c_i\leq 10\)；

对于另外10%的数据，\(c_i=1\)；

对于另外10%的数据，\(u_i=i-1\)；

对于另外20%的数据，\(n\leq 10^5\)，\(c_i\leq 10\)；

对于100%的数据，$1\leq n\leq 5\times 10^5$，$1\leq c_i\leq 100$，$1\leq u_i\leq n$且保证是一棵树。