Background

Everything in the world is so巧妙, the ocean of mathematics allows me to wander endlessly, and in that moment, I discovered beauty again.

Langze, the great mathematician of Zhencheng Ocean, responded to the call of the Zhencheng Ocean Hall Master and participated in this problem-setting.

Based on his thoughts and calculations, he came up with an interesting problem. Here is what he has to say to you:

Problem Description

The inspiration for this problem comes from this set of data:

This set of data follows the descriptive method rule, where the $ n+1 $th layer describes the data of the $ n $th layer from left to right. The description rule is as follows: Starting from the first data, whenever a consecutive sequence of $ a_1 $ $ b_1 $s is encountered, $a_1\,b_1$ is written as two new data at the end of the $ n+1 $th layer (this end is appended after the last data, and if the $ n+1 $th layer has no data initially, then this end is the beginning). Immediately after, the next consecutive sequence of $ a_2 $ $ b_2 $s ($b_1 \neq b_2$) is described, and so on, until all data is described, at which point the $ n+1 $th layer is also constructed. Here, $ n $ is a positive integer.

Now, I have a new idea. Given an initial data $ Q $ (the initial data is on the first layer, and the first layer has only one data—the initial data $ Q $), construct a set of data following a similar rule (descriptive method), called the "Langze Array". I define the rule as follows: Follow rule $ A $ on odd layers and rule $ B $ on even layers. The specific performance is shown in the following figure:

The above figure shows part of the Langze Array when the initial data is $ 1 $. As for what the rules are, you need to explore them.

But!!!

This is not the final purpose. What I want to test is, in the $ i $th layer, how many $ x $s are there (we define the layer where the initial data is located as the first layer)?

Input Format

The input consists of a single line containing three integers $ Q $, $ i $, and $ x $, separated by a space.

$ Q $ is the initial data for the Langze Array.

Output Format

The output consists of a single line containing an integer, representing the number of $ x $s in the $ i $th layer.

Since the output data is large, please take the modulo of the output data with $ 20171111 $ (i.e., the remainder of the original output data divided by $ 20171111 $ as the final output data).

Sample Input and Output

Sample Input #1

2 2 2

Sample Output #1

1

Sample Input #2

2 14 5

Sample Output #2

12

Notes

Sample 1 Explanation:

The constructed Langze Array (a small part) is:

Thus, the number of $ 2 $s in the $ 2 $nd layer is $ 1 $.

Note:

All data are integers;

If you have no clue, you can choose to solve some sub-problems;

The following is the range of input data for each test point:

见题面 Input 部分

见题面 Output 部分