Covering the Row

You are given a row with \(n\) cells and \(m\) persons. Initially, every person is located at cell 1. Each person makes a sequence of jumps until they jump out of the \(n\) cells. From any cell \(i\) (even at \(i=n\)), a person may choose one of the following moves:

• Jump one cell forward (to cell \(i+1\)); there are \(p\) distinct ways to do this.
• Jump two cells forward (to cell \(i+2\)); there are \(q\) distinct ways to do this.

When a jump takes a person beyond cell \(n\) (i.e. \(i+d>n\)), the journey terminates. Note that even in cell \(n\) a person can make a jump (which will necessarily take them out of the row).

Your task is to count the total number of assignments of jump choices (one sequence for each person) so that every cell from 1 to \(n\) is visited by at least one person. Two assignments are considered different if at least one person makes a different jump choice in their sequence. The answer is the sum over all valid assignments.

Hint: Use inclusion–exclusion. For each subset \(S\subseteq\{2,3,\dots,n\}\) (since cell 1 is always visited) consider the number of ways a single person can avoid visiting any cell in \(S\). Let \(f(i,S)\) be the number of ways to complete the journey starting from cell \(i\) while never landing on a cell in \(S\). Then we have:

[ f(i,S)=\begin{cases} 0,&\text{if } i\in S,\ ;p\cdot f(i+1,S)+q\cdot f(i+2,S),&\text{if } i<n,\ p+q,&\text{if } i=n\text{ (since even from cell (n) one can jump out)}. \end{cases} ]

The number of valid assignments is then given by

[ \sum_{S\subseteq{2,\ldots,n}}(-1)^{|S|}\Bigl(f(1,S)\Bigr)^m. ]

inputFormat

The input consists of a single line with four integers \(n\), \(m\), \(p\), and \(q\) separated by spaces.

\(n\): the number of cells.
\(m\): the number of persons.
\(p\): the number of ways to jump one cell.
\(q\): the number of ways to jump two cells.

outputFormat

Output a single integer: the total number of valid jump assignments such that every cell from 1 to \(n\) is visited by at least one person.

sample

3 1 1 1

2