Grox的序列一¶
预估时间限制：0.5 秒。内存限制：128 MB。
实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
Grox是未上轨道的实验。
——科学之书8（《Spore》，英文资料）
怀着对真理的追求，你打算前往银河中心一探究竟。然而，庞大的 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¶
输入¶
6
9
7
5
输出¶
446518
样例 2¶
输入¶
0
0
2
1
输出¶
2
样例 3¶
输入¶
0
0
0
0
输出¶
1
样例解释¶
第一组按每一种符号的次数分别检查，得到 \(446518\) 个序列。第二组只允许两种符号，各出现零次或正奇数次；长度为一时有两种选择。第三组是唯一的空序列。
数据范围与保证¶
\(0\le a,N\le10^{1000}\) ，\(0\le b\le10^5\) ，\(0\le c\le1000\) .模数 \(1004535809=479\times2^{21}+1\) 是质数，三是它的原根。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |