Alice Margatroid cần dọn tuyết trên mái nhà. Cô sẽ dùng chọn ra ~m~ con búp bê của mình để thực hiện nhiệm vụ. Alice có ~n~ thùng đựng búp bê, thùng thứ ~i~ có ~a_i~ con, và cô muốn mỗi thùng chỉ được chọn ra tối đa 1 con búp bê. Hỏi có bao nhiêu cách để chọn ra ~m~ con búp bê.

Input

• Dòng đầu tiên gồm 2 số tự nhiên ~n, m~ ~(1 \le m \le n \le 1000)~
• Dòng tiếp theo gồm ~n~ số tự nhiên là số lượng búp bê của từng thùng. (~1 \le a[i] \le 10^9~)

Output

• Gồm 1 số tự nhiên duy nhất là số cách chọn búp bê modulo ~10^9 + 7~

Sample Test

Input:

3 2
1 2 1

Output:

5

Giải thích:

• Có 5 cách chọn là: ~\{1, 2.1\}, \{1, 2.2\}, \{1, 3\}, \{2.1, 3\}, \{2.2, 3\}~ với ~x.y~ là con búp bê thứ ~y~ của thùng thứ ~x~

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.

Hôm nay Kaku Seiga đến Nhân Thôn để đi ăn trộm. Có ~n~ ngôi nhà ở cạnh nhau. Số tiền trong ngôi nhà thứ ~i~ là ~a_i~. Cô sẽ không vào ~k~ nhà liên tiếp trở lên vì sẽ rất dễ bị phát hiện. Hãy cho cô biết cô sẽ lấy được số tiền lớn nhất là bao nhiêu?

Input:

• Dòng đầu gồm 2 số nguyên dương ~n~ và ~k~.
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~.

Output:

• Số tiền lớn nhất Seiga có thể lấy được

Sample Test

Input:

6 3
6 10 10 13 10 10

Output:

40

Giải thích:

• Chọn các số 2 3 5 6.

Giới hạn:

• ~1 \le k \le n \le 10^5, 1 \le a_i \le 10^6~

Sủi là người có máu M nên layout 40% là chưa đủ khổ dâm. Sủi làm một chiếc bàn phím mới có dạng ~m~ chữ cái đầu của bảng chữ cái tiếng Anh nằm cạnh nhau. Cậu cần đánh một đoạn văn bản ~s~ có độ dài ~n~ chỉ gồm các chữ cái trong bàn phím. Sủi sẽ gõ từng chữ lần lượt theo thứ tự từ trái sang phải và chi phí để di chuyển từ một chữ sang chữ khác là khoảng cách giữa 2 chữ đó. Chi phí của văn bản là tổng các chi phí di chuyển giữa các chữ hay: ~\sum_{i=1}^{n - 1} | p_{s_{i + 1}} - p_{s_i} | ~ với ~p_x~ là vị trí kí tự ~x~ từ trái sang phải của bàn phím.

Input

• Dòng đầu gồm 2 số ~n~ và ~m~.
• Dòng tiếp theo là xâu gồm ~n~ kí tự chứa ~m~ kí tự đầu tiên trong bảng chữ cái tiếng Anh.

Output

• In ra một số nguyên duy nhất là chi phí nhỏ nhất có thể.

Sample Test

Input:

6 3
aacabc

Output:

5

Giải thích:

• Sắp xếp thành bac

Ràng buộc

• Subtask 1: ~1 \le n \le 100, 1 \le m \le 10~ (40% số điểm).
• Subtask 2: ~1 \le n \le 100000, 1 \le m \le 10~ (30% số điểm).
• Subtask 3: ~1 \le n \le 100000, 1 \le m \le 20~ (30% số điểm).

3 nàng tiên ánh sáng sau khi ăn xong quyết định ai rửa bát bằng trò chơi rút bài, ai thua sẽ phải rửa bát. Do ngày hôm qua Star Sapphire đã rửa bát nên chỉ có Sunny Milk và Luna Child chơi ngày hôm nay.

Bộ bài gồm không quá 400 lá bài, 2 người lần lượt chơi, mỗi lượt chọn 1 trong 2 lá ở 2 đầu bộ bài.

Bộ bài gồm các lá sau:

• # lá bài bình thường.
• 1, 2, 3, ... 9, lá bài cộng điểm, cộng số điểm tương ứng ghi trên lá bài.
• C, H, I, M, lá bài chìa khóa, là chìa khóa để mở các cánh cửa với chữ cái viết thường tương ứng ghi trên lá bài, một chìa khóa có thể được sử dụng nhiều lần.
• c, h, i, m, lá bài cánh cửa, cần lá bài chìa khóa để mở.

Trò chơi kết thúc khi có 1 người không thể rút bài hoặc hết bài (nếu còn bài thì bắt buộc phải rút). Do chơi 400 lá bài thì rất lâu nên 3 nàng tiên nhờ bạn xác đinh luôn ai là người phải rửa bát nếu cả Sunny Milk và Luna Child để chơi tối ưu. Sunny Milk là người đi trước.

Input:

• Gồm một xâu độ dài không quá 400 kí tự là các lá bài của bộ bài.

Output:

• In ra 2 dòng. Nếu phân định thằng thua in ra "SunnyMilk" hoặc "LunaChild" là người phải rửa bát, nếu hòa in ra "StarSapphire". Dòng tiếp theo in ra hiệu số điểm của Sunny Milk trừ đi điểm của Luna Child.

Sample Test 1

Input:

#4##

Output:

LunaChild
4

Sample Test 2

Input:

Ch#1#cH

Output:

SunnyMilk
-1

Ibuki Suika rất thích uống rượu nhưng uống rượu không thì rất chán nên cô đi mua xiên que về ăn. Có ~n~ cửa hàng bán thịt xếp theo thứ tự từ trái sang phải và cửa hàng thứ ~i~ bán một miếng thịt loại ~a_i~. Cô muốn xiên của mình có ~m~ miếng thịt. Đến một cửa hàng cô hoặc là không mua cửa hàng đó hoặc mua miếng thịt và xiên vào que theo thứ tự. Hỏi có tất cả bao nhiêu cách xiên thịt khác nhau.

Input:

• Dòng đầu tiên là hai số tự nhiên ~n~ và ~m~.
• Dòng tiếp theo gồm ~n~ số lần lượt là loại thịt các cửa hàng bán.

Output:

• In ra một số nguyên duy nhất là số cách xiên thịt khác nhau modulo ~10^9+7~

Sample Test 1

Input:

3 2
1 2 3

Output:

3

Sample Test 2

Input:

4 3
2 3 3 2

Output:

3

Giải thích:

• Ở test 1 có 3 xiên là ~\{1, 2\}, \{1, 3\}, \{2, 3\}~
• Ở test 2 có 3 xiên là ~\{2, 3, 2\}, \{2, 3, 3\}, \{3, 3, 2\}~

Ràng buộc

• ~n, m \le 1000, a_i \le 10^9~