There are N balls of integral sizes ranging from X to Y (both included) arranged in a line.
Two arrangements Al and A2 of all the bails on the line are considered to be the same if at every
position i (1 <= i <= N) Size of ball A1, * Sire of bail A2, Else, the arrangements Al and A2 are consider to be different
Consider the following operation You can choose any two indices a.b such that 1 <= a <= b <= N and reverse the order of all balls from positions a to b. You can perform this operation at most once
How many different arrangements can you obtain ?
The first line contains N. X and Y respectively.
The next line contains N integers denoting the sizes of the balls arranged in the line.
1 <= N <= 1e6
1 <= X <= Y <= 1e9
An integer denoting the number of different arrangements that can be obtained.
Example
Input:
4 1 10
3 7 9 2
Output:
7
There are N intergers at a1,a2...aN let's call this V array
You are also given two integers A and B
You perform the following operation B times:
* Select the minimum element from the array V call it & and remove
insert x* A in the array
After completing all these B operations. Sort the array V.
Since the numbers in array V can be large, output V[i] % (10^9 + 7)
Input Format
NAB
a1 a2.. aN
Output:
Print integers of V one integer per line.
Constraints
1 < N < 50
1 < A. B < 10^9
1 < ai < 10^9
Example:
Input 1:
3 10 2
1 00 10
in Bangalore:
You can exchange one Gold coin with Gi Rupees, You can spend Gi rupees and get one Gold coin or spend 1 Gold coin and get Gi Rupees.
Similarly, Si is for Silver and Bi for Bronze.
To Buy/Sell: One coin of Gold, Silver, and Bronze in "Hyderabad" costs Gj. Sj, and Bj INR respectively.
You are in Bangalore currently and looking to increase your money, so you plan to visit Hyderabad and return to Bangalore.
Given that you have N rupees, what is the maximum money you can have after your return to Bangalore?
Note that: You are allowed to visit Hyderabad only once. But once you are in
place(Hyderabad/Bangalore) you can do as many transactions as you want. Also, you can buy/sell
at Bangalore before visit as well as after the visit
1 <= N <= 5000
1 <= Gi, Si, Bi, G], Sj. Bj <= 5000
N
Gi Si Bi
Gj Sj Bj
We are having a road of length M with M + 1 with bus stops at 0, 1,..M
"d-Bus" starts from the 0-th point and then stops at every d-th bus stop. For example, consider d2, then Bus starts at 0 and then stops at 2, 4, 6, .., 2*floor (M/2)
We have N flower gardens along the road. The i-th Garden ranges from [Ai, Bil, And the i-th garden
enly has plants that produce flower type i only.
You traveling in d-bus can collect i-th type flower if your bus stops at some point in the range (AI,Bi) For each da 1, 2, .. M.
Find the maximum number of different flowers you'll be able to collect when you travel in d-Bus
Note that there are unlimited flowers of each type.
Input:
N M
A1 B1
A2 B2
..
A_N B_N
Output:
Print M lines, d-th line should contain the maximum number of flowers you can collect when you
travel in d-bus