Description

There’re bacterias in the Petri dish. The only thing they can do is to reproduce themselves everyday.

After one bacteria reproduce itself, there will be one origin bacteria and y newborn bacterias.
Suppose there’re x bacterias on the first day.
Your task is to compute how many bacterias on the n-th day.

Please output the answer modulo 10177 because the answer may be too large to be represented by int.

Hint: if you got TLE, try to optimize power by recursion.

#define MOD 10177
// Ch7 Slide P.35
// compute an
int fast_pow(int a, int n){
    if( n == 0 ){ // basis
        return 1;
    }
    else{ // resursive 
        int k = ???;
        // if n is even:
        // return (k*k)%MOD
        // if n is odd:
        // return ???
    }
}

Input

There are multiple lines of input.
Each line contains 3 positive integers x,y,n

• 0 ≤ x, y ≤ 10,000
• 1 ≤ n ≤ 10,000,000
• The input is ended by EOF.

Output

Print the number of bacterias on the n-th day modulo 10177 for each line of input.
Remember ‘\n’ on the end of line.

Explantation of Sample I/O:

• (1, 0, 9): 1 bacteria at first day. There’re no newborn bacteria after reproduction. There’s still 1 bacteria on 9-th day.
• (4, 5, 6): 4 bacterias at first day. After every bacteria reproduce itself, there’re 4 + 4*5 bacterias on the second day. On 6-th day, there’re 31,104 bacterias, 31104 modulo 10177 = 573

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Little Brick(小磚頭) once wanted to register an account on a webpage,
however, he didn't know what password he should use,
he wanted his password in increasing ASCII code order,
and he listed some characters that he wanted to use in the password,
can you show all possible passwords that he can choose.

That is, a valid password must contain 4 or more characters and be in an increasing order of ASCII code,
Every character in the list can only be used once.
You must list all possible passwords in lexicographical order.

ouo.

Lexicographical Order: Given two different sequences, if two words have the same first letter, we compare the second. If the second letters are the same, we compare the third, etc. Finally, one word comes before the other if the first differing letter comes before the corresponding letter. If two words are identical up to the length of the shorter word, the shorter word comes first.

For example, if the input is "acebd", then you should output
abcd, abcde, abce, abde, acde, bcde
Note that "abed" is not valid since characer 'e' should be after 'd',
and "abd" is not a valid password too because its length is only 3.

Note that the ASCII codes for 'A'-'Z' are 65-90 and for 'a'-'z' are 97-122.

Input

Input contains only 1 line, representing the list of some characters that can be used in the password.

It is guaranteed that the characters will not be duplicated,
and 4 <= length of the given list <= 18, and the characters will only be lowercase or uppercase alphabet.

Output

Output contains only one line.

List all possible passwords in lexicographical order, separated by ", " (without quotes)

Remember to add a newline character after your output.

Sample Input  Download

Sample Output  Download

Tags

Discuss