Hyperactive Girl
| English | Vietnamese |
Gene and Gina have a particular kind of farm. Instead of growing animals and vegetables, as
it is usually the case in regular farms, they grow strings. A string is a sequence of characters.
Strings have the particularity that, as they grow, they add characters to the left and/or to the
right of themselves, but they never lose characters, nor insert new characters in the middle.
Gene and Gina have a collection of photos of some strings at different times during their growth.
The problem is that the collection is not annotated, so they forgot to which string each photo
belongs to. They want to put together a wall to illustrate strings growing procedures, but they
need your help to find an appropriate sequence of photos.
Each photo illustrates a string. The sequence of photos must be such that if si comes imme-
diately before si+1 in the sequence, then si+1 is a string that may have grown from si (i.e., si
appears as a consecutive substring of si+1). Also, they do not want to use repeated pictures,
so all strings in the sequence must be different.
Given a set of strings representing all available photos, your job is to calculate the size of the
largest sequence they can produce following the guidelines above.
Helen is a hyperactive girl. She wants to schedule her activities so that at any moment of the day there is at least one thing she can do. She does not care if her activities overlap in time, as long as every moment of her day has an activity scheduled.
Helen divided the day in a particular way. The day starts at time 0 and finishes at time M. Each moment of the day is represented by a real number between 0 and M, inclusive. Helen made a list of all possible activities, with their start and finish times. Now she must decide which subset of activities to schedule.
If an activity starts at time S and finishes at time F, then we say that it covers all moments between S and F, inclusive. Helen does not want to waste any activities, so she will only choose minimal subsets of activities that cover the day to be scheduled. A subset of activities is a minimal subset that covers the day if and only if:
1. every moment of the day is covered by at least one activity of the subset; and
2. removing any of the activities from the subset would leave at least one moment of the day uncovered.
Note that some moments of the day may be covered by more than one activity.
Given the list of possible activities for one day, you must help Helen by determining how many distinct minimal subsets cover the day.
Input
Each test case is given using several lines. The first line contains two integers M and N, representing respectively the highest value for a moment in the day (1 ≤ M ≤ 10^9) and the number of possible activities for the day (1 ≤ N ≤ 100). Each of the next N lines describes one possible activity and contains two integers S and F, representing respectively the start and finish times of the activity (0 ≤ S < F ≤ M).
The last test case is followed by a line containing two zeros.
Output
For each test case output a single line with a single integer representing the number of minimal subsets that cover the day. To make your life easier, print the remainder of dividing the solution by 10^8.
Sample
input
8 7 0 3 2 5 5 8 1 3 3 6 4 6 0 2 1 1 0 1 2 1 0 1 0 0
output
4 1 0