All Tracks Problem

XYZ Obsessed
Tag(s):

Dynamic Programming, Medium

Problem
Editorial
Analytics

Zoro is totally obsessed with the letters XYZ. Obsession here is a bit literal. He loves having space between letters X and Z.

Due to his obsession he thought of a problem:

Given integers N and K. Find the number of strings of length exactly N and having exactly K sub sequences where X and Z have exactly 1 space in between. The string can contains all upper_case English alphabets.

Note

Answer may be too large so output it modulo \(10^{9}+7\)

Input

A single line containing N and K.

Output

Print the desired output modulo \(10^{9}+7\).

Constraints

\( 1 \leq N \leq 2000\)
\( 0\leq K \leq N \)

SAMPLE INPUT
3 1
SAMPLE OUTPUT
52
Explanation

The length of the string is 3 and we need only 1 desired subsequence. The strings can be:
XAZ ZAX
XBZ ZBX
.
.
.
.
XZZ ZZX

So there will be 54 strings possible.

Time Limit: 0,5 sec(s) for each input file.
Memory Limit: 1024 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, 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, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

The LNM Institute of Information Technology

Challenge Name

LNMIIT Algorithms Cup - June 2017

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?