ACTIV  Activities
Ana likes many activities. She likes acrobatics, alchemy, archery, art, Arabic dances, and many more. She joined a club that offers several classes. Each class has a time interval in every week. Ana wants to sign up for many classes, but since they overlap in time, she looks for a subset of nonoverlapping classes to attend. A subset is nonoverlapping if it does not contain two classes that overlap in time. If a class starts at the time another class ends, this is not considered overlapping.
Ana decided to list all the nonoverlapping nonempty subsets of classes. Then she will choose the subset she likes best. In order to predict the amount of paper needed to write the list, she wants you to calculate how many of these subsets there are.
Input
Each test case is described using several lines. The first line contains an integer N indicating the number of classes the club offers (1 ≤ N ≤ 10^{5} ). Each of the next N lines describes a class using two integers S and E that represent the starting and ending times of the class, respectively (1 ≤ S < E ≤ 10^{9} ). The end of input is indicated with a line containing a single −1.
Output
For each test case, output a single line with a single integer representing the number of nonoverlapping nonempty subsets of classes. To make your life easier, output only the last 8 digits of the result. If the result has less than 8 digits, write it with leading zeros to complete 8 digits.
Example
Input: 5 1 3 3 5 5 7 2 4 4 6 3 500000000 1000000000 1 500000000 1 500000000 1 999999999 1000000000 1 Output: 00000012 00000005 00000001
hide comments
parasnagpal:
20210718 01:28:34
A hint for the problem: https://youtu.be/8mUDO9lclY 

rushi2001:
20210610 09:48:26
Thanks @vivek singh rana


anupam_akib:
20210603 09:47:00
After 20 attempts, got AC! _ facing problem with mod. 

harshh3010:
20210322 21:06:35
use setw(8) and setfill('0') for output in c++


lamda_cdm_10:
20200920 05:22:38
remember to take mod of 10^8 ,costed me 3 WA for that


pacific_kafka:
20200823 15:57:56
Dynamic Programming makes me feels sad


vakulsingh:
20200730 13:41:23
just take mod 10^8 at every dp step,somehow did'not see that for a long time 

jopdhiwaala:
20200516 11:45:04
You could do to_string in c++ and output the characters. 

pallindromeguy:
20200329 10:00:27
Cost me 2 WA because I was taking mod 10^8+7 instead of just 10^8 :( 

dkkv0000:
20200119 19:21:08
AFTER 10 WA AC (0.16)

Added by:  Pablo Ariel Heiber 
Date:  20100924 
Time limit:  2.365s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 NODEJS OBJC VB.NET 
Resource:  FCEyN UBA ICPC Selection 2010 