პალიტრა

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: COCI, 2013/14, #2


მირკოს აქვს წიგნი, რომელშიც N ცალი ფიგურაა გასაფერადებელი. გარდა ამისა, მაქს აქვს ფუნჯი და K ფერის მქონე პალიტრა. ფიგურები გადანომრილია 1-დან N-მდე.  მირკომ გადაწყვიტა, რომ ყოველი ფიგურა გააფერადოს პალიტრაში შემავალი K ფერიდან ერთ-ერთით. თუმცა მირკოს უყვარს უცნაურობანი. მან აარჩია N ცალი fi რიცხვი და გადაწყვიტა, რომ ყოველი i ფიგურა განსხვავდებოდეს ფერით fi ნომრის მქონე ფიგურიდან, გარდა იმ შემთხვევისა, როცა fi=i. თუ fi=i, მაშინ ფიგურა fi ფერით შეიძლება შეიღებოს ნებისმიერი ფერით, თუკი სხვა პირობები დაცულია. მირკოს აინტერესებს, ფიგურების შეღებვის რამდენი განსხვავებული ვარიანტი არსებობს. რადგან პასუხი შეიძლება ძალიან დიდი რიცხვი იყოს, ის გამოიტანეთ 1 000 000 007-ზე ნაშთით.

შესატანი მონაცემები: პირველ სტრიქონში ორი მთელი დადებითი რიცხვი N და K (1 ≤ N, K ≤ 1 000 000). მომდევნო სტრიქონი შეიცავს N მთელ დადებით fi რიცხვს (1 ≤ fi ≤ N), პირობაში აღწერილის მიხედვით.

გამოსატანი მონაცემები: ერთადერთ სტრიქონში ერთი მთელი რიცხვი - ფიგურების გაფერადების ყველა შესაძლო ვარიანტების რაოდენობა. 

 

 




მაგალითები

შესატანი მონაცემები
2 3 2 1 დაკოპირება
გამოსატანი მონაცემები
6 დაკოპირება
შესატანი მონაცემები
3 4 2 3 1 დაკოპირება
გამოსატანი მონაცემები
24 დაკოპირება
შესატანი მონაცემები
3 4 2 1 1 დაკოპირება
გამოსატანი მონაცემები
36 დაკოპირება
შესატანი მონაცემები
3 4 1 1 2 დაკოპირება
გამოსატანი მონაცემები
36 დაკოპირება

შენიშვნა

პირველი მაგალითის განმარტება: მირკოს აქვს 3 ფერი და გადაწყვიტა, რომ ნახატი 2 არ უნდა იყოს ნახატი 1 ფერის ანალოგიური. შესაძლო გაფერადებებია (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), სადაც პირველი რიცხვი ფრჩხილებში აღნიშნავს პირველი ნახატის ფერს, ხოლო მეორე რიცხვი - მეორე ნახატის ფერს.

მეოთხე მაგალითის განმარტება: მირკოს აქვს 3 ფერი. რაიმე პირობა პირველი ნახატის გაფერადებაზე არ გვაქვს და ის შეიძლება ნებისმიერი ფერით გაფერადდეს. მეორე უნდა განსხვავდებოდეს პირველისგან, ხოლო მესამე - მეორისაგან. ეს ნიშნავს, რომ ეს ორი ნახატი შეიძლება გაფერადდეს დანარჩენი 3 ფერით. სულ გამოდის 36 კომბინაცია.