# Grox的序列一

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

> Grox是未上轨道的实验。
>
> ——科学之书8（《Spore》，[英文资料](https://spore.fandom.com/wiki/Books_of_Science)）

怀着对真理的追求，你打算前往银河中心一探究竟。然而，庞大的 Grox 帝国占领了银河中心附近的星系。那里引力强、恒星密集，为了航行安全，曲率引擎只能把较近的恒星系设为目标。要顶着 Grox 的攻击强行冲过去，恐怕只有拿到“丑角”徽章的人才能办到。

为了与 Grox 结盟，你接下了 Grox 母星交来的任务：计算 Grox 序列。

Grox 半机械、半有机的身体能够在极其恶劣的环境中生存，但它们体内的有机结构也因此发生了不可逆的变化。其中有一种名为 GNA 的链状高分子结构：有 $a$ 种物质可以出现任意次，$b$ 种物质只能出现偶数次，另有 $c$ 种物质只能出现零次或奇数次。Grox 想知道长度为 $N$ 的有向 GNA 序列共有多少种。

## 形式化问题描述

有三组互不相同的符号，组与组之间也没有相同符号：

- 第一组有 $a$ 种，每一种都可以出现任意非负整数次。
- 第二组有 $b$ 种，每一种都必须出现偶数次，零次也允许。
- 第三组有 $c$ 种，每一种都必须出现零次或正奇数次。

求长度为 $N$ 的合法有向序列数，答案对 $p=1004535809$ 取模。两个序列不同，当且仅当至少一个位置的符号不同。每种符号的限制分别判断。长度为零时，唯一的空序列合法。

## 输入格式

四行依次给出十进制非负整数 $a,b,c,N$ .其中 $a,N$ 可能远超内置整数范围。

## 输出格式

输出一行一个整数，表示答案的非负最小剩余。

## 样例

### 样例 1

### 输入

```text
6
9
7
5
```

### 输出

```text
446518
```

### 样例 2

### 输入

```text
0
0
2
1
```

### 输出

```text
2
```

### 样例 3

### 输入

```text
0
0
0
0
```

### 输出

```text
1
```

## 样例解释

第一组按每一种符号的次数分别检查，得到 $446518$ 个序列。第二组只允许两种符号，各出现零次或正奇数次；长度为一时有两种选择。第三组是唯一的空序列。

## 数据范围与保证

$0\le a,N\le10^{1000}$ ，$0\le b\le10^5$ ，$0\le c\le1000$ .模数 $1004535809=479\times2^{21}+1$ 是质数，三是它的原根。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |