Problem 1C. 一山不容二虎

Problem 1C. 一山不容二虎

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 1C. 一山不容二虎

时间限制:1000ms

空间限制:256MB

题目描述

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

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

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

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

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

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

输入格式

一行包含两个整数 \(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\)。

2024春 悬赏令第一周

未参加
状态
已结束
规则
OI
题目
6
开始于
2024-04-07 18:30
结束于
2024-04-21 00:00
持续时间
317.5 小时
主持人
参赛人数
72