oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

pilingup Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

pilingup.html

Piling Up

Problem Statement

Joisino has a lot of red and blue bricks and a large box. She will build a tower of these bricks in the following manner.

First, she will pick a total of N bricks and put them into the box. Here, there may be any number of bricks of each color in the box, as long as there are N bricks in total. Particularly, there may be zero red bricks or zero blue bricks. Then, she will repeat an operation M times, which consists of the following three steps:

  • Take out an arbitrary brick from the box.
  • Put one red brick and one blue brick into the box.
  • Take out another arbitrary brick from the box.

After the M operations, Joisino will build a tower by stacking the 2 × M bricks removed from the box, in the order they are taken out. She is interested in the following question: how many different sequences of colors of these 2 × M bricks are possible? Write a program to find the answer. Since it can be extremely large, print the count modulo 109+7.

Limits

  • 1 ≤ N ≤ 3000
  • 1 ≤ M ≤ 3000

Subtask 1 (10%): 1 ≤ N, M ≤ 10

Subtask 2 (30%): 1 ≤ N, M ≤ 100

Subtask 3 (60%): No additional constraints

Subtask 4 (0%): Sample

Input

Input is given from Standard Input in the following format:

N M

Output

Print the count of the different possible sequences of colors of 2 × M bricks that will be stacked, modulo 109+7.

Sample Input 1

2 3

Sample Output 1

56

A total of six bricks will be removed from the box. The only impossible sequences of colors of these bricks are the ones where the colors of the second, third, fourth and fifth bricks are all the same. Therefore, there are 26 - 2 × 2 × 2 = 56 possible sequences of colors.

Sample Input 2

1000 10

Sample Output 2

1048576

Sample Input 3

1000 3000

Sample Output 3

693347555

Tags

AtCoder, Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110101s256MBMinimum
230101s256MBMinimum
360271s256MBMinimum
4031s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o pilingup -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.