Problem 1C. 一山不容二虎
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem 1C. 一山不容二虎
时间限制:1000ms
空间限制:256MB
题目描述
一座山头容不得两只老虎,除非他们一公一母
随着时代变迁,世界上的老虎越来越少了呢。为了保护老虎,人类在登陆火星后,特地为老虎搭建了一片区域
为了美观与方便管理,这片区域由 \(n\) 行 \(m\) 列个牢笼组成,每个牢笼都很大,以方便老虎活动。
资深老虎专家说,放置老虎时,需要注意以下两点:
- 每个牢笼**最多放置一只老虎**,否则多只老虎在一起就会打架
- 每只老虎会时刻注视着自己所在的行和列。
- 对于某只老虎,若该行只有自己,它会很高兴;
- 如果该行还有另外一只老虎,它会主观认为该老虎与自己性别不同,所以也会很高兴;
- 如果这一行,还有另外两只及以上的老虎,它们会感受到同性的威胁而心情崩溃。
- 对于每一列,同理
假如你是老虎保护协会的一把手,负责把 任意只 老虎放在这片区域里, 也可以不放 ,使得每只老虎的心情都很好,请问有多少种放置方法。
输入格式
一行包含两个整数 \(n,m\),之间由一个空格隔开。
输出格式
总共的方案数,由于该值可能很大,只需给出方案数模 \(9999973\) 的结果。
样例 #1
样例输入 #1
1 3
样例输出 #1
7
提示
样例说明
除了 \(3\) 个牢笼里都放置老虎以外,其它方案都是可行的,所以一共有 \(2 \times 2 \times 2-1=7\) 种方案。
数据规模与约定
- 对于 \(30\%\) 的数据,\(n\) 和 \(m\) 均不超过 \(6\)。
- 对于 \(50\%\) 的数据,\(n\) 和 \(m\) 至少有一个数不超过 \(8\)。
- 对于 \(100\%\) 的数据,\(1 \leq n,m \leq 100\)。