All Tracks Algorithms Dynamic Programming Problem

Special Graph
Tag(s):

Math, Medium

Problem
Editorial
Analytics

Given a graph G initially having one node of label 1, you should do to the graph following steps K times:

  1. Let the current number of nodes in the graph is S
  2. copy the the graph G, let the copy be G'
  3. add the number S to labels of all nodes in G'
  4. Let the new graph be the union of G and G'
  5. 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
SAMPLE INPUT
2 4 1 2
SAMPLE OUTPUT
6
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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup Wildcard

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications