Kiramai Stone


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Hành tinh Crystalia (The Land of Jewels Crystalia) là một hành tinh được cấu tạo bởi đá quý và là nơi cư trú của người dân Crystalian. Tại đây, có những viên đá quý đã tiến hóa và sở hữu trí giác và sức mạnh toàn năng, chúng được gọi là Kiramai Stones. Nhưng không may, hành tinh này đã bị đô hộ và tàn phá bởi Quân đoàn bóng tối Yodonheim (Dark Empire Yodonheim). Mục tiêu tiếp theo của chúng là Trái Đất. Dựa vào những cơ sở dữ liệu gửi về từ nhà vua của Crystalia -- Oradin, tập đoàn CARAT đã biết được âm mưu này và đã lên kế hoạch chế tạo các vũ khí, cơ khí từ các Kiramai Stone và tập hợp lực lượng các chiến binh Kiramager.

Trong quá trình chế tạo, Hakataminami -- người đứng đầu của CARAT đã gặp một số khó khăn, đó là một số Kiramai Stone bị nọc độc của Numajo (Witch of the Stagnant Sea Numajo -- một vị tướng xảo quyệt của Yodonheim) làm cho rỉ sét (dù chúng không phải là kim loại) và mỗi trong số chúng cần một loại Kiramai Stone khác để hóa giải nọc độc này. Điều này tức là khi chế tạo một vũ khí hoặc cơ khí nào đó, để thêm Kiramai Stone bị rỉ sét, cần thêm Kiramai Stone hóa giải nó vào trước. Điều này đã khiến Hakataminami gặp không ít khó khăn trong khi chế tạo các Kiramai Shot và Kiramai Sword do số lượng Kiramai Stone cần sử dụng rất lớn, nhưng nhờ có bộ não thiên tài, ông đã lập trình được một ứng dụng đưa ra được một thứ tự sử dụng Kiramai Stone thỏa mãn yêu cầu trên.

Và để thách thức lại độc giả, ông đã đưa ra một bài toán: Cho $N$ viên Kiramai Stone, được đánh số từ 1 đến $N$. Với viên thứ $i$, cho một chỉ số $a_i$, nếu $a_i=0$, viên đá này chưa bị rỉ sét, ngược lại nó cần viên đá thứ $a_i$ để hóa giải. Hãy đếm xem có bao nhiêu thứ tự sử dụng các viên đá này và đưa ra một thứ tự bất kỳ.

Lưu ý: Một viên đá có thể hóa giải nhiều viên khác và một viên bị rỉ sét vẫn có thể tiếp tục hóa giải viên khác nếu nó đã được hóa giải từ trước.

Dữ liệu

  • Dòng đầu tiên chứa số nguyên dương $N (N \le 10^5)$;
  • Dòng tiếp theo chứa $N$ số nguyên $a_i (a_i≠i; 0 \le a_i \le N)$.

Kết quả

  • Dòng đầu tiên ghi số lượng thứ tự thỏa mãn sau khi chia lấy dư cho $1000000007$;

Ví dụ

Ví dụ 1

input

4
2 0 2 0

output

8
Ví dụ 2

input

3
0 1 2

output

1
Ví dụ 3

input

3
0 0 0

output

6

Giải thích

Dữ liệu đảm bảo không tồn tại dãy các viên đá $p_1,p_2,p_3,...,p_M$ sao cho $p_1$ hóa giải $p_2$, $p_2$ hóa giải $p_3$, ...,$p_{M-1}$ hóa giải $p_M$ và $p_M$ hóa giải $p_1$.


Comments

There are no comments at the moment.