Counting Symmetric Contiguous Subsequences

You are given a sequence of m integers. Your task is to count the number of contiguous subsequences (subarrays) that are symmetric (i.e. palindromic). A subsequence is symmetric if it reads the same from left to right as it does from right to left. As the answer can be very large, output the result modulo \(10^9+7\).

Note: A single element is considered symmetric by itself.

Example:

Input:  5
        1 2 1 2 1
Output: 9

inputFormat

The first line contains an integer \(m\) representing the length of the sequence. The second line contains \(m\) space-separated integers representing the sequence.

Input Example:

5
1 2 1 2 1

outputFormat

Output a single integer – the number of contiguous symmetric subsequences in the sequence, computed modulo \(10^9+7\).

Output Example:

9

## sample

5
1 2 1 2 1

9