Bedan Contest #02 - B - Qua cầu - TLEOJ: TLE Online Judge

Bedan Contest #02 - B - Qua cầu

Điểm: 1900 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bridge.inp

Output: bridge.out

Tác giả:

flo

Dạng bài

Ngôn ngữ cho phép

C++, ~~NASM~~, Pascal, pypy3, Python

Đây mới là bản dễ.

Sau một ngày dài đi học mệt mỏi, huyhau6a2 quyết định chơi trò chơi điện tử yêu thích của cậu ấy. Trò chơi khá đơn giản, chỉ cần điều khiển nhân vật vượt qua các chương ngại vật của mỗi màng chơi.

Sau khoảng $69420s$ chơi, huyhau6a2 cuối cùng đã đến được màng cuối cùng. Ở màng chơi này, cậu cần phải điều khiển nhân vật của mình vượt qua $1$ cây cầu. Cây cầu này có tất cả là $n$ ô và ô thứ $i$ sẽ có $a_i$ điểm. Tại mỗi bước đi, huyhau6a2 có thể nhảy sang bất kì ô nào miễn vị trí của ô đó lớn hơn vị trí của ô mà cậu bắt đầu nhảy. Khi vượt qua cây cầu, tích số điểm trên những ô mà huyhau6a2 đã điều khiển nhân vật của mình nhảy lên phải là $1$ số chính phương thì huyhau6a2 mới chiến thắng.

huyhau6a2 thắc mắc có bao nhiêu cách để điều khiển nhân vật của cậu vượt qua cây cầu để cậu giành được chiến thắng. Bạn hãy tính giúp huyhau6a2 nhé.

Input, Output and Scoring

Input (bridge.inp)

Số nguyên dương $n$ $(1 \le n \le 5 \times 10^3)$ .
Dãy $a$ gồm $n$ phần tử $a_1, a_2, ..., a_n$ $(1 \le a_i \le n)$ .

Output (bridge.out)

Với mỗi dòng, hãy in ra kết quả sau khi chia lấy dư cho $1234567891$ .

Scoring

Subtask $1$ $(15\%)$ : $1 \le n \le 20$ .
Subtask $2$ $(35\%)$ : $1 \le n \le 70$ .
Subtask $3$ $(50\%)$ : Không giới hạn gì thêm.

Example

Input

4
2 4 2 1

Output

Note

Có $7$ cách điều khiển là đi lên các ô $(2), (4), (1, 3), (2, 4), (1, 2, 3), (1, 3, 4), (1, 2, 3, 4)$ .

Bình luận

Không có bình luận nào.