Крипто

Pəşo n ədədindən ibarət bir permutasiyanı şifrələyir, burada hər bir ədəd 1-dən n-ə qədər yalnız bir dəfə rast gəlinir. O, aşağıdakı alqoritmdən istifadə edir:

1. Permutasiyadakı bütün ədədləri dəyişdirin, x ədədi x-ci sadə ədədə dəyişdirilir.

2. n-dən çox olmayan təsadüfi müsbət k seçin.

3. Alınan ardıcıllığın ardıcıl elementlərindən ibarət olan və ən azı k element ehtiva edən bütün seqmentləri nəzərdən keçirin. Onların hər biri üçün k minimal ədədin hasilini yazın.

4. p əvvəlki addımda alınan müxtəlif hasilatların sayına bərabər olsun.

5. Permutasiyanın şifri "n k p" üçlüyü olacaq.

Məsələn, gəlin görək Pəşo {4, 1, 3, 2} permutasiyasını necə şifrələyir:

1. İlk 4 sadə ədəd 2, 3, 5 və 7-dir. Buna görə də o, permutasiyada

• 4-ü dördüncü sadə ədədə, yəni 7-yə dəyişdirir;

• 1-i birinci sadə ədədə, yəni 2-yə dəyişdirir;

• 3-ü üçüncü sadə ədədə, yəni 5-ə dəyişdirir;

• 2-ni ikinci sadə ədədə, yəni 3-ə dəyişdirir.

Pəşo 7, 2, 5, 3 ardıcıllığını alır.

2. İndi o, təsadüfi k ədədini seçir. Qoy k = 2.

3. Alınan ardıcıllığın bütün seqmentləri:{7}, {2}, {5}, {3}, {7, 2}, {2, 5}, {5, 3}, {7, 2, 5}, {2, 5, 3}, {7, 2, 5, 3}

Onlardan yalnız k = 2 element ehtiva edənləri saxlayır və hər biri üçün iki minimal elementin hasilini hesablayır:

• {7, 2} 2 * 7 = 14

• {2, 5} 2 * 5 = 10

• {5, 3} 3 * 5 = 15

• {7, 2, 5} 2 * 5 = 10

• {2, 5, 3} 2 * 3 = 6

• {7, 2, 5, 3} 2 * 3 = 6

Aşağıdakı hasilatlar alınır {14, 10, 15, 10, 6, 6}

4. Cəmi dörd müxtəlif hasilat var: {6, 10, 14, 15}, beləliklə p = 4.

5. Əsas permutasiyanın şifri "4 2 4".

Pəşo tez başa düşdü ki, alqoritm ardıcıllıqları gözlədiyindən daha yaxşı şifrələyir. O, kodun qarşılıqlı tək mənalı olmasını istəyirdi, lakin məlum oldu ki, alınan şifri həmişə deşifrə etmək mümkün deyil.

Verilmiş şifrə görə müxtəlif mümkün ilkin permutasiyaların sayını hesablayan proqram yazın. Cavabı 1 000 000 007-yə bölünmənin qalıqını çıxarın.

Giriş məlumatları

Bir sətirdə üç tam ədəd n, k (1 ≤ k ≤ n ≤ 400) və p (1 ≤ p ≤ 10^9) verilir.

Çıxış məlumatları

Şifri "n k p" olan permutasiyaların sayını çıxarın. Cavabı 1 000 000 007 modulunda çıxarın.

İzah

Birinci nümunədə {1, 3, 2} və {2, 3, 1} permutasiyaları "3 2 3" kimi şifrələnə bilər.

İkinci nümunədə {1, 2, 4, 3}, {1, 3, 2, 4}, {1, 4, 2, 3}, {2, 1, 4, 3}, {2, 3, 1, 4}, {2, 4, 1, 3}, {3, 1, 4, 2}, {3, 2, 4, 1}, {3, 4, 1, 2}, {3, 4, 2, 1}, {4, 1, 3, 2}, {4, 2, 3, 1} permutasiyaları uyğun gəlir.

Nümunələr