#P1501. 一山不容二虎

一山不容二虎

题目描述

一座山头容不得两只老虎,除非他们一公一母

随着时代变迁,世界上的老虎越来越少了呢。为了保护老虎,人类在登陆火星后,特地为老虎搭建了一片区域

为了美观与方便管理,这片区域由 nnmm 列个牢笼组成,每个牢笼都很大,以方便老虎活动。

资深老虎专家说,放置老虎时,需要注意以下两点:

  • 每个牢笼最多放置一只老虎,否则多只老虎在一起就会打架
  • 每只老虎会时刻注视着自己所在的行和列。
    1. 对于某只老虎,若该行只有自己,它会很高兴;
    2. 如果该行还有另外一只老虎,它会主观认为该老虎与自己性别不同,所以也会很高兴;
    3. 如果这一行,还有另外两只及以上的老虎,它们会感受到同性的威胁而心情崩溃。
    4. 对于每一列,同理

假如你是老虎保护协会的一把手,负责把任意只老虎放在这片区域里,也可以不放,使得每只老虎的心情都很好,请问有多少种放置方法。

输入格式

一行包含两个整数 n,mn,m,之间由一个空格隔开。

输出格式

总共的方案数,由于该值可能很大,只需给出方案数模 99999739999973 的结果。

样例 #1

样例输入 #1

1 3

样例输出 #1

7

提示

样例说明

除了 33 个牢笼里都放置老虎以外,其它方案都是可行的,所以一共有 2×2×21=72 \times 2 \times 2-1=7 种方案。

数据规模与约定

  • 对于 30%30\% 的数据,nnmm 均不超过 66
  • 对于 50%50\% 的数据,nnmm 至少有一个数不超过 88
  • 对于 100%100\% 的数据,1n,m1001 \leq n,m \leq 100