Lucky Volunteer Draw

In preparation for the Beijing 2008 Olympics (90 days before the opening), CTSC is organizing a lottery among its p volunteers. Each volunteer is initially assigned a unique number from 0 to p-1. On the big screen, there are five Fuwa (mascot) images with assigned numbers as follows: Beibei has 2, Jingjing has 3, Huanhuan has 4, Yingying has 5, and Nini has 6 (the numbers 0 and 1 are not used). Before the lottery, each Fuwa may have its eyes open or closed. At least one Fuwa will have its eyes open (if not, the button is pressed again).

Once the display stops, the lucky numbers are determined as follows:

• If a Fuwa’s eyes are open, its corresponding number is called a lucky number.
• If l₁ and l₂ (possibly equal) are lucky numbers, then their product l₁\times l₂ is also a lucky number.
• No other numbers are lucky.

Let L denote the set of all lucky numbers. When the numbers in L are arranged in increasing order, we denote the x-th smallest lucky number by l(x) (for example, if only Beibei and Jingjing have open eyes, then L = \{2,3,4,6,8,9,12,\dots\} and l(1)=2, l(4)=6 etc.).

After the Fuwa are observed, two numbers are generated such that the smaller one is a and the larger one is b. Define the set

$$T_{a,b} = \{d\in L \mid l(a) \mid d \text{ and } d \mid l(b)\}, $$

where \(x \mid y\) means \(x\) divides \(y\).

For any finite subset \(S\) of natural numbers, its characteristic value \(f(S)\) is defined recursively as follows:

• If \(S\) is empty, then \(f(S) = 0\).
• If \(S\) is nonempty, let \(d\) be the smallest element in \(S\); then

  $$f(S) = d + f(S\setminus\{d\}) + q \times d \times f(S\setminus\{d\}),$$
  
  where \(q\) is a given nonnegative integer and \(S\setminus\{d\}\) means \(S\) with \(d\) removed.</li>
  

The winning volunteer’s number is determined by computing \(f(T_{a,b}) \bmod p\) (i.e. the remainder when \(f(T_{a,b})\) is divided by \(p\)).

Input Format

• The first line contains four integers: \(p\), \(q\), \(a\), and \(b\) (\(1 \le a \le b\)).
• The second line contains five integers (each 0 or 1) corresponding to the state of the Fuwa in the order: Beibei, Jingjing, Huanhuan, Yingying, Nini. A value of 1 indicates that the Fuwa's eyes are open. It is guaranteed that at least one number is 1.

Output Format

• Output a single integer: the winning volunteer's number, which is \(f(T_{a,b}) \bmod p\).

Note on Lucky Numbers Generation:

Let the initial base \(S\) be the set of numbers corresponding to the Fuwa with open eyes. The set of lucky numbers \(L\) is the multiplicative closure of \(S\) (i.e. repeatedly multiplying any two lucky numbers yields another lucky number). You are only required to generate enough lucky numbers so that you can obtain \(l(b)\) (the \(b\)-th smallest lucky number). Since the lucky numbers are sorted in increasing order, all lucky numbers less than or equal to \(l(b)\) will appear among the first \(b\) generated numbers.

Example:

Input:
100 2 1 4
1 1 0 0 1
Explanation:

p = 100, q = 2, a = 1, b = 4
Fuwa open states: 1 1 0 0 1, so initial set S = {2, 3, 6}.
Generated lucky numbers (in increasing order): 2, 3, 4, 6, …
l(1)=2 and l(4)=6.
T = { d in L | 2 divides d and d divides 6 } = {2, 6}.
f({2,6}) = 2 + (1+2×2)*f({6}) = 2 + 5×(6 + (1+2×6)*0) = 2 + 5×6 = 32.
Winning volunteer's number = 32 mod 100 = 32.
</pre>

inputFormat
The first line contains four integers: p (number of volunteers), q (the multiplier used in the recursive function), a, and b (1 ≤ a ≤ b).
The second line contains five integers (each either 0 or 1) which represent the open (1) or closed (0) state of the Fuwa in the order: Beibei (2), Jingjing (3), Huanhuan (4), Yingying (5), Nini (6). It is guaranteed that at least one of these five numbers is 1.
outputFormat
Output a single integer, the winning volunteer's number: f(Ta,b) mod p.
sample
100 2 1 4
1 1 0 0 1
32