E. Student's Camp

Codeforces

IDCF708E

Time3000ms

Memory256MB

Difficulty—

dpmath

English · Original

Chinese · Translation

Formal · Original

Alex studied well and won the trip to student camp Alushta, located on the seashore. Unfortunately, it's the period of the strong winds now and there is a chance the camp will be destroyed! Camp building can be represented as the rectangle of _n_ + 2 concrete blocks height and _m_ blocks width. Every day there is a breeze blowing from the sea. Each block, except for the blocks of the upper and lower levers, such that there is no block to the left of it is destroyed with the probability . Similarly, each night the breeze blows in the direction to the sea. Thus, each block (again, except for the blocks of the upper and lower levers) such that there is no block to the right of it is destroyed with the same probability _p_. Note, that blocks of the upper and lower level are **indestructible**, so there are only _n_·_m_ blocks that can be destroyed. The period of the strong winds will last for _k_ days and _k_ nights. If during this period the building will split in at least two connected components, it will collapse and Alex will have to find another place to spend summer. Find the probability that Alex won't have to look for other opportunities and will be able to spend the summer in this camp. ## Input The first line of the input contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 1500) that define the size of the destructible part of building. The second line of the input contains two integers _a_ and _b_ (1 ≤ _a_ ≤ _b_ ≤ 109) that define the probability _p_. It's guaranteed that integers _a_ and _b_ are coprime. The third line contains a single integer _k_ (0 ≤ _k_ ≤ 100 000) — the number of days and nights strong wind will blow for. ## Output Consider the answer as an irreducible fraction is equal to . Print one integer equal to . It's guaranteed that within the given constraints . [samples] ## Note In the first sample, each of the four blocks is destroyed with the probability . There are 7 scenarios that result in building not collapsing, and the probability we are looking for is equal to , so you should print <center>![image](https://espresso.codeforces.com/f18cc58c5c7723d892cfdaf2e1c65a9f00fb366d.png)</center>

Alex 学习优异，赢得了前往海边学生营地 Alushta 的旅行机会。不幸的是，现在正值强风季节，营地有被摧毁的风险！营地建筑可以表示为一个高度为 #cf_span[n + 2]、宽度为 #cf_span[m] 的混凝土块矩形。每天，都会有一阵海风从海面吹来。每个非最上层和最下层的块，如果其左侧没有块，则以概率 #cf_span[p] 被摧毁。同样，每晚风向变为吹向大海。因此，每个非最上层和最下层的块，如果其右侧没有块，则同样以概率 #cf_span[p] 被摧毁。注意，最上层和最下层的块是*不可摧毁*的，因此只有 #cf_span[n·m] 个块可能被摧毁。强风将持续 #cf_span[k] 天和 #cf_span[k] 夜。如果在此期间建筑分裂为至少两个连通分量，它将坍塌，Alex 将不得不寻找其他地方度过夏天。求 Alex 无需另寻他处、仍能在此营地度过夏天的概率。输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 1500]），表示建筑可摧毁部分的尺寸。第二行包含两个整数 #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ a ≤ b ≤ 10^9]），表示概率 #cf_span[p]。保证整数 #cf_span[a] 和 #cf_span[b] 互质。第三行包含一个整数 #cf_span[k]（#cf_span[0 ≤ k ≤ 100 000]）——强风持续的天数和夜数。将答案视为一个最简分数 #cf_span[\frac{u}{v}]。请输出一个整数 #cf_span[u \cdot v^{-1} \bmod (10^9 + 7)]。保证在给定约束下该值存在。在第一个样例中，每个块被摧毁的概率为 #cf_span[\frac{1}{2}]。共有 #cf_span[7] 种情况会导致建筑不坍塌，我们所求的概率为 #cf_span[\frac{7}{16}]，因此你应该输出 #cf_span[7 \cdot 16^{-1} \bmod (10^9 + 7)]。 ## Input 输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 1500]），表示建筑可摧毁部分的尺寸。第二行包含两个整数 #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ a ≤ b ≤ 10^9]），表示概率 #cf_span[p]。保证整数 #cf_span[a] 和 #cf_span[b] 互质。第三行包含一个整数 #cf_span[k]（#cf_span[0 ≤ k ≤ 100 000]）——强风持续的天数和夜数。 ## Output 将答案视为一个最简分数 #cf_span[\frac{u}{v}]。请输出一个整数 #cf_span[u \cdot v^{-1} \bmod (10^9 + 7)]。保证在给定约束下该值存在。 [samples] ## Note 在第一个样例中，每个块被摧毁的概率为 #cf_span[\frac{1}{2}]。共有 #cf_span[7] 种情况会导致建筑不坍塌，我们所求的概率为 #cf_span[\frac{7}{16}]，因此你应该输出 #cf_span[7 \cdot 16^{-1} \bmod (10^9 + 7)]。

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ be the height and width of the destructible grid ($ n \times m $ blocks). Let $ p = \frac{a}{b} $ be the probability that a block is destroyed in a single wind event, where $ \gcd(a,b) = 1 $. Let $ k \in \mathbb{Z}_{\geq 0} $ be the number of days and nights (i.e., $ 2k $ wind events: $ k $ daytime eastward, $ k $ nighttime westward). Each destructible block at position $ (i,j) $, $ 1 \leq i \leq n $, $ 1 \leq j \leq m $, is subject to: - **Daytime (sea to land)**: destroyed with probability $ p $ if it has no surviving neighbor to its left (i.e., no block at $ (i,j-1) $ remains). - **Nighttime (land to sea)**: destroyed with probability $ p $ if it has no surviving neighbor to its right (i.e., no block at $ (i,j+1) $ remains). The destruction process occurs over $ k $ cycles of day-night, with dependencies between blocks and time steps. The building collapses if the remaining blocks form fewer than one connected component (i.e., split into ≥2 components). **Constraints** 1. $ 1 \leq n, m \leq 1500 $ 2. $ 1 \leq a \leq b \leq 10^9 $, $ \gcd(a,b) = 1 $ 3. $ 0 \leq k \leq 100000 $ **Objective** Compute the probability $ \frac{q}{r} $ that the grid remains **connected** after $ k $ day-night cycles, under the described stochastic destruction model. Output $ q \cdot r^{-1} \mod (10^9 + 7) $, where $ r^{-1} $ is the modular multiplicative inverse of $ r $ modulo $ 10^9 + 7 $.

Samples

Input #1

2 2
1 2
1

Output #1

937500007

Input #2

5 1
3 10
1

Output #2

95964640

Input #3

3 3
1 10
5

Output #3

927188454

API Response (JSON)

{
  "problem": {
    "name": "E. Student's Camp",
    "description": {
      "content": "Alex studied well and won the trip to student camp Alushta, located on the seashore. Unfortunately, it's the period of the strong winds now and there is a chance the camp will be destroyed! Camp buil",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF708E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alex studied well and won the trip to student camp Alushta, located on the seashore.\n\nUnfortunately, it's the period of the strong winds now and there is a chance the camp will be destroyed! Camp buil...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Alex 学习优异，赢得了前往海边学生营地 Alushta 的旅行机会。\n\n不幸的是，现在正值强风季节，营地有被摧毁的风险！营地建筑可以表示为一个高度为 #cf_span[n + 2]、宽度为 #cf_span[m] 的混凝土块矩形。\n\n每天，都会有一阵海风从海面吹来。每个非最上层和最下层的块，如果其左侧没有块，则以概率 #cf_span[p] 被摧毁。同样，每晚风向变为吹向大海。因此，每个非最上...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ be the height and width of the destructible grid ($ n \\times m $ blocks).  \nLet $ p = \\frac{a}{b} $ be the probability that a block is destroyed in a si...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments