/ Vijos / 题库 /

Valentine’s Seat

Valentine’s Seat

描述

今天是情人节的前一天,小杉还在电影院打工(惨啊…)。

老板很懂得情人节的情调,要小杉提前做好准备,那么现在给小杉的任务是对电影院的座椅上色。

电影院总共n+1行m+1列的椅子排成一个矩阵。第一行的椅子已经全部上了粉红色,第一列从第二个开始的椅子已经全部上了天蓝色。

一个可爱的上色方案应该满足除了第一行第一列以外,对任意的一个椅子,它的颜色应当和它左边的一把椅子(同行)或上面的一把椅子(同列)颜色相同。

小杉现在想知道总共有多少种可爱的上色方案。

格式

输入格式

一行两个整数n,m(1<=n,m<=3000)

输出格式

仅有一行,一个整数,为上色方案数对19900801取模的结果

样例1

样例输入1

1 1

样例输出1

2

限制

每个测试点1s

提示

样例解释:
唯一可上色的一把椅子,不是粉红就是天蓝,怎样都是可爱的

来源

lolanv

信息

ID
1420
难度
5
分类
组合数学 点击显示
标签
递交数
344
已通过
131
通过率
38%
上传者