Cho mảng \(A\) gồm \(n\) phần tử. Một dãy con của \(A\) là một dãy thu được bằng cách chọn một số phần tử theo thứ tự tăng dần chỉ số (không nhất thiết liên tiếp).
Yêu cầu: đếm số dãy con khác nhau và khác rỗng của \(A\).
\InputFile
- Dòng đầu gồm số nguyên \(n\) (\(1 \le n \le 10^6\)).
- Dòng thứ hai gồm \(n\) số nguyên \(A_i\) (\(1 \le A_i \le 10^6\)).
\OutputFile
In ra số lượng dãy con khác nhau, modulo \(123456789\).
Example
Test 1
Input
3
1 2 1Output
6
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.