Software Engineer

You are given a binary tree. Your task is to return the count of the diagonal paths to the leaf of the given binary tree such that all the values of the nodes on the diagonal are equal.

Note:

A diagonal traversal Consider lines of slope -1 passing between nodes.
         1
       /    \
     4        2
    /  \        \
   8    5         3
       /  \       /
      9    7      6

Example: Here potential diagonals are: 
1 -- 2 -- 3
4 -- 5 -- 7 -- 6
8 -- 9 -- 7 

For Example

Input: 

     5
  /  \
 6      5
  \       \
   6       5

Output: 2 

Explanation: 

Diagonal 6 – 6 and 5 – 5 contains equal value. Therefore, the required output is 2.

You have been given an integer array/list 'ARR' of size 'N'. Your task is to return the total number of those subsequences of the array in which all the elements are equal.

A subsequence of a given array is an array generated by deleting some elements of the given array with the order of elements in the subsequence remaining the same as the order of elements in the array.

Note :

As this value might be large, print it modulo 10^9 + 7