Mai và việc cắt giảm nhân sự

Xem dạng PDF

Gửi bài giải

Điểm: 0,30 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Nguồn bài:
stolen
Dạng bài
Ngôn ngữ cho phép
C++, Pascal, Python

Mai Sakurajima thay vì theo nghiệp diễn xuất giờ đã đi làm trong một công ty lớn. Trớ trêu thay, công ty ấy đang có một cuộc cắt giảm nhân sự. Công ty của cô có ~n~ người, đánh số từ 1 đến ~n~. Giám đốc có cấp cao nhất, số thứ tự là 1. Mô hình tổ chức của công ty như sau: mỗi nhân viên có duy nhất một cấp trên tực tiếp. Giám đốc có một danh sách ghi lại cấp trên trực tiếp của mỗi nhân viên từ 2 đến ~n~ (nhân viên thứ 1 chính là giám đốc).

Công ty muốn cắt giảm nhân viên theo quy tắc sau: Nếu một nhân viên bất kì bị cắt giảm thì tất cả các nhân viên cấp dưới của nhân viên đó cũng bị cắt giảm. Giám đốc sẽ không bị cắt giảm. Có thể không có nhân viên nào bị cắt giảm. Nói cách khác, nếu coi công ty là một cái cây gốc 1, khi cắt đỉnh ~i~, mọi đỉnh trong cây con gốc ~i~ cũng sẽ bị cắt.

Vì rất lo lắng cho công việc của mình, hãy giúp Mai xác định số lượng phương án cắt giảm nhân viên khác nhau của công ty thỏa mãn điều kiện trên, vì số lượng có thể rất lớn nên hãy in ra phần dư của kết quả cho ~10^9+7~.

Input:

  • Dòng đầu chứa số nguyên dương n. (~1 \le n \le 10^5~).
  • Từ dòng thứ 2 đến dòng thứ ~n~, mỗi dòng in ra một số là cấp trên trực tiếp của nhân viên thứ ~i~.

Output:

  • In ra số nguyên duy nhất là phần dư của số lượng phương án cắt giảm nhân viên khác nhau của công ty cho ~10^9+7~. Hai phương án khác nhau khi tập nhân viên còn lại khác nhau.

Sample Test

Input:

4
1
1
3

Output:

6
Giải thích:

Có 6 phương án để cắt giảm nhân viên như sau:

  • Không cắt giảm nhân viên nào.
  • Cắt giảm nhân viên 2.
  • Cắt giảm nhân viên 3
  • Cắt giảm nhân viên 4.
  • Cắt giảm nhân viên 2,3.
  • Cắt giảm nhân viên 2,4.