You are given a rectangular grid with n rows and m columns. The rows are numbered 1 to n, from bottom to top, and the columns are numbered 1 to m, from left to right.

You are also given k special fields in the form (row, column). For each i, where 0 <= i <= k, count the number of different paths from (1, 1) to (n, m) that contains exactly n special fields.

There is one rule you must follow. You are only allowed to make moves that are straight up or to the right. In other words, from each field (row, column), you can only move to field (row+1, column) or field (row, column+1).

Output an array of k + 1 elements. The i-th element (0-indexed) must be the number of different paths that contain exactly i special fields. Since, the answer can be too big, output it modulo 1000007.

Input:
First line contains three space separated integers, n, m and k. Next k lines, each contain two space separated integers, the coordinates of a special field.

Output:
k + 1 space separated integers, the answer to the question.

Constraints:
1 <= n, m, k <= 100
For all coordinates (r, c) - 1 <= r <= n, 1 <= c <= m
All coordinates are valid and different.