292. Functions

Problem Statement:
Given 2 sets X and Y, A good function is a function F:A  →  B, that can be constructed such that A is a non-empty subset from X, and B is a non-empty subset from Y.

- A function from A to B is an assignment for each element of A to exactly one element from B.
- An injective function is a function when every element in B is assigned to at most one element from A.
- An surjective function is a function when every element in B is assigned to at least one element from A.
- A bijective function is a function that is both injective and surjective.

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  50). Followed by T test cases. Each test case will consist of a single line, containing 2 integers separated by a single space: x, y (1  ≤  x  ≤  100, 1  ≤  y  ≤  1000) representing the size of the sets X and Y respectively.

Output Format:
For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed by 4 integers separated by single spaces representing the total possible number of injective good functions, surjective good functions, bijective good functions and the total number of possible good functions respectively. The values should be be printed modulo 109 + 7.

Sample Input:
4 1 1 1 3 3 1 2 2

Sample Output:
Case 1: 1 1 1 1 Case 2: 12 3 3 12 Case 3: 3 7 3 7 Case 4: 10 8 6 14

Notes:
Explanation of the "2 2" test case. Assume that X = (1, 2) and Y = (a, b).

Only Injective:

A = (1), B = (a, b), functions = (1 : a), (1 : b)

A = (2), B = (a, b), functions = (2 : a), (2 : b)

Only Surjective:

A = (1, 2), B = (a), functions = (1 : a, 2 : a)

A = (1, 2), B = (b), functions = (1 : b, 2 : b)

Bijective:

A = (1), B = (a), functions = (1 : a)

A = (1), B = (b), functions = (1 : b)

A = (2), B = (a), functions = (2 : a)

A = (2), B = (b), functions = (2 : b)

A = (1, 2), B = (a, b), functions = (1 : a, 2 : b), (1 : b, 2 : a)

Neither Injective nor Surjective:

A = (1, 2), B = (a, b), functions = (1 : a, 2 : a), (1 : b, 2 : b)

 Added by: ahmed_aly Added at: 2014-10-11 15:00:09 UTC Time Limit: 3 seconds Partial score: No Source: ACM Egyptian Collegiate Programming Contest 2014