Question 1

Problem Statement

Question 1 Problem Description You are given a Tree of N nodes, rooted at 1. The i+1-th node's parent is P[i] (guaranteed P[i] < i) Each node has value A[i] Find the number of ways to pick a non-empty subset of nodes such that: Sum of values of picked nodes is divisible by X No two nodes in subset are adjacent. Since the answer can be large return it modulo 10 9 + 7. Input Format The first line contains an integer, N, denoting the number of elements in A. The next line contains an integer, X. Each line i of the N subsequent lines (where 1 ≤ i ≤ N) contains an integer describing A[i]. The next line contains an integer, M, denoting the number of elements in P. Each line i of the M subsequent lines (where 1 ≤ i ≤ M) contains an integer describing P[i]. Constraints 1 ≤ N ≤ 10 3 1 ≤ X ≤ 10 2 1 ≤ A[i] ≤ X N-1 ≤ M ≤ N-1 Examples Example 1: Input: 2 2 2 1 1 Output: 2 Explanation: N=2, X=2, A=[2 2], M=1, P=[1] The ways to pick the nodes are: (1) , (2) beca