小明的提醒:

本题数据范围有误导性！本题在笔试过程中使用dfs回溯法就能过所有数据，所以官方后台数据应该都是在很小的范围内。

题目内容

存储软件负责编程按照某写入策略，每次可向单块磁盘写入4KB数据，每写入几次可随机分配一次写入策略。存储软件的写入策略分为3种：

• 策略一：轮循写入
  例：存在3块硬盘0、1、2

  • 当n=2，写入顺序为0→1
  • 当n=5，写入顺序为0→1→2→0→1

• 策略二：优先写入剩余空间高的磁盘（剩余空间相同时，先写入序号小的硬盘）
  例：存在3块硬盘0、1、2，空间容量分别为12KB、16KB、24KB

  • 当n=2，写入顺序为2→2
  • 当n=5，写入顺序为2→2→1→2→0

• 策略三：按比例轮循写入
  例：存在3块硬盘0、1、2，写入比例为1:1:2

  • 当n=3，写入顺序为0→1→1
  • 当n=6，写入顺序为0→1→1→2→2→2

切换写入策略时，可切换不同的策略也可以和上次策略保持一致，切换策略后不继承上次写入策略的执行结果。
例如：3块硬盘0、1、2，写入比例为1:1:2，待写入的数据量有24KB

• 当n=2，一直通过策略1写入数据，写入顺序为（策略1）0→1→（策略1）0→1→（策略1）0→1
• 当n=2，一直通过策略3写入数据，写入顺序为（策略3）0→1→（策略3）0→1→（策略3）0→1
• 当n=5，一直通过策略1写入数据，写入顺序为（策略1）0→1→2→0→1→（策略1）0
• 当n=5，一直通过策略3写入数据，写入顺序为（策略3）0→1→2→2→0→（策略3）0

现在有一批数据要写入初始状态为空的硬盘，求存在几种写入策略分配，使最后硬盘空间的占用率（硬盘空间的占用率=硬盘写入的数据量/硬盘的总容量）保持均衡。

注：

1. 如果不存在合适的写入策略分配使最后硬盘空间的占用率保持均衡，则返回0；
2. 如果存在合适的写入策略，最终的磁盘空间占用率一定是整除的结果，精度>0.000001；
3. 不管是否写入成功，都算一次。例如：策略是轮循写入，n=3，磁盘是0、1、2，但1、2都满了，程序仍按0、1、2顺序写，失败了也算数，而不是跳过1、2继续写0。

输入描述

• 第一行：磁盘的个数（1~200）
• 第二行：每个磁盘的容量（单位KB，空间是4的倍数，1~10000）
• 第三行：磁盘的写入比例（1~1000）
• 第四行：待写入的总数据量（单位KB，总数据量是4的倍数，1~1000）
• 第五行：每n次切换一次写入策略（1~1000）

输出描述

存在几种写入策略分配，使最后的硬盘空间占用率保持均衡。

样例1

输入

3
64 64 64
1 1 1
12
3

输出

3

说明
总共有3块硬盘，每块硬盘有64KB容量，三块硬盘的写入比例为1:1:1，待写入12KB数据，每3次切换一次写入策略。存在3种写入策略分配使最后的硬盘空间占用率保持平衡：
方式1：策略1
方式2：策略2
方式3：策略3
采用3种方式均能保持写入后3块硬盘的空间占用率保持均衡，均为4/64=0.0625。

样例2

输入

3
128 64 32
1 1 1
4
3

输出

0

说明

总共有3块硬盘，每块硬盘分别有128KB、64KB、32KB容量，三块硬盘的写入比例比为1:1:1，待写入4KB数据，每3次切换一次写入策略，不存在写入策略分配使最后硬盘空间的占用率保持均衡，因此返回0。

样例3

输入

3
128 128 128
1 1 1
24
3

输出

9

说明

总共有3块硬盘，每块硬盘容量为128 KB，三块硬盘的写入权重比例为1:1:1，待写入24 KB数据，每3次切换一次写入策略。
共存在9种写入策略分配方式，可使最终三块硬盘的空间占用率保持均衡。

1. 策略1 → 策略1
2. 策略1 → 策略2
3. 策略1 → 策略3
4. 策略2 → 策略1
5. 策略2 → 策略2
6. 策略2 → 策略3
7. 策略3 → 策略1
8. 策略3 → 策略2
9. 策略3 → 策略3

采用9种方式均能保持写入后33块硬盘的空间占用率保持一致，均为8/128=0.0625。