# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Recently Alex has participated in a programming contest.

He became 1st runner up. He couldn’t solve one problem. He is so upset. Now Alex comes to you and gives you the problem.

Alex gives you an integer array **arr _{1}, arr_{2}, arr_{3}, …., arr_{n}**.

An array **p** is called to be a sub-sequence of **arr** if it is possible to remove some elements from an array **arr** to get **p**.

Array **p _{1}, p_{2}, p_{3}, … , p_{m}** is called to be “

The array a has exactly 2^{n}−1 different sub-sequences (excluding an empty sub-sequence).

**Find the number of “Happy” sub-sequences.**

The first line contains an integer **n (1 <= n <= 100000)** — the length of the array **arr**.

The next line contains integers **arr _{1}, arr_{2}, arr_{3},…, arr_{n} (1 <= arr_{i} <= 10^{6}).**

Print exactly one intger - the number of “**Happy**” subsequences taken modulo **10 ^{9} + 7**.

Input | Output |
---|---|

5 2 2 1 22 14 | 13 |

Input | Output |
---|---|

1 5 | 1 |

91% Solution Ratio

mepromeeEarliest,

neo11235Fastest, 0.0s

sakib_muhitLightest, 131 kB

cgspyn_868Shortest, 607B

Login to submit