Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: skliaustai.in

Rezultatų failas: skliaustai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Skliaustai

Yra 2k skirtingų skliaustų simbolių, sudarančių k porų.

Teisinga skliaustų seką apibrėžiame taip:

  • Tuščia skliaustų seka yra teisinga.
  • Jei A yra teisinga skliaustų seka, ir ( ir ) yra atitinkami skliaustų pora, tai "( A )" yra teisinga skliaustų seka
  • Jei A ir B yra teisingos skliaustų sekos, tai "AB" yra teisinga skliaustų seka.

Pavyzdžiui, jei turime tris skirtingus skliaustų tipus ((), [], {}), tai:

  • Šios sekos yra teisingos: "", "()", "{()}[]", "{[](())}{}[()]".
  • Šios sekos nėra teisingos: "(", ")(", "[)", "{}[", "[{]}".

Graži skliaustų seka yra tokia teisinga skliaustų seka, kurioje bet kurie du gretimi simboliai yra skirtingi.

Suskaičiuokite kiek yra skirtingų gražių ilgio 2n skliaustų sekų jei yra k skirtingų skliaustų tipų.

Pradiniai duomenys

Pirmoje eilutėje yra du skaičiai n ir k (0\\leqn\\leq10^4,1\\leqk\\leq10^6).

Rezultatai

Išveskite vieną skaičių - kiek yra skirtingų gražių skliaustų sekų iš 2n simbolių. Kadangi rezultatas gali būti labai didelis, išspausdinkite jį moduliu 10^9+7.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
6 1
 
1
 
Vienintelė galima seka: ()()()()()()
 
2 3
 
15
 








4244 157210




99727199