Special Graph
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
i+S
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.
Input format:
The first and the only line consist of 4 integers, K, N, A and B.
Output format:
Output a single integer, the answer to the problem modulo 1,000,000,007.
Constraints:
- 1 <= K <= 12
- 1 <= N <= 1,000,000,000
- 1 <= A, B <= 2^K
- A != B
Explanation
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
Time Limit:
1.0 sec(s)
for each input file.
Memory Limit:
256 MB
Source Limit:
1024 KB
Marking Scheme:
Marks are awarded when all the testcases pass.
Allowed Languages:
C,
C++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Visual Basic