Kebab House

The young man Vahtang Bumerang makes kebabs at the world-famous fast-food chain Kebab House. Each kebab contains many ingredients.

This morning Vahtang has received an order to make $n$ kebabs. At first, he should put $q_1$ ingredients to the first kebab, then $q_2$ ingredients in the second one and so on. Vahtang spends one second to put one ingredient to a kebab, so it takes $q_i$ seconds to make the $i$-th kebab. When he finishes the kebab he immediately proceeds to the next one.

Vahtang often dreams about his lovely boomerang while making kebabs. Each dream takes exactly one second and Vahtang forgets to put one ingredient to kebab during this second. Fortunately, he never dreams twice in any consecutive $(t+1)$ seconds.

Due to dreams about boomerang, some kebabs may have lesser than the desired number of ingredients, but customers are still happy if the $i$-th kebab has at least $x_i$ ingredients in it.

Vahtang wants to calculate the number of ways to have dream seconds during his work while keeping all customers happy. Can you help him? The real answer may be very huge, so you must calculate it modulo $10^9+7$.

Input

The first line contains two integers $n$ and $t(1\le n\le 1000,0\le t\le 100)$ — the number of kebabs and minimal possible time between dream seconds.

Each of the next $n$ lines contains two integers $q_i,x_i(1\le q_i\le 250,0\le x_i\le q_i)$ — the number of ingredients in the $i$-th kebab and the minimum number of ingredients to make the $i$-th customer happy.

Output

Print one integer — the number of ways to distribute dream seconds modulo $10^9+7$.

Examples