Andryusha has found a perplexing arcade machine. The machine is a vertically adjusted board divided into square cells. The board has w columns numbered from 1 to w from left to right, and h rows numbered from 1 to h from the bottom to the top. Further, there are barriers in some of board rows. There are n barriers in total, and i -th of them occupied the cells l i through r i of the row u i . Andryusha recollects well that no two barriers share the same row. Furthermore, no row is completely occupied with a barrier, that is, at least one cell in each row is free. The player can throw a marble to any column of the machine from above. A marble falls downwards until it encounters a barrier, or falls through the bottom of the board. A marble disappears once it encounters a barrier but is replaced by two more marbles immediately to the left and to the right of the same barrier. In a situation when the barrier is at an edge of the board, both marbles appear next to the barrier at the side opposite to the edge. More than one marble can occupy the same place of the board, without obstructing each other's movement. Ultimately, all marbles are bound to fall from the bottom of the machine. Peculiarly, sometimes marbles can go through barriers as if they were free cells. That is so because the barriers are in fact alive, and frightened when a marble was coming at them from a very high altitude. More specifically, if a marble falls towards the barrier i from relative height more than s i (that is, it started its fall strictly higher than u i + s i ), then the barrier evades the marble. If a marble is thrown from the top of the board, it is considered to appear at height ( h + 1) . Andryusha remembers to have thrown a marble once in each of the columns. Help him find the total number of marbles that came down at the bottom of the machine. Since the answer may be large, print it modulo 10 9 + 7 . The first line contains three integers h , w , and n ( 1 ≤ h ≤ 10 9 , 2 ≤ w