# 升级工具箱

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：128 MB

## 背景故事

武装采矿车发现了一批升级工具箱。不同类型的工具箱价值不同，仓库数量和各类物资预算也有限。调度员想知道：分别装载零个、一个、两个……工具箱时，各有多少种类型数量搭配。

## 形式化问题描述

有 $n$ 种工具箱，编号为 $1$ 到 $n$ .第 $i$ 种每个价值为 $i$ ，最多有 $K_i$ 个，所采集的该种工具箱总价值不能超过 $V_i$ .

一个方案由整数向量 $(c_1,\ldots,c_n)$ 表示，其中

$$0\le c_i\le K_i,\qquad i c_i\le V_i$$

同种工具箱不作区分；两种方案不同，当且仅当至少一种工具箱的数量不同。每种类型的价值上限独立计算，没有所有类型共享的总价值上限。

令 $C_i=\min(K_i,\lfloor V_i/i\rfloor)$ ，$S=\sum_{i=1}^n C_i$ .请依次计算工具箱总数量为 $0,1,\ldots,S$ 的方案数，并对 $100000007$ 取模。$n=0$ 时只存在空方案，$S=0$ .

## 输入格式

第一行一个整数 $n$ .接下来 $n$ 行，第 $i$ 行两个整数 $K_i,V_i$ .

## 输出格式

输出一行 $S+1$ 个整数，第 $j+1$ 个表示总数量为 $j$ 的方案数对 $100000007$ 取模的结果。

## 样例 1

### 输入

```text
3
10 2
1 10
1 10
```

### 输出

```text
1 3 4 3 1
```

### 解释

三种类型的数量上限分别为 $2,1,1$ .选两个工具箱的四种数量向量为 $(2,0,0),(1,1,0),(1,0,1),(0,1,1)$ .

## 样例 2

### 输入

```text
0
```

### 输出

```text
1
```

### 解释

空方案恰有一种。

## 样例 3

### 输入

```text
3
0 1000
3 5
1000 2
```

### 输出

```text
1 1 1
```

### 解释

只有第二种可采集，最多两个。第一种数量为零不会改变第二种的编号或单价。

## 数据范围与保证

$0\le n\le1000$ ，$0\le K_i,V_i\le1000$ ；所有输入量均为整数。

### 数据分组

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