Problem D
ETS Problem Setting
Input: Standard Input

Output: Standard Output

 

ETS is an QSA based organization that conducts ETS (Extra Terrestrial Scholastic) Exams to allow Extra Terrestrial beings (Aliens) to study in QSA. Many aliens being afraid of ETS exams, study in Euphoria instead. Each year billions of ETS exams are conducted as more than a trillion Aliens appear in it from all planets of the universe to get the coveted opportunity of studying in QSA.

 

As billions of exams are conducted so it is simply impossible for ETS to set new questions for ETS exams. That is why they use the same math problem in many exams by changing the figures/numbers only. For each math problem they write an intelligent program that can change the figures or numbers intelligently. Let’s consider a typical ETS math problem now:

 

A dice with n faces are thrown. All the faces are equally likely to appear on top. The numbers 1, 2, 3, …, n are written on the n faces. So the sample space of the event that denotes the number appearing on the top of the dice is S={1, 2, 3, 4, …, n}. Event A is defined as {a1, a2, a3, …} and Event B is defined as {b1, b2, b3  …}. Now please verify whether or not event A and B are independent with each other.

 

Now it is obvious that for different values of n and different definition of event A and B, these two events can be dependent or independent. But if values of n, A, B are randomly chosen then the in most cases A and B will be dependent. So an intelligent program is needed to assign the values of n, A and B. Your task in this problem is something similar. Given the values of n you will have to find the number of event pairs which are independent. An event is a subset of the sample space. For example the event {1, 2, 4} denotes that the dice shows 1, 2 or 4. No event can be empty in a valid independent event pair. For n=3 the sample space of the dice (A dice with three faces!!!)  is {1, 2, 3} and there are 13 possible independent event pairs. These are:

 

(1) {1}  {1,2,3}

(2) {2}  {1,2,3}

(3) {1,2}  {1,2,3}

(4) {3}  {1,2,3}

(5) {1,3}  {1,2,3}

(6) {2,3}  {1,2,3}

(7) {1,2,3}  {1}

(8) {1,2,3}  {2}

(9) {1,2,3}  {1,2}

(10) {1,2,3}  {3}

(11) {1,2,3}  {1,3}

(12) {1,2,3}  {2,3}

(13) {1,2,3}  {1,2,3}       

 

Two events A and B are independent if and only if P(AB)=P(A)*P(B).

 

Input

The input file contains at most 200 lines of inputs. Each line contains an integer n(0<n<1001). Input is terminated by a line containing a single zero. This line should not be processed.

 

Output

For each line of input produce one line of output. This line contains an integer which denotes the value P modulo 100000000. Here P is the number of independent event pairs that can be created from the sample space {1, 2, 3, …, n}. P can be a very large number for larger values of n. So you are asked to print the modulo 100000000 value. 

 

Sample Input                            Output for Sample Input

1

2

3

6

50

0

1

5

13

845

18954245

 

Problemsetter: Shahriar Manzoor

Special Thanks: Derek Kisman