There are N numbered boxes placed on a table, let Bi denote the ith box in the line. Write a program that finds the total number of ways to place N identical balls such that at most k balls are present in the boxes B1 .... Bk for 1<=k<=N. Since the number can be quite large you are supposed to output the answer modulo 761238923.

Input

Input will contain multiple testcases, on each line N (1<=N<=100) will be given. The last line contains 0 which should not be processed.

Output

For each testcase output exactly one line, the total number possible of ways modulo 761238923.

Example

Input:
1
2
0

Output:
1
2