We are looking for variable subsequences of a given sequence
.
A subsequence is obtained from a sequence by removing any number of its terms
(possibly 0).
More formally, a subsequence of the sequence is any sequence
A variable subsequence is a subsequence such that every two its
consecutive terms are different.
For example, the sequence is a variable subsequence of the sequence
.
We would like to know how many distinct and
nonempty variable subsequences
of a given sequence are there.
Two subsequences are considered distinct if the sets of positions in
corresponding to them are different.
For instance, the sequence contains two distinct variable
subsequences of the form .
Input
The first line of the standard input contains one integer
(), denoting the length of the sequence .
The second line contains integers
().
Output
Your program should write to the first and only line of the standard output
a single integer: the number of nonempty variable subsequences of the
input sequence modulo .
Example
For the input data:
4
1 2 1 1
the correct result is:
9
Explanation of the example:
The considered subsequences of the sequence are:
- counted three times,
- counted once,
- counted once,
- counted twice and
- counted twice.
Task author: Jakub Radoszewski.
Kontakt
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.