Given a graph G initially having one node of label 1, you should do to the graph following steps K times:
- Let the current number of nodes in the graph is S
- copy the the graph G, let the copy be G'
- add the number S to labels of all nodes in G'
- Let the new graph be the union of G and G'
- for every i between 1 and S, add an edge between node i and node
Now you are required to calculate the number of paths of N steps which start at node A and pass through node B at least once then return to node A after the N-th step. Paths can pass through node A at intermediate steps.
The first and the only line consist of 4 integers, K, N, A and B.
Output a single integer, the answer to the problem modulo 1,000,000,007.
- 1 <= K <= 12
- 1 <= N <= 1,000,000,000
- 1 <= A, B <= 2^K
- A != B
The graph has 4 nodes, and 4 edges 1-2, 1-3, 2-4 and 3-4, the 6 paths are:
- 1 - 2 - 4 - 3 - 1
- 1 - 3 - 4 - 2 - 1
- 1 - 2 - 1 - 2 - 1
- 1 - 2 - 1 - 3 - 1
- 1 - 3 - 1 - 2 - 1
- 1 - 2 - 4 - 2 - 1
for each input file.
Marks are awarded when all the testcases pass.