Cellulose is pure carbohydrate, H C and O . No nitrogen at all. However, hay is not pure cellulose. Any plant product will contain at least traces of protein. Bacteria likely assist by scavenging this protein, making it more available. In practice, horses are usually fed some alfalfa hay. Alfalfa is a legume like beans and peas, and is relatively high in protein. And of course all domestic animals are routinely fed all sorts of suppliments incorporated into their feed.