一排9

Time Limit: 1000ms

Memory Limit: 131071kb

Description

一维世界里有一种叫做9的生物,9的基因是一个整数,它的名字等于它的基因模L。
它们从左往右排成一排,每一天,排在最右边的9会分裂出一个新的9,新的9排在最右边。
假设旧的9的基因是a,那么新分裂出来的9的基因是(a * 999 + 9)模65536的值。
从一个9的位置向左到它或它之前的某个9,这一连串的9的名字连在一起将形成一个符卡。所以到第i天的时候,排在最右边的9能得到i个不同的符卡。如果这i个符卡中的某个符卡已经被之前的某个9得到,那么这个符卡对当前的这个9来说是没有效果的;否则就是有效的。
第一天只有一个基因为Q的9,到第N天的时候,拥有有效符卡最多的9有多少符卡?

Input

多组数据,每组有三个数字L(1<=L<=1024)、Q(0<=Q<65536)、N(0<N<=10000)。以EOF结尾。

Output

对于每组输入数据输出一行一个数字,表示拥有最多符文的9的符文数。

Sample Input

3 3 3
1024 3 3
9 9 9

Sample Output

1
3
8

Hint

None

Source

tsfn

提交代码