Combinatorics

ID 38499. Skittles coloring

N pins are placed in a row. Gromozeka paints each of them one of the K colors from her paint cans. For aesthetic reasons, any two adjacent pins should be painted in different colors. Find the number of possible ways to color the skittles.

Input
The input string contains two integers N and K (\(1<=N<=1000\),  \(2<=K<=1000\)).

Imprint
Display the answer to the problem. It is guaranteed that the correct answer does not exceed \(2^{31}-1\).
 

Examples

ID 38588. March

There is a N person. The name of the ith person is Si . We want to select three people so that the following conditions are met:
- The name of each selected person starts with M, A, R, C or H< /code>; 
- there are no people whose names start with the same letter among the selected people.
How many ways are there to choose three people without paying attention to the order?

Input
The first line contains an integer N (\(1<=N<=10^5\)) The next N lines contain names Si  - a string consisting only of English capital letters, the string length is not more than 10 characters. All names are different.

Imprint
Print the answer to the problem. Please note that the answer may not be a 32-bit integer type.
 

ID 38634. Number cookies - 2

Gromozeka has N cookies. The i-th (1<=i<=N) cookie has an integer xi written on it. He chooses one or more of these cookies so that the average value of the integers written on the chosen cookies is A.
In what ways can he make his choice?

Input
The first line contains two integers N (1<=N<=50) and A (1<=A<=50). The second line contains N integers - xi (1<=xi<=50).

Imprint
Print one number - the number of ways to choose such cookies so that the average value of all written numbers on the cookies is exactly A.
 

Examples

ID 38656. Cards for three

Silent, Grumpy and Pilyulkin play a card game for three. The rules of the game are as follows.
First, each of the three players has a deck of cards.
There are N cards in Pilyulkin's deck, M cards in Silent Man's deck, and K cards in Grumbler's deck. Each card has a letter p, m or v written on it. The order of cards in decks cannot be changed. The players take turns. Pilyulkin goes first.
If there is at least one card in the current player's deck, discard the top card in the deck.
Then the next turn goes to the player whose name begins with the letter on the discarded card. For example, if the card says "p", the next turn goes to Pilyulkin.
If the current player's deck is empty, the game ends and the current player wins the game.
There are 3N + M + K possible layouts for three players' starting decks.
How many of these patterns will lead Pilyulkin to victory? Since the answer can be large, print it modulo 1000000007 (= 10⁹ +7).

Input
The input is three integers N, M and K (2<=N, M, K <=3*10⁵).

Imprint
Print the number of patterns winning for Pilyulkin modulo 1000000007 (= 10⁹ +7).

Examples

ID 38928. Until the New Year - 1

Snezhik Sugrobovich put a row of N Christmas balls in order to color them. He decided that each ball would be one of K colors. At the same time, Snezhik Sugrobovich wants any two adjacent Christmas tree balls & nbsp; were painted in different colors. Find the number of possible ways to color the Christmas balls.

Input
The input string contains two integers N and K (\(1<=N<=1000\),  \(2<=K<=1000\)).

Imprint
Display the answer to the problem. It is guaranteed that the correct answer does not exceed \(2^{31}-1\).

Examples