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...

## This Problem was Asked in

Challenge Name

LNMIIT Algorithms Cup - June 2017

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Math > Number Theory
• Data Structures > Advanced Data Structures
• Algorithms > Graphs
Уведомления

?