3094: 连乘问题

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:12 解决:11

题目描述

给定 n 个整数 �1,�2,⋯,��a1,a2,,an,请计算一组乘积,记为 �1,�2,⋯,��P1,P2,,Pn,其中 ��Pi 的定义如下:

��=�1⋅�2⋅�3⋯����Pi=aia1a2a3an

也就是说,��Pi 是 �1a1 到 ��an 的连乘再除去 ��ai。由于答案可能比较大,输出每个 ��Pi 模 1000010000 的余数。

输入

  • 第一行:单个整数表示 n
  • 第二行:n 个整数表示 �1,�2,⋯,��a1,a2,,an
  • 对于 30%30% 的数据,2≤�≤10002n1000
  • 对于 60%60% 的数据,2≤�≤100002n10000
  • 对于 100%100% 的数据,2≤�≤1000002n1000001≤��≤100001ai10000



输出

共 n 行:第 i 行输出 ��Pi 模 1000010000 的余数。

样例输入 复制

4
1 3 4 6

样例输出 复制

72
24
18
12