CP Course Contest
A. I will win
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Your participating a tournament. The tournament consists of $$$n$$$ games. Your probability to win a game is $$$\frac{p}{q}$$$. Initially your rank in the tournament is $$$n+1$$$. If you win a game your rank will decrease by 1. If you lose a game, you rank will increase by 1. What is the probability that you will win the tournament (i.e. your rank will be 1)? Print answer modulo $$$10^9 + 7$$$.

Input

The first line contains one integer $$$T (1 \leq T \leq 2 \cdot 10^5)$$$ — number of testcases.

Each of the next $$$T$$$ lines contain three integers — $$$n, p, q$$$ $$$(1 \leq n, p, q \leq 10^{18})$$$, $$$(p \leq q)$$$.

Output

For each test case print your probability of winning the tournament. If it is $$$\frac{x}{y}$$$ print $$$x \cdot y^{-1}$$$ modulo $$$10^9 + 7$$$.

Example
Input
4
10000 1 1
1000000000000000000 2 2
2 1 2
1000000000000000000 900000000000000000 1000000000000000000
Output
1
1
250000002
100777456
Note

In the first test case, you will win every game, so answer is 1.

In the second test case, probability is $$$\frac{1}{4}$$$. So the answer will $$$1 \cdot 4^{-1}$$$ modulo $$$10^9 + 7$$$. Modular inverse of $$$4$$$ (mod $$$10000007$$$) is $$$2500002$$$. So the answer is $$$2500002$$$.

B. Gift
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You want to give your friend a gift on his birthday. The gift is a box of $$$n$$$ candies. You went to a candy shop and there are $$$m$$$ flavors of candy. The $$$i$$$th flavor is defined by the $$$i$$$th letter in the alphabet. i.e. first flavor is defined by $$$a$$$, second flavor is defined by $$$b$$$, third flavor is defined by $$$c$$$, $$$\cdots$$$ and so on.

Print all possible choices for candy box. Two candy box will be different if for any $$$i$$$, $$$i$$$th candy flavor in two boxes are different.

Print them in lexicographic order.

Input

Only line in the input contains two integers, $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 9$$$, $$$1 \leq m \leq 6$$$)

Output

First line of the output should contain one integer $$$k$$$ — number of possible choices.

Each of the next $$$k$$$ lines should contain a string of length $$$n$$$ denoting the choice. They should be in lexicographic order.

Examples
Input
3 2
Output
8
aaa
aab
aba
abb
baa
bab
bba
bbb
Input
1 1
Output
1
a
Input
1 2
Output
2
a
b