eolymp
bolt
Try our new interface for solving problems
Problems

Сколько возрастающих - 2

Сколько возрастающих - 2

Time limit 1 second
Memory limit 64 MiB

Пусть задана числовая последовательность, составленная из N целых чисел.

Определить количество строго возрастающих подпоследовательностей данной последовательности.

Input data

В первой строке входного файла дано число N, в следующей строке идут через один или несколько пробелов Nцелых чисел, члены заданной последовательности (1N100000, члены последовательности по модулю не превосходят 1,25·10^5).

Output data

В единственной строке – ответ задачи. Ответ выдать по модулю 1000000009 (10^9+9).

Examples

Input example #1
1
1
Output example #1
1