跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F2549. Dima and Figure

  • ID: 2555
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 动态规划
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Dima and Figure

题目描述

D. Dima and Figure
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Dima loves making pictures on a piece of squared paper. And yet more than that Dima loves the pictures that depict one of his favorite figures.

A piece of squared paper of size n×m is represented by a table, consisting of n rows and m columns. All squares are white on blank squared paper. Dima defines a picture as an image on a blank piece of paper, obtained by painting some squares black.

The picture portrays one of Dima's favorite figures, if the following conditions hold:

  • The picture contains at least one painted cell;
  • All painted cells form a connected set, that is, you can get from any painted cell to any other one (you can move from one cell to a side-adjacent one);
  • The minimum number of moves needed to go from the painted cell at coordinates (x1,y1) to the painted cell at coordinates (x2,y2), moving only through the colored cells, equals |x1-x2|+|y1-y2|.

Now Dima is wondering: how many paintings are on an n×m piece of paper, that depict one of his favorite figures? Count this number modulo 1000000007(109+7).

Input

The first line contains two integers n and m − the sizes of the piece of paper (1≤n,m≤150).

Output

In a single line print the remainder after dividing the answer to the problem by number 1000000007(109+7).

Examples
Input
2 2
Output
13
Input
3 4
Output
571

题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 2195 题。保留原作者与原赛事署名。